Build an Electrical Grid
Rust, score = 104
This is an implementation of the algorithm noted by Grønlund et al. (2017) at the end of §3.3.1, though I had to follow a long citation chain and fill in some missing details. It runs in O(N log A[N − 1]) time.
Compile with rustc -O. Input format is K on the first line, followed by the entries of A, one entry per line, all on stdin.
(Note: I’m submitting this an hour after the bounty deadline, but I expect the last version I submitted before the bounty deadline, which ran in O(N log N log A[N − 1]) time, to score about 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()
);
}
Try it online!
Rust, pretest score = 73
Compile with rustc -O. Input format is K on the first line, followed by the entries of A, one entry per line, all on 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()
);
}
Try it online!
C, score = 56
content of 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 script to compile and test the above:
#!/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 takes 6.2s, n=891 takes 12s
n=1176 takes 5.9s, n=1351 takes a little over 10s
n=1351 takes 8.7s, n=1552 takes more than 10s
(with k=2*n/3) on my Intel(R) Core(TM) i3-2375M CPU @ 1.50GHz
C++, score = 53
The solution I had said in the comment. O(n²×k). (now I deleted it because it is no longer necessary) Probably can be reduced to O(n×k).
The input is pretty flexible, on the first line, the first number is k, the other numbers are items of array a, but if it encounters any close-parentheses it stops reading input. So input like K = 1, A = [0, 2, 4, 6, 8] : 12 is accepted.
// https://codegolf.stackexchange.com/questions/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;
}
Try it online!
Generate random test cases. (input N and optionally city range, 1000×N by default)