Baue ein elektrisches Netz

22

Die Herausforderung

Es gibt N Städte, die in einer geraden Linie ausgerichtet sind. Die i-te Stadt liegt A[i]Kilometer rechts vom Ursprung. Keine zwei Städte werden am selben Ort sein.

Sie werden mit einigen Kraftwerken ein Stromnetz bauen. Kraftwerke müssen in einer Stadt gebaut werden. Sie dürfen jedoch nur K(<N) Kraftwerke bauen, daher gibt es einige Städte ohne Kraftwerke. Für jede Stadt ohne Kraftwerke müssen Sie ein Kabel zwischen ihr und der nächstgelegenen Stadt mit einem Kraftwerk bauen .

Wenn sich beispielsweise drei Städte in befinden 0, 1, 2und nur die Stadt in 0ein Kraftwerk hat, müssen Sie zwei Kabel bauen, eines von 2bis 0(2 km) und das andere von 1bis0 Gesamtlänge von 3 (1 km) bauen .

Gegeben Kund Positionen der Städte (A ) sollten Sie die minimalen Kabelkilometer berechnen, die Sie zum Aufbau des Netzes benötigen.

Beispiel Testfälle

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

Spezifikationen

  • Sie sollten eine Funktion oder ein Programm implementieren, das eine positive Ganzzahl Kund eine Liste von Ganzzahlen Ain beliebiger Form akzeptiert und eine Ganzzahl ausgibt / zurückgibt, die die Antwort darstellt.

  • A wird in aufsteigender Reihenfolge sortiert, und alle Elemente sind nicht negative ganze Zahlen.

  • A[0] = 0und A[N-1]wird nicht mehr als 1000N sein.

  • Beachten Sie, dass die Ausgabe eine Größe von 1000 N 2 hat. In größeren Fällen benötigen Sie in einigen Sprachen möglicherweise 64-Bit-Ganzzahlen.

  • Multithreading ist nicht zulässig (ich werde die Affinität Ihres Programms bei der Beurteilung auf nur 1 Kern setzen). Compiler-Optimierungen (wie -O2in C) sind zulässig.

Wertung

  • Ich werde Ihren Code auf meinem Computer (Ubuntu 16.04 mit Intel i7-3770S Prozessor) mit unterschiedlicher Größe von Testfällen zeitlich festlegen. Insbesondere werde ich einige Testfälle mit N = floor (2 x / 5 ) generieren, wobei x eine positive ganze Zahl ist.
    Ihre Punktzahl ist der x-Wert des kleinsten Testfalls, für den Ihr Programm mehr als 10 Sekunden oder 1 GB Speicher benötigt, oder Sie geben keine korrekte Antwort.

    • Die Antwort mit der höchsten Punktzahl gewinnt. Wenn zwei Antworten die gleiche Punktzahl erhalten, gewinnt die frühere Antwort.
  • Alle Programme werden nach denselben Testfällen beurteilt.

  • Fühlen Sie sich frei, Ihre eigenen Scorings zu posten. Erklärungen Ihres Algorithmus werden angeregt.

Bonus

Dies ist mein C ++ - Programm, es erhält 108 Punkte . Sie können den SHA-256-Digest überprüfen9a87fa183bad1e3a83d2df326682598796a216b3a4262c32f71dfb06df12935d anhand des gesamten Codesegments (ohne Fußzeile) im Link .

Der Algorithmus kombiniert die binäre Suche und die Knuth-Optimierung, um die richtige Strafe für jede Pflanze zu finden und die gewünschte Zahl zu erhalten. Die Komplexität ist O (N log N log A [N-1]). Ich war überrascht, dass das Programm eine höhere Punktzahl als die Lösung O (N log A [N − 1]) von Anders Kaseorg erhielt . Dies liegt wahrscheinlich daran, dass der Log-Fall in Knuths Optimierung normalerweise nicht auftritt.

