Table of Contents
Mining – 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 <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge
#ifdef DONLINE_JUDGE
// palindromic tree is better than splay tree!
#define lld I64d
#endif
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(10);
int N,K;
cin >> N >> K;
vector<long long> W(N),X(N);
for(int i =0; i < N; i++) cin >> X[i] >> W[i];
vector<long long> sumW(N+1,0),sumWX(N+1,0);
for(int i =0; i < N; i++) sumW[i+1] =sumW[i]+W[i], sumWX[i+1] =sumWX[i]+W[i]*X[i];
vector< vector<long long> > ansL(K+1,vector<long long>(N+1,OVER9000));
vector< vector<long long> > ansR(K+1,vector<long long>(N+1,OVER9000));
ansR[0][0] =0;
for(int i =0; i < N; i++) for(int k =0; k < K; k++) {
if(K-k > N-i+3) continue;
if(k > i+3) break;
for(int j =i; j >= 0; j--) {
ansL[k+1][i+1] =min(ansL[k+1][i+1],(ansR[k][j]+sumWX[j])-sumW[j]*X[i]);
if(sumWX[j]-sumW[j]*X[i] > ansL[k+1][i+1]) break;}
ansL[k+1][i+1] +=sumW[i+1]*X[i]-sumWX[i+1];
for(int j =i; j >= 0; j--) {
ansR[k+1][i+1] =min(ansR[k+1][i+1],(ansL[k+1][j+1]+X[j]*sumW[j]-sumWX[j])-X[j]*sumW[i+1]);
if(X[j]*sumW[j]-sumWX[j]-X[j]*sumW[i+1] > ansR[k+1][i+1]) break;}
ansR[k+1][i+1] +=sumWX[i+1];
}
cout << ansR[K][N] << "\n";
return 0;}
// look at my code
// my code is amazing
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
public class CodeSprintJuly16qF {
static int l, g;
static long x[], w[];
static long dp[][], cost[][], left[][], right[][];
static long prefix[];
static long inf = (long)1e17;
public static void main(String args[]) {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
l = in.nextInt();
g = in.nextInt();
x = new long[l + 1];
w = new long[l + 1];
prefix = new long[l + 1];
for (int i = 1; i <= l; i++) {
x[i] = in.nextInt();
w[i] = in.nextInt();
prefix[i] = prefix[i - 1] + w[i];
}
left = new long[l + 1][l + 1];
right = new long[l + 2][l + 2];
for (int i = 1; i <= l; i++) {
for (int j = i + 1; j <= l; j++) {
left[i][j] = left[i][j - 1] + (x[j] - x[i]) * 1L * w[j];
}
for (int j = i - 1; j >= 1; j--) {
right[i][j] = right[i][j + 1] + (x[i] - x[j]) * 1L * w[j];
}
}
cost = new long[l + 1][l + 1];
dp = new long[g + 1][l + 1];
for (int i = 0; i <= l; i++)
dp[0][i] = inf;
int best = 1;
for (int i = 2; i <= l; i++) {
/*while (best < i) {
long newCost = right[best + 1][1] + left[best + 1][i];
long oldCost = right[best][1] + left[best][i];
if (newCost < oldCost)
best++;
else
break;
}
cost[0][i] = right[best][1] + left[best][i];*/
cost[0][i] = dp[1][i] = right[i][1];
}
for (int i = 1; i <= l; i++) {
best = i;
for (int j = i; j <= l; j++) {
while (best < j && cost(i, best + 1, j) < cost(i, best, j))
best++;
cost[i][j] = cost(i, best, j);
//System.out.println("cost " + i + " " + j + " " + best + " " + cost[i][j]);
}
}
for (int d = 2; d <= g; d++)
go(d, 1, l, 0, l);
long ans = inf;
for (int last = 1; last <= l; last++)
ans = Math.min(ans, dp[g][last] + left[last][l]);
out.println(ans);
out.close();
}
static long cost(int i, int mid, int j) {
return left(i, mid) + right(mid + 1, j);
}
static long left(int i, int j) {
return left[i][j];
}
static long right(int i, int j) {
return right[j][i];
}
static void go(int d, int s, int e, int optL, int optR) {
if (s > e)
return;
int m = (s + e) >> 1, best = -1;
dp[d][m] = inf;
for (int i = optL; i <= optR && i < m; i++) {
if (dp[d - 1][i] + cost(i, m) < dp[d][m]) {
//if (d == 2 && m == 5)
//System.out.println("yyy " + i + " " + dp[d - 1][i] + " " + cost(i, m));
dp[d][m] = dp[d - 1][i] + cost(i, m);
best = i;
}
}
//System.out.println("xxx " + d + " " + m + " " + dp[d][m]);
go(d, s, m - 1, optL, best);
go(d, m + 1, e, best, optR);
}
static long cost(int i, int j) {
return cost[i][j];
}
static class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int snext() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = snext();
while (isSpaceChar(c)) {
c = snext();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = snext();
while (isSpaceChar(c)) {
c = snext();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String readString() {
int c = snext();
while (isSpaceChar(c)) {
c = snext();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = snext();
} while (!isSpaceChar(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
}
Python 3 rep HackerRank Solution
Python 2 rep HackerRank Solution
C rep HackerRank Solution
#include <stdio.h>
#define MAX 5001
typedef struct _Mine {
int x;
int w;
} Mine;
int n;
int k;
Mine mines[MAX];
long long int ranges[MAX][MAX];
long long int score[MAX][MAX];
void calculateRanges()
{
int i;
int j;
int ki;
int wl;
int wr;
long long int tmp;
for (i = 0; i < n; ++i) {
ranges[i][i] = 0;
}
for (i = 0; i < n; ++i) {
ki = i;
wl = 0;
wr = 0;
for (j = i + 1; j < n; ++j) {
ranges[i][j] = ranges[i][j-1] + (long long int) mines[j].w * (mines[j].x - mines[ki].x);
wr += mines[j].w;
while (ki < j) {
tmp = ranges[i][j] + ((long long int) (wl + mines[ki].w) * (mines[ki+1].x - mines[ki].x)) - ((long long int) wr * (mines[ki+1].x - mines[ki].x));
if (ranges[i][j] < tmp) {
break;
}
ranges[i][j] = tmp;
wr -= mines[ki+1].w;
wl += mines[ki].w;
ki += 1;
}
}
}
}
long long int calculateCost()
{
int i;
int j;
int l;
int index;
for (i = 0; i < n; ++i) {
score[i][1] = ranges[0][i];
}
for (i = 2; i <= k; ++i) {
index = 0;
for (j = i-1; j < n; ++j) {
score[j][i] = score[index][i-1] + ranges[index+1][j];
for (l = index+1; l < j; ++l) {
if (score[l][i-1] + ranges[l+1][j] < score[j][i]) {
score[j][i] = score[l][i-1] + ranges[l+1][j];
index = l;
}
}
}
}
return score[n-1][k];
}
int main() {
int i;
long long int res;
scanf("%d %d", &n, &k);
for (i = 0; i < n; ++i) {
scanf("%d %d", &mines[i].x, &mines[i].w);
}
calculateRanges();
res = calculateCost();
printf("%lld\n", res);
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
