Wyzwanie

N miast jest wyrównanych w linii prostej. I-te miasto znajduje się A[i]kilometry na prawo od miejsca pochodzenia. Żadne dwa miasta nie będą w tym samym miejscu.

Zamierzasz zbudować sieć elektryczną z kilkoma elektrowniami. Elektrownie muszą być budowane w mieście. Możesz budować tylko Kelektrownie (<N), więc będą miasta, w których nie będzie elektrowni. Dla każdego miasta bez elektrowni musisz zbudować kabel między nim a najbliższym miastem, które ma elektrownię .

Na przykład, jeśli są zlokalizowane trzy miasta 0, 1, 2, a tylko miasto 0ma elektrownię, musisz zbudować dwa kable, jeden od 2do 0(2 km), a drugi od 1do0 (1 km) o łącznej długości 3 km .

Dane Ki pozycje miast (A ), należy obliczyć minimalną liczbę kilometrów kabla potrzebną do zbudowania sieci.

Przykładowe przypadki testowe

K = 1, A = [0, 2, 4, 6, 8] : 12 
# build power plant in the city at position 4, total length = 4 + 2 + 0 + 2 + 4 = 12

K = 3, A = [0, 1, 10, 11, 20, 21, 22, 30, 32] : 23
# build power plants in cities at positions 0, 10 and 22

K = 5, A = [0, 1, 3, 6, 8, 11, 14] : 3
# build power plants in all cities except those at positions 0, 3

K = 6, A = [0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84] : 49

Dane techniczne

• Powinieneś zaimplementować funkcję lub program, który przyjmuje dodatnią liczbę całkowitą Ki listę liczb całkowitych Aw dowolnej formie, i wypisuje / zwraca liczbę całkowitą reprezentującą odpowiedź.

• A jest posortowane w porządku rosnącym, a wszystkie elementy są liczbami całkowitymi nieujemnymi.

• A[0] = 0, i A[N-1]będzie nie więcej niż 1000 N.

• Zauważ, że moc wyjściowa będzie wynosić 1000 N ² , więc w większych przypadkach możesz potrzebować 64-bitowych liczb całkowitych w niektórych językach.

• Wielowątkowość nie jest dozwolona ( ustawię powinowactwo twojego programu na 1 rdzeń podczas oceniania). -O2Dozwolone są optymalizacje kompilatora (takie jak w C).

Punktacja

• Wyznaczę czas twojego kodu na moim komputerze (Ubuntu 16.04 z procesorem Intel i7-3770S) z różnymi rozmiarami przypadków testowych. W szczególności wygeneruję kilka przypadków testowych z N = floor (2 ^{x / 5} ), gdzie x jest dodatnią liczbą całkowitą.
  Twój wynik będzie wartością x najmniejszej próbki testowej, którą Twój program używa dłużej niż 10 sekund lub 1 GiB pamięci lub nie daje poprawnej odpowiedzi.

  • Odpowiedź z najwyższym wynikiem wygrywa. Jeśli dwie odpowiedzi otrzymają ten sam wynik, wygrywa wcześniejsza odpowiedź.

• Wszystkie programy będą oceniane według tego samego zestawu przypadków testowych.

• Możesz dodawać własne wyniki. Zachęcamy do objaśnienia twojego algorytmu.

Premia

To mój program w C ++, który ma 108 punktów . Możesz zweryfikować skrót SHA-256 9a87fa183bad1e3a83d2df326682598796a216b3a4262c32f71dfb06df12935dprzez cały segment kodu (bez stopki) w łączu.

Algorytm łączy wyszukiwanie binarne i optymalizację Knutha, aby znaleźć właściwą karę dla każdej rośliny i uzyskać żądaną liczbę. Złożoność wynosi O (N log N log A [N-1]). Byłem zaskoczony, że program uzyskał wyższy wynik niż rozwiązanie O (N log A [N-1]) Andersa Kaseorga . Prawdopodobnie wynika to z faktu, że przypadek dziennika w optymalizacji Knutha zwykle nie występuje.

Pamiętaj, że to wyzwanie jest takie samo jak w przypadku urzędu pocztowego IOI 2000 . Jednak pierwotne ograniczenia to N <= 300 i K <= 30.

Rdza , wynik = 104

Jest to implementacja algorytmu zauważonego przez Grønlund i in. (2017) na końcu §3.3.1, chociaż musiałem przestrzegać długiego łańcucha cytowań i uzupełnić brakujące dane. Działa w czasie O ( N log A [ N - 1]).

Kompiluj z rustc -O. Format wejściowy znajduje Księ w pierwszym wierszu, po nim wpisy A, jeden wpis w wierszu, wszystkie na standardowym wejściu.

(Uwaga: przesyłam to godzinę po terminie nagród, ale spodziewam się, że ostatnia wersja, którą przesłałem przed upływem terminu nagród , który upłynął w czasie O ( N log N log A [ N - 1]), uzyskała około 94 .)

use std::cmp::min;
use std::io::{self, BufRead};
use std::iter::{once, Cloned};
use std::num::Wrapping;
use std::ops::Range;
use std::slice;
use std::time::Instant;
use std::u64;

type Cost = u64;
const INF: Cost = u64::MAX;

trait ColsTrait<Col>: Clone {
    type Iter: Iterator<Item = Col>;
    fn len(&self) -> usize;
    fn iter(&self) -> Self::Iter;
    fn slice(&self, range: Range<usize>) -> Self;
}

impl<'a, Col: Clone> ColsTrait<Col> for &'a [Col] {
    type Iter = Cloned<slice::Iter<'a, Col>>;
    fn len(&self) -> usize {
        (*self).len()
    }
    fn iter(&self) -> Self::Iter {
        (*self).iter().cloned()
    }
    fn slice(&self, range: Range<usize>) -> Self {
        unsafe { self.get_unchecked(range) }
    }
}

impl ColsTrait<usize> for Range<usize> {
    type Iter = Range<usize>;
    fn len(&self) -> usize {
        self.end - self.start
    }
    fn iter(&self) -> Range<usize> {
        self.clone()
    }
    fn slice(&self, range: Range<usize>) -> Self {
        Range {
            start: self.start + range.start,
            end: self.start + range.end,
        }
    }
}

