HackerRank Mining Problem Solution

In this post, we will solve HackerRank Mining Problem Solution.

There are n gold mines along a river, and each mine i produces w, tons of gold. In order to collect the mined gold, we want to redistribute and consolidate it amongst exactly k mines where it can be picked up by trucks. We do this according to the following rules:
You can move gold between any pair of mines (i.e.. i and j, where 1 <i<j<n).

All the gold at some pickup mine i must either stay at mine i or be completely moved to some other mine, j.
Move w tons of gold between the mine at location, and the mine at location, at a cost of xxxw.
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.
Input Format
The first line contains two space-separated integers describing the respective values of n (the number of mines) and k (the number of pickup locations).
Each line of the n subsequent lines contains two space-separated integers describing the respective values of x, (the mine’s distance from the mouth of the river) and w, (the amount of gold produced in tons) for mine i.
Note: It is guaranteed that the mines are will be given in order of ascending location.

Output Format

Print a single line with the minimum cost of consolidating the mined gold amongst K different pickup sites according to the rules stated above.

Sample Input 0

Sample Output 0

Explanation 0
We need to consolidate the gold from n = 3 mines into a single pickup location (because k = 1). The mines are all equidistant and they all produce the same amount of gold, so we just move the gold from the mines at locations X = 20 and x = 40 to the mine at x = 30 for a minimal cost of 20.

Sample Input 1

Sample Input 1

Explanation 1
We need to consolidate the gold from n = 3 mines into a single pickup location (because k = 1). We can achieve a minimum cost of 4 by moving the gold from mines = 12 and x = 13 to the mine at x = 11.

Table of Contents

Mining C Solution

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

Mining C++ Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, x, n) for(int i = int(x); i <= int(n); ++i)
#define for1(i, n, x) for(int i = int(n); i >= int(x); --i)
#define file ""
#define pb push_back
#define F first
#define S second
#define _bits __builtin_popcountll

typedef long long ll;
typedef long double ld;
typedef pair <int, int> PII;

const int N = 5e3 + 10;         
const ll INF = 1e18;                                           
const int B = 1e9 + 7;                     
                                
int n, k;
ll w[N], m[N], x[N], s[N];
ll d[N][N], cost[N][N];
int at[N][N];

ll f(int l, int r, int i) {
	ll cur = (s[i] - s[l - 1]) * x[i] - (m[i] - m[l - 1]);
	return cur + (m[r] - m[i]) - (s[r] - s[i]) * x[i];
}

int main() {
#ifdef machine42
	freopen(file"in", "r", stdin);
	freopen(file"out", "w", stdout);
#endif
	ios_base :: sync_with_stdio (0);
	cin.tie(0);

	cin >> n >> k;
	forn(i, 1, n) {
		cin >> x[i] >> w[i];
        s[i] = s[i - 1] + w[i];
        m[i] = m[i - 1] + w[i] * x[i];
    }        

	forn(l, 1, n) {
		int ptr = l;
		forn(r, l, n) {
			while (ptr < r && f(l, r, ptr) >= f(l, r, ptr + 1)) ++ptr;
			cost[l][r] = f(l, r, ptr);	                        
		}
	}    

	d[0][0] = 0;
	forn(i, 1, k)
		d[0][i] = INF;	
	forn(i, 1, n) {
		d[i][0] = INF; 
		at[i][k + 1] = i - 1;
		for1(j, k, 1) {	
			d[i][j] = INF;
			forn(p, at[i - 1][j], at[i][j + 1]) {
				if (d[i][j] >= d[p][j - 1] + cost[p + 1][i]) {
					d[i][j] = d[p][j - 1] + cost[p + 1][i];
					at[i][j] = p;
				}	
			}
			assert(at[i][j] >= at[i - 1][j]);
			if (j < k) assert(at[i][j] <= at[i][j + 1]);
		}            
	}

	cout << d[n][k] << "\n";

	return 0;
}

Mining C Sharp Solution

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;

public class Solver
{
    int n, m;
    long[][] dp, cost;
    void Fun(int d, int l, int r, int ol, int or)
    {
        if (l > r)
            return;
        if (l == r)
        {
            for (int i = ol; i <= or && i < l; i++)
                if (dp[d - 1][i] < long.MaxValue)
                    dp[d][l] = Math.Min(dp[d][l], dp[d - 1][i] + cost[i][l - i - 1]);
            return;
        }

        int mid = (l + r) / 2;
        int ob = -1;
        for (int i = ol; i <= or && i < mid; i++)
            if (dp[d - 1][i] < long.MaxValue && dp[d][mid] > dp[d - 1][i] + cost[i][mid - i - 1])
            {
                dp[d][mid] = dp[d - 1][i] + cost[i][mid - i - 1];
                ob = i;
            }

        Fun(d, l, mid - 1, ol, ob);
        Fun(d, mid + 1, r, ob, or);
    }

