Table of Contents
Oil Well – 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 <iostream>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <stdint.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <bitset>
#include <deque>
#include <list>
#include <stack>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define forn(i, n) for(int i = 0; i < int(n); ++i)
#define foreach(it, v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
#define sz(v) int((v).size())
const int max_n = 50, inf = 1e9;
bool is_oil[max_n][max_n];
bool used[max_n][max_n][max_n][max_n];
int d[max_n][max_n][max_n][max_n];
inline int get_penalty(int x0, int y0, int x1, int y1, int x, int y) {
return max(max(abs(x - x0), abs(x - x1)), max(abs(y - y0), abs(y - y1)));
}
int rec(int x0, int y0, int x1, int y1, int n, int m) {
assert(x0 <= x1 && x0 >= 0 && x1 < n);
assert(y0 <= y1 && y0 >= 0 && y1 < m);
if(used[x0][y0][x1][y1]) {
return d[x0][y0][x1][y1];
}
int result = inf;
if(x0 == 0 && y0 == 0 && x1 == n - 1 && y1 == m - 1) {
result = 0;
} else {
if(x0 > 0) {
int add = 0;
for(int y = y0; y <= y1; y++) {
if(is_oil[x0 - 1][y]) {
add += get_penalty(x0 - 1, y0, x1, y1, x0 - 1, y);
}
}
result = min(result, add + rec(x0 - 1, y0, x1, y1, n, m));
}
if(y0 > 0) {
int add = 0;
for(int x = x0; x <= x1; x++) {
if(is_oil[x][y0 - 1]) {
add += get_penalty(x0, y0 - 1, x1, y1, x, y0 - 1);
}
}
result = min(result, add + rec(x0, y0 - 1, x1, y1, n, m));
}
if(x1 + 1 < n) {
int add = 0;
for(int y = y0; y <= y1; y++) {
if(is_oil[x1 + 1][y]) {
add += get_penalty(x0, y0, x1 + 1, y1, x1 + 1, y);
}
}
result = min(result, add + rec(x0, y0, x1 + 1, y1, n, m));
}
if(y1 + 1 < m) {
int add = 0;
for(int x = x0; x <= x1; x++) {
if(is_oil[x][y1 + 1]) {
add += get_penalty(x0, y0, x1, y1 + 1, x, y1 + 1);
}
}
result = min(result, add + rec(x0, y0, x1, y1 + 1, n, m));
}
}
used[x0][y0][x1][y1] = true;
return d[x0][y0][x1][y1] = result;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
bool empty = true;
forn(i, n) {
forn(j, m) {
int k;
scanf("%d", &k);
is_oil[i][j] = (k == 1);
if(is_oil[i][j]) {
empty = false;
}
}
}
int result = (empty) ? 0 : inf;
forn(i, n) {
forn(j, m) {
if(is_oil[i][j]) {
result = min(result, rec(i, j, i, j, n, m));
}
}
}
printf("%d\n", result);
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static int dist(int x1,int y1,int x2,int y2) {
int x = x1 - x2, y = y1 - y2;
if (x < 0) {
x = -x;
}
if (y < 0) {
y = -y;
}
return (x > y)?x:y;
}
public static int cost(int x,int y,int x1,int y1,int x2,int y2) {
int d1 = dist(x,y,x1,y1), d2 = dist(x,y,x2,y2);
return (d1 > d2)?d1:d2;
}
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner scanner = new Scanner(System.in);
int row = scanner.nextInt(), col = scanner.nextInt();
int [][] a = new int [row][col];
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
a[i][j] = scanner.nextInt();
}
}
int[][][][] result = new int [row][col][row][col];
for (int x1 = row - 1; x1 >= 0; --x1) {
for (int y1 = col - 1; y1 >= 0; --y1) {
for (int x2 = x1; x2 < row; ++x2) {
for (int y2 = (x1 == x2)?(y1 + 1):y1; y2 < col; ++y2) {
result[x1][y1][x2][y2] = 1000000000;
if (x1 < x2) {
int temp = result[x1 + 1][y1][x2][y2];
for (int y = y1; y <= y2; ++y) {
if (a[x1][y] == 1) {
temp += cost(x1, y, x1 + 1, y1, x2, y2);
}
}
if (result[x1][y1][x2][y2] > temp) {
result[x1][y1][x2][y2] = temp;
}
temp = result[x1][y1][x2 - 1][y2];
for (int y = y1; y <= y2; ++y) {
if (a[x2][y] == 1) {
temp += cost(x2, y, x1 ,y1, x2 - 1, y2);
}
}
if (result[x1][y1][x2][y2] > temp) {
result[x1][y1][x2][y2] = temp;
}
}
if (y1 < y2) {
int temp = result[x1][y1 + 1][x2][y2];
for (int x = x1; x <= x2; ++x) {
if (a[x][y1] == 1) {
temp += cost(x, y1, x1, y1 + 1, x2, y2);
}
}
if (result[x1][y1][x2][y2] > temp) {
result[x1][y1][x2][y2] = temp;
}
temp = result[x1][y1][x2][y2 - 1];
for (int x = x1; x <= x2; ++x) {
if (a[x][y2] == 1) {
temp += cost(x, y2, x1, y1, x2, y2 - 1);
}
}
if (result[x1][y1][x2][y2] > temp) {
result[x1][y1][x2][y2] = temp;
}
}
}
}
}
}
System.out.println(result[0][0][row - 1][col - 1]);
}
}
Python 3 rep HackerRank Solution
r, c = list(map(int, input().strip().split()))
n = max(r, c)
g = [[0]*n for i in range(n)]
for i in range(r):
bs = list(map(int, input().strip().split()))
for j in range(c):
g[i][j] = bs[j]
x = [[0]*(n+1) for i in range(n+1)]
for i in range(n):
for j in range(n):
x[i+1][j+1] = x[i+1][j] + x[i][j+1] - x[i][j] + g[i][j]
fs = g
fz = [[0]*n for i in range(n)]
ans = [[0]*n for i in range(n)]
anz = [[0]*n for i in range(n)]
for d in range(1,n):
for i in range(n-d):
I = i + d + 1
for j in range(n-d):
J = j + d + 1
total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
anz[i][j] = min(
ans[i ][j ] + d*(total - fs[i ][j ]),
ans[i ][j+1] + d*(total - fs[i ][j+1]),
ans[i+1][j ] + d*(total - fs[i+1][j ]),
ans[i+1][j+1] + d*(total - fs[i+1][j+1]),
)
ans, anz = anz, ans
fs, fz = fz, fs
print (ans[0][0])
Python 2 rep HackerRank Solution
r, c = map(int, raw_input().strip().split())
n = max(r, c)
g = [[0]*n for i in xrange(n)]
for i in xrange(r):
bs = map(int, raw_input().strip().split())
for j in xrange(c):
g[i][j] = bs[j]
x = [[0]*(n+1) for i in xrange(n+1)]
for i in xrange(n):
for j in xrange(n):
x[i+1][j+1] = x[i+1][j] + x[i][j+1] - x[i][j] + g[i][j]
fs = g
fz = [[0]*n for i in xrange(n)]
ans = [[0]*n for i in xrange(n)]
anz = [[0]*n for i in xrange(n)]
for d in xrange(1,n):
for i in xrange(n-d):
I = i + d + 1
for j in xrange(n-d):
J = j + d + 1
total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
anz[i][j] = min(
ans[i ][j ] + d*(total - fs[i ][j ]),
ans[i ][j+1] + d*(total - fs[i ][j+1]),
ans[i+1][j ] + d*(total - fs[i+1][j ]),
ans[i+1][j+1] + d*(total - fs[i+1][j+1]),
)
ans, anz = anz, ans
fs, fz = fz, fs
print ans[0][0]
C rep HackerRank Solution
#include <stdio.h>
int a[55][55][55][55],b[55][55],t,i,j,k,l,m,n,r,c,dy,dx;
int z[55][55][55],v[55][55][55],u;
int main()
{
scanf("%d %d", &r, &c);
for(i=0;i<r;i++)
for(j=0;j<c;j++)
scanf("%d",&b[i][j]);
for(i=0;i<c;i++)
for(j=0;j<r;j++)
{
z[j][j][i] = b[j][i];
for(k=j+1;k<r;k++) z[j][k][i] = z[j][k-1][i] + b[k][i];
}
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
v[i][j][j] = b[i][j];
for(k=j+1;k<c;k++) v[i][j][k] = v[i][j][k-1] + b[i][k];
}
/*
for(i=0;i<r;i++)
for(k=0;k<r;k++)
for(j=0;j<c;j++)
for(l=j;l<c;l++)
*/
u = -1;
for(dy=0;dy<r;dy++)
for(dx=0;dx<c;dx++)
for(i=0;i+dy<r;i++)
for(j=0;j+dx<c;j++)
/*
for(dy=0;dy<2;dy++)
for(dx=0;dx<2;dx++)
for(i=0;i+dy<2;i++)
for(j=0;j+dx<2;j++)
*/
{
k = i+dy;
l = j+dx;
m = 2000000000;
if(k==i && l==j) m = 0;
if(k-i >= l-j && k-i > 0)
{
t = a[i+1][j][k][l];
if(v[k][j][l])
{
t += v[i][j][l]*(k-i);
if(t<m) m = t;
}
t = a[i][j][k-1][l];
if(v[i][j][l])
{
t += v[k][j][l]*(k-i);
if(t<m) m = t;
}
}
// printf("prve m %d\n",m);
if(k-i <= l-j && l-j > 0)
{
t = a[i][j+1][k][l];
if(z[i][k][l])
{
t += z[i][k][j]*(l-j);
if(t<m) m = t;
}
t = a[i][j][k][l-1];
if(z[i][k][j])
{
t += z[i][k][l]*(l-j);
if(t<m) m = t;
}
}
a[i][j][k][l] = m;
if(m!=2000000000 && m > u) u = m;
// if(m)
// printf("%d %d %d %d -> %d\n",i,j,k,l,m);
}
/*
for(i=0;i<r;i++)
for(j=0;j<c;j++)
for(k=j;k<c;k++)
printf("v %d %d %d -> %d\n", i,j,k, v[i][j][k]);
*/
/*
for(j=0;j<c;j++)
for(i=0;i<r;i++)
for(l=i;l<r;l++)
printf("z %d %d %d -> %d\n", i,l,j, z[i][l][j]);
*/
//k = a[0][0][r-1][c-1];
if(u<0) u = 0;
printf("%d\n",u);
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
