Table of Contents
Hard Disk Drives – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cassert>
#include <ctime>
#include <map>
#include <math.h>
#include <cstdio>
#include <set>
#include <deque>
#include <memory.h>
#include <queue>
#include <unordered_map>
#pragma comment(linker, "/STACK:64000000")
typedef long long ll;
using namespace std;
const int MAXN = 1 << 18;
const int MOD = 1; // 1000 * 1000 * 1000 + 7;
const ll INF = (ll)(1e18);
int n, k, m;
vector<int> a, b, vct;
vector<vector<ll> > dp;
vector<vector<int> > id[2];
vector<pair<int, int> > t[2][MAXN * 2];
vector<int> tt[2][MAXN * 2];
vector<ll> s[2][MAXN * 2];
void make(int tp, int v) {
s[tp][v].resize(t[tp][v].size());
for (int i = 0; i < (int)t[tp][v].size(); i++) {
s[tp][v][i] = (i ? s[tp][v][i - 1] : 0) + t[tp][v][i].second;
}
tt[tp][v].resize(t[tp][v].size());
for (int i = 0; i < (int)t[tp][v].size(); i++) {
tt[tp][v][i] = t[tp][v][i].first;
}
}
void build(int tp, int v, int tl, int tr) {
t[tp][v].clear();
if (tl == tr) {
t[tp][v].reserve(id[tp][tl].size());
for (int r : id[tp][tl]) {
if (tp == 0) {
t[tp][v].push_back(make_pair(vct[a[r]] + vct[b[r]], vct[a[r]]));
}
else {
t[tp][v].push_back(make_pair(-vct[a[r]] - vct[b[r]], -vct[b[r]]));
}
}
sort(t[tp][v].begin(), t[tp][v].end());
make(tp, v);
return;
}
int tm = (tl + tr) >> 1;
build(tp, v * 2, tl, tm);
build(tp, v * 2 + 1, tm + 1, tr);
t[tp][v].resize(t[tp][v * 2].size() + t[tp][v * 2 + 1].size());
merge(t[tp][v * 2].begin(), t[tp][v * 2].end(), t[tp][v * 2 + 1].begin(), t[tp][v * 2 + 1].end(), t[tp][v].begin());
make(tp, v);
}
ll coef;
ll get(int tp, int v, int tl, int tr, int l, int r, int x) {
if (l > r) return 0;
if (l == tl && r == tr) {
//int id = lower_bound(t[tp][v].begin(), t[tp][v].end(), make_pair(x, -(int)(1.1e9))) - t[tp][v].begin();
int id = lower_bound(tt[tp][v].begin(), tt[tp][v].end(), x) - tt[tp][v].begin();
return (id > 0) ? (id * coef + s[tp][v][id - 1]) : 0LL;
}
int tm = (tl + tr) >> 1;
return get(tp, v * 2, tl, tm, l, min(r, tm), x) + get(tp, v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x);
}
unordered_map<ll, ll> mp;
ll cost(int l, int j) {
if (l > j) return INF;
ll hh = ((ll)l << 32) + j;
if (mp.count(hh)) {
return mp[hh];
}
ll cost = 0;
coef = -vct[l];
cost += get(0, 1, 0, m - 1, l, j, vct[l] + vct[j] + 1);
coef = vct[j];
cost += get(1, 1, 0, m - 1, l, j, -vct[l] - vct[j]);
cost *= 2;
mp[hh] = cost;
return cost;
}
void rec(int k, int l, int r, int optL, int optR) {
if (l > r) return;
int m = (l + r) >> 1;
int opt = -1;
for (int i = optL; i <= optR; i++) {
if (dp[k - 1][i] >= dp[k][m]) continue;
if (dp[k][m] > dp[k - 1][i] + cost(i, m)) {
dp[k][m] = dp[k - 1][i] + cost(i, m);
opt = i;
}
}
rec(k, l, m - 1, optL, opt);
rec(k, m + 1, r, opt, optR);
}
int main() {
#ifdef _MSC_VER
freopen("input.txt", "r", stdin);
#endif
mp.reserve((int)(5e6));
while (scanf("%d%d", &n, &k) == 2) {
a.resize(n);
b.resize(n);
for (int i = 0; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
a[i] = x;
b[i] = y;
if (a[i] > b[i]) swap(a[i], b[i]);
}
vct.clear();
for (int i = 0; i < n; i++) {
vct.push_back(a[i]);
vct.push_back(b[i]);
}
vct.push_back(-1.001e9);
vct.push_back(1.001e9);
sort(vct.begin(), vct.end());
vct.resize(unique(vct.begin(), vct.end()) - vct.begin());
m = vct.size();
for (int i = 0; i < n; i++) {
a[i] = lower_bound(vct.begin(), vct.end(), a[i]) - vct.begin();
b[i] = lower_bound(vct.begin(), vct.end(), b[i]) - vct.begin();
}
id[0].assign(m, vector<int>());
id[1].assign(m, vector<int>());
for (int i = 0; i < n; i++) {
id[0][a[i]].push_back(i);
id[1][b[i]].push_back(i);
}
build(0, 1, 0, m - 1);
build(1, 1, 0, m - 1);
ll sum = 0;
for (int i = 0; i < n; i++) sum += vct[b[i]] - vct[a[i]];
dp.assign(k + 1, vector<ll>(m, INF));
dp[0][0] = 0;
cerr << clock() / (double)CLOCKS_PER_SEC << endl;
for (int i = 1; i <= k; i++) {
rec(i, 1, m - 1, 0, m - 1);
}
ll mn = INF;
ll ssum = 0;
int cnt = 0;
for (int i = m - 1; i >= 0; i--) {
mn = min(mn, dp[k][i] + 2 * (ssum - 1LL * cnt * vct[i]));
for (int ii = 0; ii < (int)id[0][i].size(); ii++) {
int iid = id[0][i][ii];
cnt++;
ssum += vct[a[iid]];
}
}
//ll mn = dp[k + 1][m - 1];
cout << sum + mn << endl;
}
cerr << clock() / (double)CLOCKS_PER_SEC << endl;
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
static HD[] hdds;
static Point[] points;
static int n, k;
static long[][] f;
static long[] g;
static long totalLength;
static SegmentTree stHD;
static PersistentSegmentTree pst;
static Vertex[] rootsPST;
static boolean dist;
static long[] prefR;
static long[] prefL;
static Calc calc;
static class HD {
int left, right, length;
Point pL, pR;
long mid;
int index;
public HD(int left, int right) {
boolean b = left > right;
this.left = b ? right : left;
this.right = b ? left : right;
mid = (left + right);
length = (this.right - this.left);
}
@Override
public String toString() {
return left + " " + right + " " + mid;
}
}
static class Point {
HD hd;
int point;
int sortIndex;
public Point(HD hd, boolean isLeft) {
this.hd = hd;
point = isLeft ? hd.left : hd.right;
}
@Override
public String toString() {
return hd.left + " " + hd.right + " " + point;
}
}
static interface Calc {
public long getW(int start, int end);
}
static class Pair {
int nL, nR;
long sumL, sumR;
public Pair(int nR, int nL, long sumR, long sumL) {
this.nR = nR;
this.nL = nL;
this.sumR = sumR;
this.sumL = sumL;
}
}
static class Node {
int[] valueSLe;
int[] valueSRi;
long[] sumParR;
long[] sumParL;
int size;
int nL, nR;
public Node() {
}
}
static class SegmentTree {
Node[] t;
SegmentTree(int n) {
t = new Node[4 * n];
for (int i = 0; i < 4 * n; i++) {
t[i] = new Node();
}
}
void build(HD[] a, int v, int tl, int tr) {
if (tl == tr) {
t[v].valueSLe = new int[1];
t[v].valueSRi = new int[1];
t[v].valueSRi[0] = a[tl + 1].pR.point;
t[v].valueSLe[0] = a[tl + 1].pL.point;
t[v].size = 1;
t[v].sumParL = new long[1];
t[v].sumParL[0] = a[tl + 1].left;
t[v].sumParR = new long[1];
t[v].sumParR[0] = a[tl + 1].right;
} else {
int tm = (tl + tr) / 2;
build(a, v * 2, tl, tm);
build(a, v * 2 + 1, tm + 1, tr);
t[v].size = t[v * 2].size + t[v * 2 + 1].size;
merge(v);
}
}
private void merge(int v) {
t[v].valueSLe = new int[t[v].size];
t[v].valueSRi = new int[t[v].size];
t[v].sumParL = new long[t[v].size];
t[v].sumParR = new long[t[v].size];
mergeAInt(t[v].valueSLe, t[2 * v].valueSLe, t[2 * v + 1].valueSLe);
mergeAInt(t[v].valueSRi, t[2 * v].valueSRi, t[2 * v + 1].valueSRi);
updateCS(t[v]);
}
private void updateCS(Node node) {
long[] sumParLu = new long[node.size];
long[] sumParRu = new long[node.size];
int[] valueL = node.valueSLe;
int[] valueR = node.valueSRi;
sumParLu[0] = valueL[0];
sumParRu[0] = valueR[0];
for (int i = 1; i < node.size; i++) {
sumParLu[i] = sumParLu[i - 1] + valueL[i];
sumParRu[i] = sumParRu[i - 1] + valueR[i];
}
node.sumParL = sumParLu;
node.sumParR = sumParRu;
}
static long[] ZERO = new long[] { 0, 0, 0, 0 };
void query(int v, int tl, int tr, int l, int r, int p, long[] fResults) {
if (l > r || tr < l || tl > r) {
return;
}
if (l == tl && tr == r) {
Node node = t[v];
int size = node.size;
long[] sPL = node.sumParL;
int limU = upperBound(node.valueSRi, p);
int limL = lowerBound(node.valueSLe, p);
int nR = limU == -1 ? 0 : limU + 1;
long sumR = limU == -1 ? 0 : node.sumParR[limU];
int nL = limL == size ? 0 : size - limL;
long sumL = limL == size ? 0 : sPL[size - 1] - (limL == 0 ? 0 : sPL[limL - 1]);
fResults[0] += nR;
fResults[1] += nL;
fResults[2] += sumR;
fResults[3] += sumL;
return;
}
int tm = (tl + tr) / 2;
query(v * 2, tl, tm, l, Math.min(r, tm), p, fResults);
query(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, p, fResults);
}
}
static class Vertex {
Vertex l, r;
int count;
Vertex(int val) {
count = val;
}
Vertex(Vertex l, Vertex r) {
this.l = l;
this.r = r;
if (l != null)
count += l.count;
if (r != null)
count += r.count;
}
};
static class PersistentSegmentTree {
Vertex build(int tl, int tr) {
if (tl == tr) {
return new Vertex(0);
}
int tm = (tl + tr) / 2;
return new Vertex(build(tl, tm), build(tm + 1, tr));
}
Vertex update(Vertex v, int tl, int tr, int pos) {
if (tl == tr) {
return new Vertex(1);
}
int tm = (tl + tr) / 2;
if (pos <= tm) {
return new Vertex(update(v.l, tl, tm, pos), v.r);
} else {
return new Vertex(v.l, update(v.r, tm + 1, tr, pos));
}
}
int query(Vertex v1, Vertex v2, int b, int e, int x) {
if (b == e) {
return b;
}
int oo = v1.l.count - v2.l.count;
int mid = (b + e) / 2;
if (oo >= x) {
return query(v1.l, v2.l, b, mid, x);
} else {
return query(v1.r, v2.r, mid + 1, e, x - oo);
}
}
}
static void mergeAInt(int[] values, int[] values1, int[] values2) {
int n1 = values1.length;
int n2 = values2.length;
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
int p1 = values1[i];
int p2 = values2[j];
if (p1 <= p2) {
i++;
values[k++] = p1;
} else {
j++;
values[k++] = p2;
}
}
while (i < n1) {
values[k++] = values1[i++];
}
while (j < n2) {
values[k++] = values2[j++];
}
}
static private int upperBound(int[] arr, int endV) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (right + left) / 2;
if (arr[mid] <= endV) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
static private int lowerBound(int[] arr, int startV) {
int left = 0;
int al = arr.length;
int right = al - 1;
while (left <= right) {
int mid = (right + left) / 2;
if (arr[mid] >= startV) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
private static void initW() {
f = new long[k + 1][n + 1];
g = new long[n + 2];
Arrays.sort(hdds, 1, n + 1, new Comparator<HD>() {
@Override
public int compare(HD o1, HD o2) {
long d = o1.mid - o2.mid;
if (d != 0) {
return d < 0 ? -1 : 1;
} else {
return o1.left - o2.left;
}
}
});
SASD sd = new SASD();
dist = true;
for (int j = 1; j <= n; j++) {
sd.add(hdds[j]);
f[1][j] = sd.ans;
if (j < n && hdds[j].right > hdds[j + 1].left) {
dist = false;
}
}
if (!dist) {
calc = new Calc() {
@Override
public long getW(int start, int end) {
return getW1(start, end);
}
};
Point[] pointsToSort = new Point[2 * n];
for (int j = 1; j <= n; j++) {
HD hd = hdds[j];
hd.index = j;
Point p = new Point(hd, true);
hd.pL = p;
pointsToSort[2 * j - 2] = p;
p = new Point(hd, false);
hd.pR = p;
pointsToSort[2 * j - 1] = p;
}
Arrays.sort(pointsToSort, 0, 2 * n, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
long d = o1.point - o2.point;
if (d != 0) {
return d < 0 ? -1 : 1;
} else {
return o1.hd.index - o2.hd.index;
}
}
});
points = new Point[2 * n];
for (int j = 0; j < 2*n; j++) {
Point p = pointsToSort[j];
p.sortIndex = j;
points[j] = p;
}
stHD = new SegmentTree(n);
stHD.build(hdds, 1, 0, n - 1);
rootsPST = new Vertex[n+1];
pst = new PersistentSegmentTree();
rootsPST[0] = pst.build(0, 2*n-1);
for (int j = 1; j <= n; j++) {
Vertex root = pst.update(rootsPST[j-1], 0, 2*n-1, hdds[j].pL.sortIndex);
rootsPST[j] = pst.update(root, 0, 2*n-1, hdds[j].pR.sortIndex);
}
} else {
calc = new Calc() {
@Override
public long getW(int start, int end) {
return getW2(start, end);
}
};
prefL = new long[n + 1];
prefR = new long[n + 1];
for (int j = 1; j <= n; j++) {
prefR[j] = prefR[j - 1] + hdds[j].right;
prefL[j] = prefL[j - 1] + hdds[j].left;
}
}
}
static Map<Integer, Long>[] memo;
private static long getW1(int jStart, int jEnd) {
Long ans = memo[jEnd].get(jStart);
if (ans != null) {
return ans;
}
int mid = pst.query(rootsPST[jEnd], rootsPST[jStart-1], 0, 2 * n - 1, jEnd-jStart+1);
int p = points[mid].point;
long[] pair = new long[4];
stHD.query(1, 0, n - 1, jStart - 1, jEnd - 1, p, pair);
ans = p * pair[0] - pair[2] + pair[3] - p * pair[1];
memo[jEnd].put(jStart, ans);
return ans;
}
private static long getW2(int jStart, int jEnd) {
int mid = (jStart + jEnd) / 2;
long p = hdds[mid].right;
long ans = p * (mid - jStart + 1) - (prefR[mid] - prefR[jStart - 1]) + (prefL[jEnd] - prefL[mid])
- p * (jEnd - mid);
return ans;
}
static int INF = 2000000000;
static class SASD {
int mid1 = -INF;
int mid2 = INF;
long ans;
private PriorityQueue<Integer> r = new PriorityQueue<Integer>();
void add(HD hd) {
int nLow = hd.left;
int nHigh = hd.right;
if (nLow >= mid2) {
ans += (nLow - mid2);
r.remove();
r.add(nLow);
r.add(nHigh);
mid1 = mid2;
mid2 = r.peek();
} else if (nLow < mid1) {
r.add(nHigh);
} else {
r.add(nHigh);
mid1 = nLow;
if (mid2 == INF) {
mid2 = nHigh;
}
if (nHigh <= mid2) {
mid2 = nHigh;
}
}
}
}
static class SADS {
int mid1 = -INF;
int mid2 = INF;
long ans;
private PriorityQueue<Integer> l = new PriorityQueue<Integer>(n, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
void add(HD hd) {
int nLow = hd.left;
int nHigh = hd.right;
if (nHigh <= mid1) {
ans += (mid1 - nHigh);
l.remove();
l.add(nLow);
l.add(nHigh);
mid2 = mid1;
mid1 = l.peek();
} else if (nHigh > mid2) {
l.add(nLow);
if (nLow >= mid2) {
ans += (nHigh - mid2);
}
} else {
l.add(nLow);
mid2 = nHigh;
if (mid1 == -INF) {
mid1 = nLow;
}
if (nLow >= mid1) {
mid1 = nLow;
}
}
}
}
//static int c = 0;
//static long time = 0;
static long hardDrive() {
if (k == n) {
return totalLength;
}
initW();
if (f[1][n] == 0) {
return totalLength;
}
int STEEP = 10;
SADS ds = new SADS();
long ans = f[1][n];
int minG = 1;
for (int s = n; s >= 1; s--) {
ds.add(hdds[s]);
g[s] = ds.ans;
long pAns = f[1][s - 1] + ds.ans;
if (pAns < ans) {
ans = pAns;
minG = s;
}
}
f[2][n] = ans;
if (k == 2) {
return 2 * ans + totalLength;
}
long fRMIN = 0;
int[] minAJ = new int[n + 1];
Arrays.fill(minAJ, 1);
for (int i = 2; i < k; i++) {
if (i == k - 1) {
ans = f[i - 1][n];
int lower = minG;
int higher = n;
if (higher > lower + STEEP) {
Pair p = search(calc, i, n, lower, higher, STEEP);
ans = p.sumR;
lower = p.nR;
higher = p.nL;
}
for (int s = lower; s <= higher; s++) {
long pAns = f[i - 1][s - 1] + g[s];
if (pAns < ans) {
ans = pAns;
minG = s;
}
}
f[i][n] = ans;
fRMIN = ans;
int minG2 = n;
minG = minG > 1 ? minG - 1 : 1;
int fSteep = 100;
for (int j = minG; j <= minG2; j++) {
ans = f[i - 1][j];
lower = 1;
higher = j;
if (higher > lower + STEEP) {
Pair p = search(calc, i, j, lower, higher, STEEP);
ans = p.sumR;
lower = p.nR;
higher = p.nL;
}
if (f[i - 1][lower - 1] != f[i - 1][higher - 1]) {
for (int s = lower; s <= higher; s++) {
long pAns = f[i - 1][s - 1] + calc.getW(s, j);
if (pAns < ans) {
ans = pAns;
}
}
} else {
ans = f[i - 1][higher - 1] + calc.getW(higher, j);
}
f[i][j] = ans;
long pFA = ans + g[j + 1];
if (pFA < fRMIN) {
fRMIN = pFA;
}
if (ans >= fRMIN) {
break;
}
if (j + fSteep <= minG2 && ans + g[j + fSteep] >= fRMIN) {
j = j + fSteep;
}
while (j < minG2 && g[j+1] == g[j+2]) {
j++;
}
}
} else {
for (int j = i + 1; j < n; j++) {
ans = f[i - 1][j];
int nMin = minAJ[j];
int lower = nMin;
int higher = j;
if (higher > lower + STEEP) {
Pair p = search(calc, i, j, lower, higher, STEEP);
ans = p.sumR;
lower = p.nR;
higher = p.nL;
}
if (f[i - 1][lower - 1] != f[i - 1][higher - 1]) {
for (int s = lower; s <= higher; s++) {
long pAns = f[i - 1][s - 1] + calc.getW(s, j);
if (pAns < ans) {
ans = pAns;
nMin = s;
}
}
} else {
ans = f[i - 1][higher - 1] + calc.getW(higher, j);
}
f[i][j] = ans;
minAJ[j] = nMin;
}
}
}
return 2 * fRMIN + totalLength;
}
static Pair search(Calc calc, int i, int j, int lower, int higher, int steep) {
long ans = 0;
while (higher > lower + steep) {
int mid = (lower + higher) / 2;
int mid1 = (lower + mid) / 2;
mid1 = mid1 % 2 == 0 ? mid1 : mid1 + 1;
int mid2 = (higher + mid) / 2;
mid2 = mid2 % 2 == 0 ? mid2 : mid2 - 1;
long res1 = f[i - 1][mid1 - 1] + calc.getW(mid1, j);
long res2 = f[i - 1][mid2 - 1] + calc.getW(mid2, j);
if (res1 < res2) {
higher = mid2 - 1;
ans = res1;
} else if (res1 >= res2) {
lower = mid1 + 1;
ans = res2;
}
}
return new Pair(lower, higher, ans, 0);
}
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 2 * 4096 * 4096);
String[] nk = reader.readLine().trim().split(" ");
n = Integer.parseInt(nk[0]);
k = Integer.parseInt(nk[1]);
hdds = new HD[n + 1];
totalLength = 0;
for (int hddsRowItr = 1; hddsRowItr <= n; hddsRowItr++) {
String[] hddsRowItems = reader.readLine().trim().split(" ");
HD hd = new HD(Integer.parseInt(hddsRowItems[0]), Integer.parseInt(hddsRowItems[1]));
hdds[hddsRowItr] = hd;
totalLength += hd.length;
}
memo = new Map[n+1];
for (int j = 1; j <= n; j++) {
memo[j] = new HashMap<Integer, Long>();
}
dist = true;
long result = hardDrive();
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
reader.close();
}
}
Python 3 rep HackerRank Solution
Python 2 rep HackerRank Solution
C rep HackerRank Solution
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
