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.

HackerRank Mining problem solution


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