Beachten Sie, dass diese Herausforderung mit IOI 2000 Post Office identisch ist . Die ursprünglichen Bedingungen sind jedoch N <= 300 und K <= 30.

Colera Su
quelle
2^^(x/5): was ist die Bedeutung ? Können Sie nur eine Obergrenze für N angeben?
Setop
1
@Setop Wenn Ihr Programm zum Beispiel N=21( = floor(2^(22/5)) )in 10 Sekunden fertig ist , aber nicht fertig ist N=24( = floor(2^(23/5)) ), ist 23 die Punktzahl. Ich habe keine Obergrenze verwendet, da die Unterschiede zwischen den verschiedenen Algorithmen zu groß sind. Wenn ich N Zum Beispiel setzen <= 40, wird es kaum einen Unterschied zwischen O(KN^2)und O(KN^3), aber O(2^N)nicht einmal in vernünftiger Zeit zu beenden.
Colera So
5
Das ist so ziemlich das, was ich beruflich mache, und ich kann Ihnen so viel sagen: So gestalten wir das Stromnetz nicht!
Stewie Griffin
3
Zufallstestgenerator
user202729
3
Exzellente Herausforderung, exzellentes Punktesystem. Gut gemacht!
isaacg

Antworten:

9

Rost , Score = 104

Dies ist eine Implementierung des von Grønlund et al. (2017) am Ende von §3.3.1, obwohl ich einer langen Zitierkette folgen und einige fehlende Details eintragen musste. Es läuft in O ( N log A [ N - 1]).

Kompilieren mit rustc -O. Das Eingabeformat befindet sich Kin der ersten Zeile, gefolgt von den Einträgen von Aeinem Eintrag pro Zeile, alle auf stdin.

(Hinweis: Ich übermittle dies eine Stunde nach Ablauf der Prämienfrist, erwarte jedoch, dass die letzte Version, die ich vor Ablauf der Prämienfrist eingereicht habe und die in O ( N log N log A [ N - 1]) abgelaufen ist, etwa 94 Punkte erzielt .)

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()
    );
}

Probieren Sie es online!

Rost , Pretest Score = 73

Kompilieren mit rustc -O. Das Eingabeformat befindet sich Kin der ersten Zeile, gefolgt von den Einträgen von Aeinem Eintrag pro Zeile, alle auf stdin.

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()
    );
}

Probieren Sie es online!

Anders Kaseorg
quelle
Sie haben eine Pretest-Punktzahl 61, aber das liegt am Überlauf von u32. Vielleicht können Sie auf 64-Bit-Integer-Typ ändern?
Colera So
@ColeraSu kann es besser tun , wenn ich nur ändern type Cost = u32zu type Cost = u64?
Anders Kaseorg
1
Wow, ich hatte noch nie an einen SMAWK-Algorithmus gedacht. Gute Arbeit, hast du 73.
Colera So
2
@ngn Was hast du gegen Rust? :-(
Anders Kaseorg
1
Herzlichen Glückwunsch zum Gewinn der ersten Prämie!
Urous
5

C, Score = 56

Inhalt von 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);}

Shell-Skript zum Kompilieren und Testen des oben genannten:

#!/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 dauert 6,2 s, n = 891 dauert 12 s

n = 1176 dauert 5,9 s, n = 1351 dauert etwas mehr als 10 s

n = 1351 dauert 8,7 s, n = 1552 dauert mehr als 10 s (mit k = 2 * n / 3) auf meiner Intel(R) Core(TM) i3-2375M CPU @ 1.50GHz