fn smawk<Col: Copy, Cols: ColsTrait<Col>, Key: Ord, F: Copy + Fn(usize, Col) -> Key>(
    n: usize,
    shift: u32,
    cols: Cols,
    f: F,
) -> Vec<usize> {
    if n == 0 {
        Vec::new()
    } else if cols.len() > n {
        let mut s = Vec::with_capacity(n);
        let mut sk = Vec::with_capacity(n);
        for (jk, j) in cols.iter().enumerate() {
            while match s.last() {
                Some(&l) => f(!(!(s.len() - 1) << shift), j) <= f(!(!(s.len() - 1) << shift), l),
                None => false,
            } {
                s.pop();
                sk.pop();
            }
            if s.len() < n {
                s.push(j);
                sk.push(jk);
            }
        }
        smawk1(
            n,
            shift,
            cols,
            f,
            smawk(n / 2, shift + 1, &s[..], f)
                .into_iter()
                .map(|h| unsafe { *sk.get_unchecked(h) }),
        )
    } else {
        smawk1(
            n,
            shift,
            cols.clone(),
            f,
            smawk(n / 2, shift + 1, cols, f).into_iter(),
        )
    }
}

fn smawk1<
    Col: Copy,
    Cols: ColsTrait<Col>,
    Key: Ord,
    F: Fn(usize, Col) -> Key,
    Iter: Iterator<Item = usize>,
>(
    n: usize,
    shift: u32,
    cols: Cols,
    f: F,
    iter: Iter,
) -> Vec<usize> {
    let mut out = Vec::with_capacity(n);
    let mut range = 0..0;
    for (i, k) in iter.enumerate() {
        range.end = k + 1;
        out.push(
            range
                .clone()
                .zip(cols.slice(range.clone()).iter())
                .min_by_key(|&(_, col)| f(!(!(2 * i) << shift), col))
                .unwrap()
                .0,
        );
        out.push(k);
        range.start = k;
    }
    if n % 2 == 1 {
        range.end = cols.len();
        out.push(
            range
                .clone()
                .zip(cols.slice(range.clone()).iter())
                .min_by_key(|&(_, col)| f(!(!(n - 1) << shift), col))
                .unwrap()
                .0,
        );
    }
    out
}

fn solve(k: usize, a: &[Cost]) -> Cost {
    if k >= a.len() {
        return 0;
    }
    let sa = once(Wrapping(0))
        .chain(a.iter().scan(Wrapping(0), |s, &x| {
            *s += Wrapping(x);
            Some(*s)
        }))
        .collect::<Vec<_>>();
    let c = |i: usize, j: usize| {
        let h = (i - j) / 2;
        unsafe {
            (sa.get_unchecked(i) - sa.get_unchecked(i - h) - sa.get_unchecked(j + h)
                + sa.get_unchecked(j))
                .0
        }
    };
    let cost1 = c(a.len(), 0);
    if k == 1 {
        return cost1;
    }
    let cost2 = (1..a.len()).map(|j| c(j, 0) + c(a.len(), j)).min().unwrap();
    let mut low = 0;
    let mut high = cost1 - cost2;
    let mut ret = INF;
    while low <= high {
        let penalty = low + (high - low) / 2;
        let mut out = vec![(INF, 0); a.len() + 1];
        out[0] = (0, 0);
        let mut begin = 0;
        let mut chunk = 1;
        loop {
            let r = min(a.len() + 1 - begin, 2 * chunk);
            let edge = begin + chunk;
            let (out0, out1) = out.split_at_mut(edge);
            let f = |i: usize, j: usize| {
                let h = (edge + i - j) / 2;
                let &(cost, count) = unsafe { out0.get_unchecked(j) };
                (
                    cost.saturating_add(
                        unsafe {
                            sa.get_unchecked(edge + i) - sa.get_unchecked(edge + i - h)
                                - sa.get_unchecked(j + h)
                                + sa.get_unchecked(j)
                        }.0 + penalty,
                    ),
                    count + 1,
                )
            };
            for ((i, j), o) in smawk(r - chunk, 0, begin..edge, &f)
                .into_iter()
                .enumerate()
                .zip(out1.iter_mut())
            {
                *o = min(f(i, begin + j), *o);
            }
            let x = unsafe { out1.get_unchecked(r - 1 - chunk) };
            if let Some(j) = (edge..begin + r - 1).find(|&j| &f(r - 1 - chunk, j) <= x) {
                begin = j;
                chunk = 1;
            } else if r == a.len() + 1 - begin {
                break;
            } else {
                chunk *= 2;
            }
        }
        let &(cost, count) = unsafe { out.get_unchecked(a.len()) };
        if count > k {
            low = penalty + 1;
        } else {
            ret = cost.wrapping_sub(k as Cost * penalty);
            if count == k {
                return ret;
            }
            high = penalty - 1;
        }
    }
    ret
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let k = lines.next().unwrap().unwrap().parse().unwrap();
    let a = lines
        .map(|s| s.unwrap().parse().unwrap())
        .collect::<Vec<_>>();
    let start = Instant::now();
    let cost = solve(k, &a);
    let time = start.elapsed();
    println!(
        "cost: {}\ntime: {}.{:09} sec",
        cost,
        time.as_secs(),
        time.subsec_nanos()
    );
}

Wypróbuj online!

Rdza , wynik testu wstępnego = 73

Kompiluj z rustc -O. Format wejściowy znajduje Księ w pierwszym wierszu, po nim wpisy A, jeden wpis w wierszu, wszystkie na standardowym wejściu.

use std::io::{self, BufRead};
use std::iter::once;
use std::num::Wrapping;
use std::time::Instant;
use std::u64;

type Cost = u64;
const INF: Cost = u64::MAX;