    public void Solve()
    {
        n = ReadInt();
        m = ReadInt();
        
        var x = new int[n];
        var a = new int[n];
        for (int i = 0; i < n; i++)
        {
            x[i] = ReadInt();
            a[i] = ReadInt();
        }

        //n = m = 5000;
        //x = Enumerable.Range(1, n).ToArray();
        //a = Enumerable.Range(1, n).ToArray();

        cost = new long[n][];
        for (int i = 0; i < n; i++)
        {
            cost[i] = new long[n - i];
            int p = i;
            long left = 0, right = 0, wleft = 0, wright = 0;
            for (int j = i + 1; j < n; j++)
            {
                wright += a[j];
                right += 1L * a[j] * (x[j] - x[p]);
                while (p < j)
                {
                    if (left + right < left + (wleft + a[p]) * (x[p + 1] - x[p]) + right - wright * (x[p + 1] - x[p]))
                        break;
                    wleft += a[p];
                    left += wleft * (x[p + 1] - x[p]);
                    right -= wright * (x[p + 1] - x[p]);
                    wright -= a[p + 1];
                    p++;
                }
                cost[i][j - i] = left + right;
            }
        }

        dp = new long[m + 1][];
        for (int i = 0; i <= m; i++)
        {
            dp[i] = new long[n + 1];
            for (int j = 0; j <= n; j++)
                dp[i][j] = long.MaxValue;
        }
        dp[0][0] = 0;

        for (int i = 1; i <= m; i++)
            Fun(i, i, n, i - 1, n - 1);
        //for (int i = 0; i < n; i++)
        //    for (int j = 0; j < m; j++)
        //        if (dp[i, j] < long.MaxValue)
        //            for (int k = i + 1; k <= n; k++)
        //                dp[k, j + 1] = Math.Min(dp[k, j + 1], dp[i, j] + cost[i, k - 1]);

        Write(dp[m][n]);
    }

    #region Main

    protected static TextReader reader;
    protected static TextWriter writer;
    static void Main()
    {
#if DEBUG
        reader = new StreamReader("..\\..\\input.txt");
        //reader = new StreamReader(Console.OpenStandardInput());
        writer = Console.Out;
        //writer = new StreamWriter("..\\..\\output.txt");
#else
        reader = new StreamReader(Console.OpenStandardInput());
        writer = new StreamWriter(Console.OpenStandardOutput());
        //reader = new StreamReader("input.txt");
        //writer = new StreamWriter("output.txt");
#endif
        try
        {
            new Solver().Solve();
            //var thread = new Thread(new Solver().Solve, 1024 * 1024 * 128);
            //thread.Start();
            //thread.Join();
        }
        catch (Exception ex)
        {
#if DEBUG
            Console.WriteLine(ex);
#else
            throw;
#endif
        }
        reader.Close();
        writer.Close();
    }

    #endregion

    #region Read / Write
    private static Queue<string> currentLineTokens = new Queue<string>();
    private static string[] ReadAndSplitLine() { return reader.ReadLine().Split(new[] { ' ', '\t', }, StringSplitOptions.RemoveEmptyEntries); }
    public static string ReadToken() { while (currentLineTokens.Count == 0)currentLineTokens = new Queue<string>(ReadAndSplitLine()); return currentLineTokens.Dequeue(); }
    public static int ReadInt() { return int.Parse(ReadToken()); }
    public static long ReadLong() { return long.Parse(ReadToken()); }
    public static double ReadDouble() { return double.Parse(ReadToken(), CultureInfo.InvariantCulture); }
    public static int[] ReadIntArray() { return ReadAndSplitLine().Select(int.Parse).ToArray(); }
    public static long[] ReadLongArray() { return ReadAndSplitLine().Select(long.Parse).ToArray(); }
    public static double[] ReadDoubleArray() { return ReadAndSplitLine().Select(s => double.Parse(s, CultureInfo.InvariantCulture)).ToArray(); }
    public static int[][] ReadIntMatrix(int numberOfRows) { int[][] matrix = new int[numberOfRows][]; for (int i = 0; i < numberOfRows; i++)matrix[i] = ReadIntArray(); return matrix; }
    public static int[][] ReadAndTransposeIntMatrix(int numberOfRows)
    {
        int[][] matrix = ReadIntMatrix(numberOfRows); int[][] ret = new int[matrix[0].Length][];
        for (int i = 0; i < ret.Length; i++) { ret[i] = new int[numberOfRows]; for (int j = 0; j < numberOfRows; j++)ret[i][j] = matrix[j][i]; } return ret;
    }
    public static string[] ReadLines(int quantity) { string[] lines = new string[quantity]; for (int i = 0; i < quantity; i++)lines[i] = reader.ReadLine().Trim(); return lines; }
    public static void WriteArray<T>(IEnumerable<T> array) { writer.WriteLine(string.Join(" ", array)); }
    public static void Write(params object[] array) { WriteArray(array); }
    public static void WriteLines<T>(IEnumerable<T> array) { foreach (var a in array)writer.WriteLine(a); }
    private class SDictionary<TKey, TValue> : Dictionary<TKey, TValue>
    {
        public new TValue this[TKey key]
        {
            get { return ContainsKey(key) ? base[key] : default(TValue); }
            set { base[key] = value; }
        }
    }
    private static T[] Init<T>(int size) where T : new() { var ret = new T[size]; for (int i = 0; i < size; i++)ret[i] = new T(); return ret; }
    #endregion
}

Mining Java Solution

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

Mining C Solution

Mining C++ Solution

Mining C Sharp Solution

Mining Java Solution

Related Posts