In this HackerRank Mining problem solution Given N, K, and the amount of gold produced at each mine, find and print the minimum cost of consolidating the gold into K pickup locations according to the above conditions.
Problem solution in Java.
import java.io.*; import java.util.*; public class Solution { static long chase2(long dpij0, long dpij1, long[][] cost, int j0, int j1) { long l = j1 + 1; long h = cost.length; while (l < h) { int m = (int) (l + h >> 1); if (dpij0 + cost[j0][m] < dpij1 + cost[j1][m]) { l = m + 1; } else { h = m; } } return l; } static long mining(int k, int[] x, int[] w) { long[][] cost = new long[x.length][x.length]; long[] dp1 = new long[x.length]; long[] dp2 = new long[x.length]; long sumi = 0; long sumi2 = 0; for (int i = 0; i < x.length; i++) { int ki = i; long sumk = sumi; long sumk2 = sumi2; long sumj = sumi; long sumj2 = sumi2; for (int j = i; j < x.length; j++) { sumj += w[j]; sumj2 += (long)w[j]*x[j]; for (; ki < j && x[ki]-x[i] < x[j]-x[ki]; ki++) { sumk += w[ki]; sumk2 += (long)w[ki]*x[ki]; } cost[i][j] = sumk2-sumi2-(sumk-sumi)*x[i] + (sumj-sumk)*x[j]-sumj2+sumk2; } sumi += w[i]; sumi2 += (long)w[i]*x[i]; dp1[i] = sumi*x[i]-sumi2; } int[] q = new int[x.length]; for (int i = 0; i < k-1; i++) { int hd = 0; int tl = 0; for (int j = 0; j < q.length; j++) { while (hd+1 < tl && dp1[q[hd]]+cost[q[hd]][j] > dp1[q[hd+1]]+cost[q[hd+1]][j]) { hd++; } dp2[j] = j != 0 ? dp1[q[hd]]+cost[q[hd]][j] : 0; while (hd <= tl - 2 && chase2(dp1[q[tl - 2]], dp1[q[tl - 1]], cost, q[tl - 2], q[tl - 1]) > chase2(dp1[q[tl - 1]], dp1[j], cost, q[tl - 1], j)) { tl--; } q[tl++] = j; } long[] t = dp1; dp1 = dp2; dp2 = t; } long ans = Long.MAX_VALUE; long sum = sumi; long sum2 = sumi2; sumi = sumi2 = 0; for (int i = 0; i < x.length; i++) { ans = Math.min(ans, dp1[i]+sum2-sumi2-(sum-sumi)*x[i]); sumi += w[i]; sumi2 += (long)w[i]*x[i]; } return ans; } 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()); int[] x = new int[n]; int[] w = new int[n]; for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine()); x[i] = Integer.parseInt(st.nextToken()); w[i] = Integer.parseInt(st.nextToken()); } long result = mining(k, x, w); bw.write(String.valueOf(result)); bw.newLine(); bw.close(); br.close(); } }
Problem solution in C++.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; vector<long long> Fk, Fknew; vector<vector<long long>> C; void updatefk(int mina, int maxa, int minc, int maxc) { if (mina==maxa) return; int mid = (mina+maxa)/2; long long optval=-1; int opti = -1; for (int i=minc; i<=maxc && i<=mid;++i) { long long val = Fk[i]+C[i][mid]; if (optval>val || optval==-1) { optval = val; opti = i; } } Fknew[mid] = optval; updatefk(mina, mid, minc, opti); updatefk(mid+1, maxa, opti, maxc); } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int n, k; cin >> n >> k; vector<long long> x(n), w(n); for (int i=0;i<n;++i) { cin >> x[i] >> w[i]; } C = vector<vector<long long>>(n, vector<long long>(n, 0)); for (int i=0;i<n;++i) { int firsttoj=i; long long goldtoj=w[firsttoj]; long long cost=0; for (int j=i+1;j<n;++j) { cost+=(x[j]-x[j-1])*goldtoj; goldtoj+=w[j]; while ( x[firsttoj]-x[i]<x[j]-x[firsttoj] ) { cost+= (2*x[firsttoj]-x[j]-x[i])*w[firsttoj];goldtoj-=w[firsttoj++]; } C[i][j]=cost; } } vector<long long> Cminusinf(n, 0), Cinf(n, 0); long long weight = w[0]; Cminusinf[0]=0; for (int i=1;i<n;++i) { Cminusinf[i]=Cminusinf[i-1]+weight*(x[i]-x[i-1]); weight+=w[i]; } Cinf[n-1]=0; weight = w[n-1]; for (int i=n-2;i>=0;--i) { Cinf[i]=Cinf[i+1]+weight*(x[i+1]-x[i]); weight+=w[i]; } Fk = vector<long long>(n, 0); Fknew = vector<long long>(n, 0); for (int i=0;i<n;++i) Fk[i]=Cminusinf[i]; for (int i=1; i<k;++i) { updatefk(0, n, 0, n-1); Fk=Fknew; } long long record = -1; for (int i=0;i<n;++i) { long long val=Fk[i]+Cinf[i]; if (val<record || record == -1) record = val; } cout << record << endl; return 0; }
Problem solution in C.
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> int x[5000]; int w[5000]; int64_t val[5000][5000]; int64_t a[5000], b[5000]; int64_t mining() { int n, k, i; scanf("%d %d", &n, &k); for(i = 0; i < n; ++ i) scanf("%d %d", &x[i], &w[i]); for(i = 0; i < n; ++i) { int64_t left = 0, right = 0, acc = 0; int s, j; for(j = i + 1, s = i; j < n; ++ j) { acc += w[j] * (int64_t)(x[j] - x[s]); right += w[j]; while(s < j && left + w[s] < right) { acc += (left + w[s] - right) * (int64_t)(x[s + 1] - x[s]); left += w[s]; right -= w[s + 1]; ++ s; } val[j][i] = acc; } } /* memcpy(a, val[0], n * sizeof(int64_t)); */ for(i = 0; i < n; ++ i) a[i] = val[i][0]; if(n * (int64_t) n * (int64_t) k < 1000000000) { for(; 1 < k; --k) for(i = n - 1; -1 < i; --i) { int s; a[i] = val[i][0]; for(s = 1; s < i + 1; ++ s) { const int64_t c = a[s - 1] + val[i][s]; if(c < a[i]) a[i] = c; } } return a[n - 1]; } for(; 1 < k; -- k) { int idx = 0; memcpy(b, a, n * sizeof(int64_t)); for(i = 0; i < n; ++ i) { a[i] = (idx ? b[idx - 1] : 0) + val[i][idx]; for(; idx < i && b[idx] + val[i][idx + 1] < a[i]; ++ idx) a[i] = b[idx] + val[i][idx + 1]; { int s = i; for(s = i; idx < s && i < s + 50; -- s) { const int64_t v = (s ? b[s - 1] : 0) + val[i][s]; if(v < a[i]) a[i] = v; } } } } return a[n - 1]; } int main() { printf("%lld", (long long) mining()); return EXIT_SUCCESS; }