fn smawk<Col: Clone, Key: Ord, F: Clone + Fn(usize, &Col) -> Key>(
    n: usize,
    shift: u32,
    cols: &[Col],
    f: F,
) -> Vec<usize> {
    if n == 0 {
        Vec::new()
    } else if cols.len() > n {
        let mut s = Vec::with_capacity(n);
        let mut sk = Vec::with_capacity(n);
        for (jk, j) in cols.iter().enumerate() {
            while match s.last() {
                Some(l) => f(!(!(s.len() - 1) << shift), j) <= f(!(!(s.len() - 1) << shift), l),
                None => false,
            } {
                s.pop();
                sk.pop();
            }
            if s.len() < n {
                s.push(j.clone());
                sk.push(jk);
            }
        }
        smawk1(
            n,
            shift,
            cols,
            f.clone(),
            smawk(n / 2, shift + 1, &s, f)
                .into_iter()
                .map(|h| unsafe { *sk.get_unchecked(h) }),
        )
    } else {
        smawk1(
            n,
            shift,
            cols,
            f.clone(),
            smawk(n / 2, shift + 1, &cols, f).into_iter(),
        )
    }
}

fn smawk1<Col: Clone, Key: Ord, F: Clone + Fn(usize, &Col) -> Key, Iter: Iterator<Item = usize>>(
    n: usize,
    shift: u32,
    cols: &[Col],
    f: F,
    iter: Iter,
) -> Vec<usize> {
    let mut out = Vec::with_capacity(n);
    let mut range = 0..0;
    for (i, k) in iter.enumerate() {
        range.end = k + 1;
        out.push(
            range
                .clone()
                .zip(unsafe { cols.get_unchecked(range.clone()) })
                .min_by_key(|&(_, col)| f(!(!(2 * i) << shift), col))
                .unwrap()
                .0,
        );
        out.push(k);
        range.start = k;
    }
    if n % 2 == 1 {
        range.end = cols.len();
        out.push(
            range
                .clone()
                .zip(unsafe { cols.get_unchecked(range.clone()) })
                .min_by_key(|&(_, col)| f(!(!(n - 1) << shift), col))
                .unwrap()
                .0,
        );
    }
    out
}

fn solve(k: usize, a: &[Cost]) -> Cost {
    let mut cost = vec![INF; a.len() + 1 - k];
    let sa = once(Wrapping(0))
        .chain(a.iter().scan(Wrapping(0), |s, &x| {
            *s += Wrapping(x);
            Some(*s)
        }))
        .collect::<Vec<_>>();
    cost[0] = 0;
    let cols = (0..a.len() + 1 - k).collect::<Vec<_>>();
    for m in 0..k {
        cost = {
            let f = |i: usize, &j: &usize| {
                if i + 1 >= j {
                    let h = (i + 1 - j) / 2;
                    unsafe {
                        cost.get_unchecked(j).saturating_add(
                            (sa.get_unchecked(i + m + 1) - sa.get_unchecked(i + m + 1 - h)
                                - sa.get_unchecked(j + m + h)
                                + sa.get_unchecked(j + m))
                                .0,
                        )
                    }
                } else {
                    INF
                }
            };
            smawk(a.len() + 1 - k, 0, &cols, &f)
                .into_iter()
                .enumerate()
                .map(|(i, j)| f(i, &j))
                .collect()
        };
    }
    cost[a.len() - k]
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let k = lines.next().unwrap().unwrap().parse().unwrap();
    let a = lines
        .map(|s| s.unwrap().parse().unwrap())
        .collect::<Vec<_>>();
    let start = Instant::now();
    let cost = solve(k, &a);
    let time = start.elapsed();
    println!(
        "cost: {}\ntime: {}.{:09} sec",
        cost,
        time.as_secs(),
        time.subsec_nanos()
    );
}

Wypróbuj online!

C, wynik = 56

zawartość a.c:

typedef void V;typedef char C;typedef long L;typedef unsigned long U;
#define R return
#define W while
#define S static
#include<sys/syscall.h>
#define h1(f,x    )({L r;asm volatile("syscall":"=a"(r):"0"(SYS_##f),"D"(x)              :"cc","rcx","r11","memory");r;})
#define h3(f,x,y,z)({L r;asm volatile("syscall":"=a"(r):"0"(SYS_##f),"D"(x),"S"(y),"d"(z):"cc","rcx","r11","memory");r;})
#define read(a...) h3(read ,a)
#define write(a...)h3(write,a)
#define exit(a...) h1(exit ,a)
S V P(U x){C s[32],*p=s+32;*--p='\n';do{*--p='0'+x%10;x/=10;}W(x);write(1,p,s+32-p);}
S V mc(V*x,V*y,L n){C*p=x,*q=y;for(L i=0;i<n;i++)p[i]=q[i];}
#define min(x,y)({typeof(x)_x=(x),_y=(y);_x+(_y-_x)*(_y<_x);})
#define t(x,i,j)x[(i)*(n+n-(i)+1)/2+(j)] //triangle indexing
#define x(i,j)t(x,i,j)
#define y(i,j)t(y,i,j)
#define z(i,j)t(z,i,j)
#define N 4096 //max
L n;U ka[N+1],c[N],x[N*(N+1)/2],y[N*(N+1)/2],z[N*(N+1)/2];
V _start(){
 C s[1<<20];L r=0;U v=0;
 W(0<(r=read(0,s,sizeof(s))))for(L i=0;i<r;i++)if('0'<=s[i]&&s[i]<='9'){v=s[i]-'0'+10*v;}else{ka[n++]=v;v=0;}
 n--;U k=*ka,*a=ka+1;
 for(L i=n-1;i>=0;i--)for(L j=i-1;j>=0;j--)x(j,i)=x(j+1,i)-a[j]+a[i];
 for(L i=0;i<n;i++)for(L j=i+1;j<n;j++)y(i,j)=y(i,j-1)+a[j]-a[i];
 for(L i=n-1;i>=0;i--)for(L j=i+1;j<n;j++){
  U v=~0ul,*p=&x(i,i),*q=&y(i,j);for(L l=i;l<j;l++){v=min(v,*p+++*q);q+=n-l;} //min(v,x(i,l)+y(l,j));
  z(i,j)=v;}
 mc(c,z,8*n);
 for(L m=1;m<k;m++)for(L j=n-1;j>=m;j--){
  U v=~0ul,*p=&z(j,j);for(L i=j-1;i>=m-1;i--){v=min(v,c[i]+*p);p-=n-i;} //min(v,c[i]+z(i+1,j))
  c[j]=v;}
 P(c[n-1]);exit(0);}

skrypt powłoki, aby skompilować i przetestować powyższe:

#!/bin/bash -e
clang -O3 -nostdlib -ffreestanding -fno-unwind-tables -fno-unroll-loops -fomit-frame-pointer -oa a.c
strip -R.comment -R'.note*' a;stat -c'size:%s' a
t(){ r="$(echo "$1"|./a)";if [ "$r" != "$2" ];then echo "in:$1, expected:$2, actual:$r";fi;} #func tests
t '1 0 2 4 6 8' 12
t '3 0 1 10 11 20 21 22 30 32' 23
t '5 0 1 3 6 8 11 14' 3
t '6 0 1 3 6 8 14 15 18 29 30 38 41 45 46 49 58 66 72 83 84' 49
t '2 0 7 9' 2
for n in 1176 1351 1552 1782 2048;do #perf test
 echo "n:$n";a=0 inp="$((2*n/3))" RANDOM=1;for i in `seq $n`;do inp="$inp $a";a=$((a+=RANDOM%1000));done
 ulimit -t10 -v1048576;time ./a<<<"$inp"
done

n = 776 zajmuje 6,2 s, n = 891 trwa 12 s

n = 1176 zajmuje 5,9 s, n = 1351 zajmuje nieco ponad 10 s

n = 1351 zajmuje 8,7 s, n = 1552 zajmuje więcej niż 10 s (przy k = 2 * n / 3) na moim Intel(R) Core(TM) i3-2375M CPU @ 1.50GHz

C ++, wynik = 53

Rozwiązanie, które powiedziałem w komentarzu. O(n²×k). (teraz go usunąłem, ponieważ nie jest już potrzebny) Prawdopodobnie można go zmniejszyć do O(n×k).

Dane wejściowe są dość elastyczne, w pierwszym wierszu pierwsza liczba jest k, pozostałe liczby są elementami tablicy a, ale jeśli napotka jakieś nawiasy, przestaje czytać dane wejściowe. Tak więc wejście podobne K = 1, A = [0, 2, 4, 6, 8] : 12jest akceptowane.

// /codegolf/149029/build-an-electrical-grid

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <climits>

bool read(std::istream& str, int& x) {

    char ch;

    do {
        if (str >> x) return true;
        if (str.eof()) return false;
        str.clear(); // otherwise it's probably int parse error
    } while (str >> ch && ch != ']' && ch != ')' && ch != '}');
    // ignore 1 character, but treat any close parentheses as end of input

    // cannot read anything now
    return false;
}

int main() {
    int k; std::vector<int> a;

    //{ Read input
    std::string st; std::getline(std::cin, st);
    std::stringstream sst (st);

    read(sst, k);

    int x;
    while (read(sst, x)) a.push_back(x);
    //}

    std::vector<std::vector<int>> dp (a.size(), std::vector<int>(k));
    // dp[n][k] = min distance you can get for cities [n..a.size()-1]
    // and [k+1] power plants, and city [n] has a power plant.

    // sum_array[x] = sum of coordinates of cities [x..a.size()-1]
    std::vector<int> sum_array (a.size()+1);
    sum_array.back() = 0;
    for (int n = a.size(); n --> 0;)
        sum_array[n] = sum_array[n+1] + a[n];

    for (int n = a.size(); n --> 0;) {
        for (int k1 = k; k1 --> 0;) {
            if (k1 == 0) {
                int nWire = a.size() - 1 - n;
                dp[n][k1] = sum_array[n+1] - nWire * a[n];
            } else {
            // unindent because my screen width is limited

dp[n][k1] = INT_MAX / 2; // avoid stupid overflow error (in case of -ftrapv)

// let [n1] be the next position for a power plant
int first_connect_right = n; // < lengthy variable name kills screen width
// ^ lengthy comment kills screen width

for (int n1 = n + 1; n1 < (int)a.size(); ++n1) {

    while (a[first_connect_right]-a[n] < a[n1]-a[first_connect_right]) ++first_connect_right;

    int nRightWire = n1 - first_connect_right, nLeftWire = first_connect_right - 1 - n;
    dp[n][k1] = std::min(dp[n][k1],
        a[n1]*nRightWire-(sum_array[first_connect_right]-sum_array[n1]) +
        (sum_array[n+1]-sum_array[first_connect_right])-a[n]*nLeftWire +
        dp[n1][k1-1]
    );

}

            }

        }
    }

    int ans = INT_MAX;
    for (int n = a.size()+1-k; n --> 0;) {
        ans = std::min(ans, dp[n].back() + a[n]*n-sum_array[0]+sum_array[n]);
    }

    std::cout << ans << '\n';

    return 0;
}

Wypróbuj online!

Generuj losowe przypadki testowe. ( domyślnie podaj Ni opcjonalnie zasięg miasta 1000×N)

C #, wynik = 23

Jestem pewien, że to nie wygra tego wyzwania, chciałem tylko opublikować pierwszą (i bardzo podstawową) odpowiedź, aby zachęcić inne osoby do opublikowania swoich algorytmów i ulepszenia mojego. Ten kod musi zostać skompilowany jako projekt konsoli korzystający z pakietu Combinatorics firmy NuGet. Główna metoda zawiera niektóre wywołania Buildmetody do testowania proponowanych przypadków.

using Combinatorics.Collections;
using System;

namespace ElectricalGrid
{
    class Program
    {
        static void Main(string[] args)
        {
            if (Build(1, new long[] { 0, 2, 4, 6, 8 }) == 12)
                Console.WriteLine("OK");
            else
                Console.WriteLine("ERROR");
            if (Build(3, new long[] { 0, 1, 10, 11, 20, 21, 22, 30, 32 }) == 23)
                Console.WriteLine("OK");
            else
                Console.WriteLine("ERROR");
            if (Build(5, new long[] { 0, 1, 3, 6, 8, 11, 14 }) == 3)
                Console.WriteLine("OK");
            else
                Console.WriteLine("ERROR");
            if (Build(6, new long[] { 0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84 }) == 49)
                Console.WriteLine("OK");
            else
                Console.WriteLine("ERROR");

            Console.ReadKey();
        }

        static long Build(int k, long[] a)
        {
            var combs = new Combinations<long>(a, k);
            var totalDist = long.MaxValue;
            foreach (var c in combs)
            {
                long tempDist = 0;
                foreach (var i in a)
                {
                    var dist = long.MaxValue;
                    foreach (var e in c)
                    {
                        var t = Math.Abs(i - e);
                        if (t < dist) dist = t;
                    }
                    tempDist += dist;
                }
                if (tempDist < totalDist) totalDist = tempDist;
            }
            return totalDist;
        }
    }
}