ngn
quelle
2
Ich nehme an, das ist kein Code-Golf?
user202729
@ user202729 So schreibe ich normalerweise C-Code im Inkunabel- Stil.
2.
@ngn Ich nehme an, du verwendest dann normalerweise auch keine Syntaxhervorhebung?
Jonathan Frech
@ JonathanFrech mache ich eigentlich. Ich habe meine angepasst syntax/c.vim.
3.
2
@cole Das ist nur normales C, nur dichter. Wenn Sie mit der Sprache vertraut sind, sollten Sie sie ohne große Schwierigkeiten lesen können, wenn auch um ein Vielfaches langsamer, da eine Zeile Informationen enthält, die die meisten C-Programmierer über 5 bis 10 Zeilen verteilen würden (was für eine Verschwendung!). Ich schrieb Kommentare nur für die schwierigsten Teile.
7.
3

C ++, Score = 53

Die Lösung hatte ich im Kommentar gesagt. O(n²×k). (jetzt habe ich es gelöscht weil es nicht mehr nötig ist) Kann wohl auf reduziert werden O(n×k).

Die Eingabe ist ziemlich flexibel. In der ersten Zeile ist die erste Zahl k, die anderen Zahlen sind Elemente des Arrays a. Wenn sie jedoch in engen Klammern stehen, werden die Eingaben nicht mehr gelesen. Eingaben wie werden K = 1, A = [0, 2, 4, 6, 8] : 12also akzeptiert.

// /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;
}

Probieren Sie es online!

Generieren Sie zufällige Testfälle. (Eingabe Nund optional Stadtbereich, 1000×Nstandardmäßig)

user202729
quelle
Wenn es in der Lage ist, einen größeren Testfall zu lösen, ändere ich das notwendige ints in int64_ts.
user202729
dp [runned_n, runned_k] = min {dp [runned_n-x, runned_k] + f [x, n]}, daher ist die direkte dynamische Programmierung O (n ^ 2 * k). Müssen Sie möglicherweise den Weg vollständig ändern, um die Komplexität zu reduzieren?
14 m²,
@ l4m2 Mach den Algorithmus nicht kaputt! (
Nun
Tut mir leid, aber ich weiß nicht so recht, ob "Verwöhnen" "Wegwerfen" oder "Stehlen" oder beides bedeutet. Kann beides bedeuten. Ich kenne dieses Wort nicht ganz. (Ich habe auch gedacht, Kopfgeld bedeutet gebunden)
14m2
2
Der Zufallstestgenerator erzwingt nicht A [0] = 0, wie in der Frage angegeben.
Anders Kaseorg
2

C #, Score = 23

Ich bin mir sicher, dass dies diese Herausforderung nicht gewinnen wird. Ich wollte lediglich eine erste (und sehr einfache) Antwort veröffentlichen, um andere zu ermutigen, ihre Algorithmen zu veröffentlichen und meine zu verbessern. Dieser Code muss als Konsolenprojekt kompiliert werden, das das Combinatorics-Paket von NuGet verwendet. Die Hauptmethode enthält einige Aufrufe der BuildMethode zum Testen der vorgeschlagenen Fälle.

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;
        }
    }
}

Wirklich einfache Erklärung: Berechnen Sie für jede Kombination cvon kElementen aus adie Summe der Abstände von jedem Element azum nächsten Element in cund geben Sie die Kombination mit dem geringsten Gesamtabstand zurück.

Einzeilige Version der BuildMethode (wahrscheinlich langsamer als die ursprüngliche, erweiterte Version; dazu muss ein Verweis hinzugefügt werden 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))));
}
Charlie
quelle
2

C ++, Score = 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);
}

Gebrauchseingabe: NKA [1] A [2] ... A [N]

l4m2
quelle
2
Wenn Sie das Limit stepauf 70 erhöhen, beträgt Ihr Pretest-Score 60.
Colera So
2

Ruby , Score = 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}

Probieren Sie es online!

Ich glaube nicht, dass es gewinnen wird, aber ich wollte es versuchen.

GB
quelle
2

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

