In this HackerRank Hard Disk Drives problem solution, we have given the locations of n pairs of hard disk drivers of HDDs and the number of computers K. we need to place all K computers in such a way that the total length of wire needed to connect each pair of HDDs to computers is minimal. and then print the total length on a new line.
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
static class Pll {
long fi;
long se;
Pll(long fi, long se) {
this.fi = fi;
this.se = se;
}
Pll() {}
}
static long[] xs;
static int lowerBound(long[] arr, long key) {
if (key <= arr[0]) {
return 0;
}
if (key > arr[arr.length - 1]) {
return 0;
}
int index = Arrays.binarySearch(arr, 0, arr.length, key);
if (index < 0) {
index = - index - 1;
if (index < 0) {
return 0;
}
}
while (index > 0 && arr[index-1] == key) {
index--;
}
return index;
}
static int allo;
static long[] segFi;
static long[] segSe;
static int[] child0;
static int[] child1;
static long x;
static long xx;
static void insert(int r, int rt, long l, long h) {
long m = l+h >> 1;
segFi[r] =segFi[rt] + 1;
segSe[r] = segSe[rt] + xx;
if (l < h-1) {
if (x < m) {
child1[r] = child1[rt];
child0[r] = allo++;
insert(child0[r], child0[rt], l, m);
} else {
child0[r] = child0[rt];
child1[r] = allo++;
insert(child1[r], child1[rt], m, h);
}
}
}
static long[] prefix;
static int[] root;
static long query(int l, int h) {
long r = prefix[2*h]-prefix[2*l];
int rt0 = root[2*l];
int rt1 = root[2*h];
int k = h-l;
l = 0;
h = xs.length;
while (k != 0 && l < h-1) {
int m = l+h >> 1;
long t = segFi[child0[rt1]] - segFi[child0[rt0]];
if (k < t) {
h = m;
rt0 = child0[rt0];
rt1 = child0[rt1];
} else {
k -= t;
r -= (segSe[child0[rt1]] - segSe[child0[rt0]])*2;
l = m;
rt0 = child1[rt0];
rt1 = child1[rt1];
}
}
if (k != 0) {
r -= segSe[rt1] / segFi[rt1]*k*2;
}
return r;
}
static long[] dp;
static long[] dp0;
static void conquer(int l, int h, int jl, long jh) {
if (l >= h) return;
int m = l+h >> 1;
long opt = Long.MAX_VALUE;
int optj = jl;
for (int j = jl; j < Math.min(jh, m); j++) {
if (dp[j] < Long.MAX_VALUE) {
long t = dp[j] + query(j, m);
if (t < opt) {
opt = t;
optj = j;
}
}
}
dp0[m] = opt;
conquer(l, m, jl, optj+1);
conquer(m+1, h, optj, jh);
}
static int N = 100000;
static int LOGN = 63-Long.numberOfLeadingZeros(N-1)+1;
static int V = 4*(LOGN+1);
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
Pll[] a = new Pll[n];
xs = new long[2*n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int fi = Integer.parseInt(st.nextToken());
int se = Integer.parseInt(st.nextToken());
a[i] = new Pll(fi, se);
xs[2*i] = fi;
xs[2*i+1] = se;
}
Arrays.sort(a, (u, v) -> { return (int)((u.fi + u.se) - (v.fi + v.se)); });
prefix = new long[2*n+1];
for (int i = 0; i < n; i++) {
prefix[2*i+1] = prefix[2*i]+a[i].fi;
prefix[2*i+2] = prefix[2*i+1]+a[i].se;
}
Arrays.sort(xs);
segFi = new long[2*n*V];
segSe = new long[2*n*V];
child0 = new int[2*n*V];
child1 = new int[2*n*V];
root = new int[2*n+1];
allo = 1;
for (int i = 0; i < n; i++) {
root[2*i+1] = allo++;
x = lowerBound(xs, a[i].fi);
xx = a[i].fi;
insert(root[2*i+1], root[2*i], 0, 2*n);
root[2*i+2] = allo++;
x = lowerBound(xs, a[i].se);
xx = a[i].se;
insert(root[2*i+2], root[2*i+1], 0, 2*n);
}
dp = new long[n+1];
dp0 = new long[n+1];
Arrays.fill(dp, Long.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < k; i++) {
conquer(1, n+1, 0, n);
System.arraycopy(dp0, 1, dp, 1, n);
}
bw.write(String.valueOf(dp[n]));
bw.newLine();
bw.close();
br.close();
}
}
Problem solution in C++.
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);
const int maxnk = 310004;
ll dbuf[maxnk];
ll *d[maxnk];
vector<pii> coords;
vector<pii> v;
namespace Set {
int t[maxnk * 2];
int base = 1;
void init() {
base = 1;
while (base < sz(coords))
base *= 2;
fill(t, t + 2 * base, 0);
}
void put(int v, int val) {
v += base;
t[v] = val;
while (v > 1) {
v /= 2;
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
int prev(int v) {
v += base;
while (true) {
int u = v;
v /= 2;
if ((u & 1) && t[u] != t[v]) {
v *= 2;
break;
}
}
while (v < base) {
v *= 2;
if (t[v + 1] > 0)
++v;
}
return v - base;
}
int next(int v) {
v += base;
while (true) {
int u = v;
v /= 2;
if (!(u & 1) && t[u] != t[v]) {
v = v * 2 + 1;
break;
}
}
while (v < base) {
v *= 2;
if (t[v] == 0)
++v;
}
return v - base;
}
}
namespace T {
int bl, br;
int pos;
ll f;
void init(int id) {
Set::init();
bl = id, br = id + 1;
Set::put(v[id].first, 1);
Set::put(v[id].second, 1);
pos = v[id].second;
f = coords[v[id].second].first - coords[v[id].first].first;
}
void move(int to) {
f += (coords[to].first - coords[pos].first) * 2;
pos = to;
}
void ins(int id) {
int l = v[id].first;
int r = v[id].second;
Set::put(l, 1);
Set::put(r, 1);
f += abs(coords[r].first - coords[pos].first);
f += abs(coords[l].first - coords[pos].first);
if (pos < l)
pos = Set::next(pos);
else if (r < pos)
move(Set::prev(pos));
}
void del(int id) {
int l = v[id].first;
int r = v[id].second;
if (pos <= l)
pos = Set::prev(pos);
else if (r <= pos)
move(Set::next(pos));
Set::put(l, 0);
Set::put(r, 0);
f -= abs(coords[r].first - coords[pos].first);
f -= abs(coords[l].first - coords[pos].first);
}
void moveBounds(int nl, int nr) {
assert(nl < nr);
while (br < nr)
ins(br++);
while (bl > nl)
ins(--bl);
while (br > nr)
del(--br);
while (bl < nl)
del(bl++);
assert(bl == nl && br == nr);
}
}
int ck;
void divideAndConquer(int l, int r, int pl, int pr) {
assert(T::bl == pl && T::br == l);
int mid = (l + r) / 2;
int pm = pl;
T::moveBounds(pm, mid);
pair<ll, int> best{T::f + d[ck][pm], pm};
for (pm = pl + 1; pm < min(mid, pr); ++pm) {
T::moveBounds(pm, mid);
best = min(best, {T::f + d[ck][pm], pm});
}
d[ck + 1][mid] = best.first, pm = best.second;
if (mid + 1 < r) {
T::moveBounds(pm, mid + 1);
divideAndConquer(mid + 1, r, pm, pr);
}
T::moveBounds(pl, l);
if (l < mid)
divideAndConquer(l, mid, pl, pm + 1);
}
int main() {
#ifdef LOCAL
assert(freopen("test.in", "r", stdin));
#else
#endif
int n, k;
cin >> n >> k;
forn (i, k + 1)
d[i] = dbuf + i * (n + 1);
vector<pii> _v;
forn (i, n) {
int l, r;
cin >> l >> r;
if (l > r)
swap(l, r);
_v.emplace_back(l, r);
}
sort(_v.begin(), _v.end(), [](pii a, pii b) {
return a.first + a.second < b.first + b.second;
});
forn (i, n) {
coords.emplace_back(_v[i].first, i * 2);
coords.emplace_back(_v[i].second, i * 2 + 1);
}
sort(coords.begin(), coords.end());
v.resize(n);
forn (i, n) {
v[i].first = lower_bound(coords.begin(), coords.end(),
pii{_v[i].first, i * 2}) - coords.begin();
v[i].second = lower_bound(coords.begin(), coords.end(),
pii{_v[i].second, i * 2 + 1}) - coords.begin();
}
forn (i, k + 1)
fill(d[i], d[i] + n + 1, infl);
d[0][0] = 0;
forn (j, k) {
T::init(0);
ck = j;
divideAndConquer(1, n + 1, 0, n);
}
cout << d[k][n] << 'n';
}