Naprawdę proste wyjaśnienie: dla każdej kombinacji cz kelementami z aoblicz sumę odległości od każdego elementua z dokładnością do elementuc i przywrócić połączenie z najmniejszą łączną odległość.

Jednowierszowa wersja Buildmetody (prawdopodobnie wolniejsza niż oryginalna, rozszerzona wersja; należy do niej dodać odniesienie System.Linq):

static long Build(int k, long[] a)
{
    return new Combinations<long>(a, k).Min(c => a.Sum(i => c.Min(e => Math.Abs(i - e))));
}

C ++, wynik = 48

#include <stdio.h>
#include <queue>
#include <algorithm>
typedef long long ull;
typedef unsigned int uint;
uint A[1<<20];
ull S[1<<20];

double ky = 1;
struct point {
    ull dist;
    int n;
    inline point() {}
    inline point(ull dist, int n): dist(dist), n(n) {}
    inline double res() const{
        return dist + n * ky;
    }
    inline int operator<(const point& other) const {
        return res() < other.res();
    }
} V[1<<20];
inline ull f(int L, int R) {
    int m = L+R+1 >> 1;
    return (S[R]-S[m]) - A[m]*(R-m) +
           A[m]*(m-L) - (S[m]-S[L]);
}
int main() {
    int N, K, i, j, p;
    scanf ("%d%d", &N, &K);
    ull s = 0;
    for (i=1; i<=N; i++) {
        scanf ("%u", A+i);
        S[i] = s += A[i];
    }
    double kyL = 0, kyH = 1e99;
    point cL, cR;
    for (int step=0; step++<50; ky = std::min(ky*2, (kyL+kyH)*.5)) {
        for (i=1; i<=N; i++) {
            point tmp(f(0,i), 1);
            for (j=1; j<i; j++) {
            //printf("ky=%f [%d]=%d %I64d %f\n", ky, i, tmp.n, tmp.dist, tmp.res());
                point cmp = V[j];
                cmp.dist += f(j, i);
                cmp.n ++;
                if (cmp<tmp) tmp=cmp;
            }
            //printf("ky=%f [%d]=%d %I64d %f\n", ky, i, tmp.n, tmp.dist, tmp.res());
            V[i] = tmp;
        }
        if (V[N].n == K) {
_:          return! printf("%I64d", V[N].dist);
        }
        if (V[N].n > K) {
            kyL = ky;
            cL = V[N];
        } else {
            kyH = ky;
            cR = V[N];
        }
        //printf("ky=%f %d %I64d %f\n", ky, V[N].n, V[N].dist, V[N].res());
        //getch();
    }
    V[N].dist = (double)cL.dist / (cR.n-cL.n) * (K-cL.n) +
                (double)cR.dist / (cL.n-cR.n) * (K-cR.n) + .5;
    printf("%I64d", V[N].dist);
}

Dane wejściowe użycia: NKA [1] A [2] ... A [N]

Rubin , wynik = 23

->a,l{d=l.map{|x|l.map{|y|(x-y).abs}};[*0...l.size].combination(a).map{|r|r.map{|w|d[w]}.transpose.sum{|r|r.min}}.min}

Wypróbuj online!

Nie sądzę, że wygra, ale chciałem spróbować.

JavaScript (ES6) (Node.js) , wynik = 10

Nowy algorytm wyjaśni, czy tym razem faktycznie działa.

const {performance} = require('perf_hooks');

class Connection{
    constructor(left,index,length,right){
        if(typeof right === 'undefined'){
            this._distance = 0;
        } else {
            this._distance = typeof left === 'undefined' ? 0 :
                    Math.abs(right - left);
        }
        var half = Math.floor(length/2);
        if(length % 2 < 1){
            this._magnitude = half - Math.abs(index - half + 1);
        } else {
            var temp = index - half;
            this._magnitude = half - Math.abs(temp >= 0 ?temp:temp + 1);
        }
        this._value = this.distance * this.magnitude;
    }

    get distance(){return this._distance;};
    get magnitude(){return this._magnitude;};
    set magnitude(value){
        this._magnitude = value;
        this._value = this.distance * this.magnitude;
    };
    valueOf(){return this._value};
}

class Group{
	constructor(...connections){
        this._connections = connections;
		
		this._max = Math.max(...connections); //uses the ValueOf to get the highest Distance to the Left
	}
	get connections(){return this._connections;};
	get max(){return this._max;};
    cutLeft(index){

            for(let i=1,j=index-1;;i++){
                
                if(typeof this.connections[j] === 'undefined' || this.connections[j].magnitude <= i){
                    break;
                }
                this.connections[j].magnitude = i;
                j--;
            }

    }

    cutRight(index){

            for(let i=0,j=index;;i++){
                
                if(typeof this.connections[j] === 'undefined' || this.connections[j].magnitude <= i){
                    break;
                }
                this.connections[j].magnitude = i;
                j++;
            }

    }

    static of(...connections){
        return new Group(...connections.map((c,i)=>new Connection(c.distance,i,connections.length)));
    }

	split(){
        var index = this.connections.findIndex(c=>c.valueOf() == this.max);
        if(index < 0){
            return;
        }
        var length = this.connections.length;
        var magnitude = this.connections[index].magnitude;

        this.cutLeft(index);
        this.cutRight(index);
        this._max = Math.max(...this.connections);
	}

    center(){
        if(typeof this._center === 'undefined'){
            this._center = this.connections.reduce((a,b)=>a==0?b.valueOf():a.valueOf()+b.valueOf(),0);
        }
        return this._center;
    }

    valueOf(){return this._max;};
    toString(){
        var index = this.connections.findIndex(c=>c.valueOf() == this.max);
        var value = this.connections[index].magnitude;
        var ret = '';
        for(let i = 0;i<value;i++){
            ret += this.connections.map(c=>{return (i<c.magnitude)?c.distance:' ';}).reduce((a,b)=>a==''?b:a+'-'+b,'') + '\n';
        }
        return ret;
    };
}