Neuer Algorithmus, wird erklären, ob er diesmal tatsächlich funktioniert.

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`);
}

Probieren Sie es online!

Führe den gleichen Weg wie den anderen.

JavaScript (ES6) (Node.js) , Pretest-Score = 12

Umriss des Algorithmus:

Das Programm ordnet die Daten zuerst der Stadtklasse zu, die einige Datenpunkte ordnet:

  • Stadt - die absolute Entfernung der Stadt
  • left - die Entfernung der nächstgelegenen Stadt links
  • rechts - Entfernung der nächstgelegenen Stadt rechts
  • index - (veralteter) Index im ursprünglichen Stadtarray

Das Array wird dann in die Group-Klasse geworfen, die Folgendes enthält:

  • Städte - das Stadtarray
  • dist - die Entfernung über die Gruppe
  • max - die größte linke Verbindung in der Gruppe
  • Teilt()
    • Gibt ein Array zurück, das Untergruppen enthält, die entlang der größten Verbindung aufgeteilt sind, die mit der Stadtmitte in der Gruppe verbunden ist
    • Wenn es 2 Mittelknoten gibt (eine Gruppe mit gerader Länge), wählt sie aus diesen 3 Verbindungen aus
    • (* Anmerkung *: Dadurch werden alle Gruppen mit weniger als zwei Städten gelöscht.)
  • Center()
    • Gibt den besten Drahtwert für die Gruppe zurück
    • Arbeiten an einer Lösung, um zu überspringen, welche Städte für diesen Schritt übrig sind
    • jetzt mit 50% weniger Mapping

Nun teilt der Algorithmus die Gruppen so lange auf, wie zwei oder mehr Kraftwerke zu platzieren sind.

Schließlich ordnet es die Gruppen den Zentren zu und fasst sie alle zusammen.

Wie läuft man:

Mit Node.js ausführen (v9.2.0 wurde für die Erstellung verwendet)

Ausführen des Programms mit generierten Testfällen für Punktzahl 70:

node program.js 70

Ausführen des Programms mit 1 Kraftwerk und Städten [0,3,5]:

node program.js 1 0 3 5

Code:

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`);
}

Probieren Sie es online!

Ich werde den auskommentierten Code in den nächsten Tagen bereinigen, da ich immer noch daran arbeite. Ich wollte nur sehen, ob dies mehr als nur die kleinen Fälle passiert.

Wilson Johnson Reta232
quelle
Betrachten Sie den Testfall K = 2, A = [0, 21, 31, 45, 49, 54]. Die richtige Antwort ist 40, aber Ihr Programm gibt 51 aus.
Colera So
Noch einfacher: K = 2, A = [0, 4, 7, 9, 10]. Richtig: 7, Ihre Antwort: 8.
Colera So
Okay, es sollte jetzt funktionieren ... Es funktioniert zumindest für alle bereitgestellten Fälle.
Wilson Johnson Reta232
Eigentlich könnte ich auch einen anderen Algorithmus abgeleitet haben, der besser funktioniert. Ich werde die Theorie testen und in Kürze veröffentlichen.
Wilson Johnson Reta232
Immer noch nicht funktioniert ... K = 2, A = [0, 1, 3, 4, 9]. Richtig: 6, Ihre Antwort: 7.
Colera So
1

C (nicht konkurrierend, Pretest Score = 76)

Dies ist ein Versuch, @ AndersKaseorgs zweite Rust-Lösung in C zu übersetzen.

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);
}

Kompilieren mit:

#!/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
ngn
quelle
1

Sauber , Score = 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

Kompilieren mit:
clm -h 1024M -gci 32M -gcf 32 -s 32M -t -nci -ou -fusion -dynamics -IL Platform main

Nimmt Kund dann jedes Element von Aals Befehlszeilenargumente.

Οurous
quelle
@ColeraSu Darf ich fragen, was der entscheidende Faktor in der Punktzahl war? Richtigkeit / Zeit / Gedächtnis? Ich hoffe es war Zeit.
Οurous
Sie haben recht, es war Zeit.
Colera So