HackerRank Mining problem solution

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