function crunch(plants, cities){
	var found = [];
    var size = cities.length;
    cities = cities.map((city,i,arr)=> new Connection(city,i,size,arr[i+1])).slice(0,cities.length-1);
    var group = new Group(...cities);
    for(;plants>1;plants--){
    group.split();
    }
    console.log(`Wire Length Needed: ${group.center()}`);
}

function biggestGroup(groups){
	return groups.find(g => g[g.length-1].orig - g[0].orig);
}

function* range (start, end, limit) {
    while (start < end || typeof limit !== 'undefined' && limit-- > 0) {
        yield start
        start += 1 + Math.floor(Math.random()*100);
    }
}

function* cities (score){
	let n = Math.floor(Math.pow(2,score/5));
	var start = 0;
	while (n-- > 0 && start <= (1000 * n)) {
		yield start;
        start += 1 + Math.floor(Math.random()*100);
    }
}


if(typeof process.argv[3] === 'undefined'){
    crunch(1,[0, 2, 4, 6, 8]);
    console.log("Correct Answer: 12");
    crunch(3,[0, 1, 10, 11, 20, 21, 22, 30, 32]);
    console.log("Correct Answer: 23");
    crunch(5,[0, 1, 3, 6, 8, 11, 14]);
    console.log("Correct Answer: 3");
    crunch(6,[0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84]);
    console.log("Correct Answer: 49");
    crunch(2, [0, 21, 31, 45, 49, 54]);
    console.log("Correct Answer: 40");
    crunch(2, [0, 4, 7, 9, 10]);
    console.log("Correct Answer: 7");
    crunch(2, [0, 1, 3, 4, 9]);
    console.log("Correct Answer: 6");
    
    var max = 0;
    var min = Number.POSITIVE_INFINITY;
    var avg = [];
    
    var score = typeof process.argv[2] === 'undefined' ? 60 : process.argv[2];

    for(j = 0; j<10; j++){
        var arr = []; for(let i of cities(score)) arr.push(i);
        var plants = Math.floor(1 + Math.random() * arr.length);
        console.log(`Running: Test:${j} Plants: ${plants}, Cities ${arr.length}, Score: ${score}`);
        // console.log(`City Array: [${arr}]`);
        var t0 = performance.now();
        crunch(plants,arr);
        var t1 = performance.now();
        time = (t1-t0)/1000;
        console.log(`Time Taken = ${time} seconds`);
        avg.push(time);
        max = Math.max(time,max);
        min = Math.min(time,min);
    }
    console.log(`Bench: ${avg.reduce((a,b)=>a+b,0)/avg.length} Max: ${max} Min: ${min} Total: ${avg.reduce((a,b)=>a+b,0)}`);
} else {
    var plants = process.argv[2];
    var arr = process.argv.slice(3);
    console.log(`Running: Plants: ${plants}, Cities ${arr.length}`);
    var t0 = performance.now();
    crunch(plants,arr);
    var t1 = performance.now();
    time = (t1-t0)/1000;
    console.log(`Time Taken = ${time} seconds`);
}

Wypróbuj online!

Uruchom taki sam sposób jak drugi.

JavaScript (ES6) (Node.js) , wynik testu wstępnego = 12

Zarys algorytmu:

Najpierw program mapuje dane do klasy miasta, która mapuje kilka punktów danych:

• miasto - absolutna odległość miasta
• left - odległość najbliższego miasta po lewej stronie
• prawo - odległość od najbliższego miasta po prawej stronie
• index - (przestarzały) indeks w oryginalnej tablicy miasta

tablica jest następnie wrzucana do klasy Group, która ma następujące cechy:

• miasta - tablica miast
• dist - odległość obejmująca grupę
• max - największe lewe połączenie w grupie
• rozdzielać()
  • zwraca tablicę zawierającą podgrupy podzielone wzdłuż największego połączenia połączonego z centrum miasta w grupie
  • jeśli są 2 węzły środkowe (grupa o parzystej długości), wybiera spośród tych 3 połączeń
  • (* uwaga *: spowoduje to usunięcie grup z mniej niż dwoma miastami)
• Centrum()
  • zwraca najlepszą wartość drutu dla grupy
  • pracując nad rozwiązaniem pomijającym iterację po każdym mieście pozostawionym na tym etapie
  • teraz z mapowaniem o 50% mniej

Teraz algorytm dzieli grupy, o ile ma 2 lub więcej elektrowni do umieszczenia.

Na koniec mapuje grupy do centrów i sumuje je wszystkie.

Jak uruchomić:

Uruchom za pomocą Node.js (wersja 9.0.0 została użyta do stworzenia)

uruchomienie programu przy użyciu wygenerowanych przypadków testowych dla wyniku 70:

node program.js 70

uruchomienie programu z wykorzystaniem 1 elektrowni i miast [0,3,5]:

node program.js 1 0 3 5

Kod:

const {performance} = require('perf_hooks');

class City{
	constructor(city, left, right, i){
		this._city = city;
		this._index = i;
		this._left = typeof left === 'undefined' ? 0 : city - left;
		this._right = typeof right === 'undefined' ? 0 : right - city;
	}

	get city(){return this._city;};
	get index(){return this._index;};
	get left(){return this._left;};
    get right(){return this._right;};
    set left(left){this._left = left};
    set right(right){this._right = right};

	valueOf(){return this._left;};
}

class Group{
	constructor(...cities){
        this._cities = cities;
        // console.log(cities.map(a=>a.city).reduce((a,b)=>a===''?a+(b<10?' '+b:b):a+'-'+(b<10?' '+b:b),""));
        // console.log(cities.map(a=>a.left).reduce((a,b)=>a===''?a+(b<10?' '+b:b):a+'-'+(b<10?' '+b:b),""));
        // console.log(cities.map(a=>a.right).reduce((a,b)=>a===''?a+(b<10?' '+b:b):a+'-'+(b<10?' '+b:b),""));
        // console.log("+==+==+==+==+==+==+==+==+==+==+==+==")
		this._dist = cities[cities.length-1].city - cities[0].city;
		this._max = Math.max(...cities); //uses the ValueOf to get the highest Distance to the Left
	}

	get dist(){return this._dist;};
	get cities(){return this._cities;};
	get max(){return this._max;};

