HackerRank Hard Disk Drives problem solution

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