	split(){
        //var index = this.cities.findIndex(city=>city.left == this.max);
        //this.cities[index].left = 0;
        // console.log(`Slicing-${this.max}-${index}------`)
        var centerIndex = this.cities.length / 2;
        var splitIndex = Math.floor(centerIndex);
        if(centerIndex%1 > 0){
            var center = this.cities[splitIndex];
            if(center.right > center.left){

                splitIndex++;
            }
        } else {
            var right = this.cities[splitIndex];
            var left = this.cities[splitIndex-1];
            if(left.left > Math.max(right.right,right.left)){
               
                splitIndex--;
            } else if(right.right > Math.max(left.left,left.right)){
                
                splitIndex++;
            }
        }
        // console.log(splitIndex);
        this.cities[splitIndex].left = 0;
        this.cities[splitIndex-1].right = 0;
        var leftCities = [...this.cities.slice(0,splitIndex)];
        var rightCities = [...this.cities.slice(splitIndex)];

        // var center = this.cities[]

        if(leftCities.length <= 1){
            if(rightCities.length <= 1){
                return [];
            }
            return [new Group(...rightCities)]
        }
        if(rightCities.length <= 1){
            return [new Group(...leftCities)];
        }
        return [new Group(...leftCities), new Group(...rightCities)];
	}

    center(){
        if(typeof this._center === 'undefined'){
            if(this.cities.length == 1){
                return [0];
            }
            if(this.cities.length == 2){
                return this.cities[1].left;
            }
            var index = Math.floor(this.cities.length/2);
            this._center = this.cities.reduce((a,b)=> {
                // console.log(`${a} + (${b.city} - ${city.city})`);
                return a + Math.abs(b.city - this.cities[index].city);
            },0);
            // console.log(this._center);
        }
        
        return this._center;
    }

	valueOf(){return this._max;};
}

function crunch(plants, cities){
	var found = [];
    var size = cities.length;
    cities = cities.map((city,i,arr)=> new City(city,arr[i-1],arr[i+1],i));
	var groups = [new Group(...cities)];

	// console.log(groups);
    for(;plants>1;plants--){
        var mapped = groups.map(g=>g.center()-g.max);
        var largest = Math.max(...groups);
        // console.log('Largest:',largest)
        // console.log(...mapped);
		var index = groups.findIndex((g,i)=> mapped[i] == g.center() - g.max && g.max == largest);
		// console.log(index);
        groups = index == 0 ? 
            [...groups[index].split(),...groups.slice(index+1)]:
            [...groups.slice(0,index),...groups[index].split(),...groups.slice(index+1)];
    }
    // console.log(`=Cities=${size}================`);
    // console.log(groups);
    size = groups.map(g=>g.cities.length).reduce((a,b)=>a+b,0);
    
    // console.log(`=Cities=${size}================`);
    var wires = groups.map(g=>g.center());
    
    // console.log(...wires);
    // console.log(`=Cities=${size}================`);
    console.log(`Wire Length Needed: ${wires.reduce((a,b)=>a + b,0)}`);
}

function biggestGroup(groups){
	return groups.find(g => g[g.length-1].orig - g[0].orig);
}

function* range (start, end, limit) {
    while (start < end || typeof limit !== 'undefined' && limit-- > 0) {
        yield start
        start += 1 + Math.floor(Math.random()*100);
    }
}

function* cities (score){
	let n = Math.floor(Math.pow(2,score/5));
	var start = 0;
	while (n-- > 0 && start <= (1000 * n)) {
		yield start;
        start += 1 + Math.floor(Math.random()*100);
    }
}

if(typeof process.argv[3] === 'undefined'){
    crunch(1,[0, 2, 4, 6, 8]);
    console.log("Correct Answer: 12");
    crunch(3,[0, 1, 10, 11, 20, 21, 22, 30, 32]);
    console.log("Correct Answer: 23");
    crunch(5,[0, 1, 3, 6, 8, 11, 14]);
    console.log("Correct Answer: 3");
    crunch(6,[0, 1, 3, 6, 8, 14, 15, 18, 29, 30, 38, 41, 45, 46, 49, 58, 66, 72, 83, 84]);
    console.log("Correct Answer: 49");
    crunch(2, [0, 21, 31, 45, 49, 54]);
    console.log("Correct Answer: 40");
    crunch(2, [0, 4, 7, 9, 10]);
    console.log("Correct Answer: 7");
    
    var max = 0;
    var min = Number.POSITIVE_INFINITY;
    var avg = [];
    
    var score = typeof process.argv[2] === 'undefined' ? 60 : process.argv[2];

    for(j = 0; j<10; j++){
        var arr = []; for(let i of cities(score)) arr.push(i);
        var plants = Math.floor(1 + Math.random() * arr.length);
        console.log(`Running: Test:${j} Plants: ${plants}, Cities ${arr.length}, Score: ${score}`);
        var t0 = performance.now();
        crunch(plants,arr);
        var t1 = performance.now();
        time = (t1-t0)/1000;
        console.log(`Time Taken = ${time} seconds`);
        avg.push(time);
        max = Math.max(time,max);
        min = Math.min(time,min);
    }
    console.log(`Bench: ${avg.reduce((a,b)=>a+b,0)/avg.length} Max: ${max} Min: ${min} Total: ${avg.reduce((a,b)=>a+b,0)}`);
} else {
    var plants = process.argv[2];
    var arr = process.argv.slice(3);
    console.log(`Running: Plants: ${plants}, Cities ${arr.length}`);
    var t0 = performance.now();
    crunch(plants,arr);
    var t1 = performance.now();
    time = (t1-t0)/1000;
    console.log(`Time Taken = ${time} seconds`);
}

Wypróbuj online!

Wyczyszczę skomentowany kod w ciągu najbliższych kilku dni, ponieważ wciąż nad tym pracuję, chciałem tylko sprawdzić, czy to przechodzi więcej niż tylko małe skrzynki.

C (niekonkurencyjny, wynik testu wstępnego = 76)

Jest to próba przetłumaczenia drugiego rozwiązania Rust @ AndersKaseorga na język C.

typedef void V;typedef char C;typedef long L;
#define R return
#define W while
#define S static
#include<sys/syscall.h>
#define exit(x)     ({L r;asm volatile("syscall":"=a"(r):"0"(SYS_exit ),"D"(x)              :"cc","rcx","r11","memory");r;})
#define read(x,y,z) ({L r;asm volatile("syscall":"=a"(r):"0"(SYS_read ),"D"(x),"S"(y),"d"(z):"cc","rcx","r11","memory");r;})
#define write(x,y,z)({L r;asm volatile("syscall":"=a"(r):"0"(SYS_write),"D"(x),"S"(y),"d"(z):"cc","rcx","r11","memory");r;})
S V P(L x){C s[32],*p=s+32;*--p='\n';do{*--p='0'+x%10;x/=10;}W(x);write(1,p,s+32-p);}
#define N 0x100000 //max
#define INF (-1ul>>1)
S L cost[N],nk1,*am; //nk1:n-k+1, am:input's partial sums offset with the current "m" in _start()
S L f(L i,L j){if(i+1>=j&&cost[j]!=INF){L h=(i-j+1)>>1;R cost[j]+am[i+1]-am[j+h]-am[i-h+1]+am[j];}else{R INF;}}
S V smawk(L sh,L*c,L nc,L*r){ //sh:shift,c:cols,r:result
 L n=nk1>>sh;if(!n)R;
 L m=n>>1,u[m];
 if(n<nc){
  L ns=0,s[nc],sk[nc],*skp=sk;
  for(L jk=0;jk<nc;jk++){
   L j=c[jk];W(ns>0&&f(~(~(ns-1)<<sh),j)<=f(~(~(ns-1)<<sh),s[ns-1])){--ns;--skp;}
   if(ns<n){s[ns++]=j;*skp++=jk;}
  }
  smawk(sh+1,s,ns,u);for(L i=0;i<m;i++)u[i]=sk[u[i]];
 }else{
  smawk(sh+1,c,nc,u);
 }
 L l=0,ish=(1<<sh)-1,dsh=1<<(sh+1);
 for(L i=0;i<m;i++){
  L k=u[i],bj=l,bc=f(ish,c[l]);
  for(L j=l+1;j<=k;j++){L h=f(ish,c[j]);if(h<bc){bc=h;bj=j;}}
  *r++=bj;*r++=k;l=k;ish+=dsh;
 }
 if(n&1){
  L nsh=~(~(n-1)<<sh),bj=l,bc=f(nsh,c[l]);
  for(L j=l+1;j<nc;j++){L h=f(nsh,c[j]);if(h<bc){bc=h;bj=j;}}
  *r=bj;
 }
}
S L inp(L*a){
 L n=-1,l,v=0;C b[1<<20];
 W(0<(l=read(0,b,sizeof(b))))for(L i=0;i<l;i++)if('0'<=b[i]&&b[i]<='9'){v=b[i]-'0'+10*v;}else{a[++n]=v;v=0;}
 R n;
}
V _start(){
 S L a[N];L n=inp(a),k=*a,s=0;for(L i=0;i<n;i++){a[i]=s;s+=a[i+1];}a[n]=s;
 *cost=0;for(L i=1,l=n+1-k;i<l;i++)cost[i]=INF;
 S L c[N];L nc=n+1-k;for(L i=0;i<nc;i++)c[i]=i;
 S L r[N];nk1=n-k+1;for(L m=0;m<k;m++){am=a+m;smawk(0,c,nc,r);for(L i=n-k;i>=0;i--)cost[i]=f(i,r[i]);}
 P(cost[n-k]);exit(0);
}

Połącz z:

#!/bin/bash -e
clang -O3 -nostdlib -ffreestanding -fno-unwind-tables -fno-unroll-loops -fomit-frame-pointer -oa a.c
strip -R.comment -R'.note*' a

Czyste , wynik = 65

module main
import StdEnv, System.IO

parseArgs :: *World -> ((Int, {#Int}), *World)
parseArgs world
    # (args, world)
        = nextArgs [] world
    # args
        = reverse args
    # (k, a)
        = (hd args, tl args)
    = ((toInt k, {toInt n \\ n <- a}), world)
where
    nextArgs :: [String] *World -> ([String], *World)
    nextArgs args world
        # (arg, world)
            = evalIO getLine world
        | arg == ""
            = (args, world)
        = nextArgs [arg:args] world

minimalWeight :: Int !{#Int} -> Int
minimalWeight k a
    # count
        = size a
    # touches
        = createArray ((count - k + 3) / 2 * k) 0
    = treeWalk k count a [(0, 0, 0, 0)] touches
where
    treeWalk :: Int !Int {#Int} ![(!Int, !Int, Int, Int)] *{Int} -> Int
    treeWalk k verticies a [(weight, vertex, degree, requires) : nodes] touches
        | vertex >= verticies
            = weight
        | requires >= k
            = treeWalk k verticies a nodes touches
        # index
            = degree * k + requires
        | (select touches index) > vertex
            = treeWalk k verticies a nodes touches
        # (next, pivot)
            = (vertex + 1 + degree, verticies + requires)
        # (nodes, touches)
            = (orderedPrepend (weight, next, 0, requires + 1) nodes, update touches index (vertex + 1))
        | pivot >= k + next
            # (weight, vertex)
                = (weight + (select a next) - (select a vertex), vertex + 1)
            # nodes
                = orderedPrepend (weight, next + 1, 0, requires + 1) nodes
            | pivot == k + next
                = treeWalk k verticies a nodes touches
            # weight
                = weight + (select a (next + 1)) - (select a vertex)
            # nodes
                = orderedPrepend (weight, vertex, degree + 1, requires) nodes
            = treeWalk k verticies a nodes touches
        = treeWalk k verticies a nodes touches
    where
        orderedPrepend :: (!Int, Int, Int, Int) ![(!Int, Int, Int, Int)] -> [(Int, Int, Int, Int)]
        orderedPrepend a []
            = [a]
        orderedPrepend a [b : b_]
            # (x, _, _, _)
                = a
            # (y, _, _, _)
                = b
            | y > x
                = [a, b : b_]
            = [b : orderedPrepend a b_]

Start world
    # ((k, a), world)
        = parseArgs world
    = minimalWeight k a

Połącz z:
clm -h 1024M -gci 32M -gcf 32 -s 32M -t -nci -ou -fusion -dynamics -IL Platform main

Pobiera K, a następnie każdy element Ajako argumenty wiersza polecenia.