Table of Contents
The Blacklist – 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
#define TRACE
#define DEBUG
#include <algorithm>
#include <bitset>
#include <deque>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<string> vs;
// Basic macros
#define st first
#define se second
#define all(x) (x).begin(), (x).end()
#define ini(a, v) memset(a, v, sizeof(a))
#define re(i,s,n) for(int i=s;i<(n);++i)
#define rep(i,s,n) for(int i=s;i<=(n);++i)
#define fr(i,n) re(i,0,n)
#define repv(i,f,t) for(int i = f; i >= t; --i)
#define rev(i,f,t) repv(i,f - 1,t)
#define frv(i,n) rev(i,n,0)
#define pu push_back
#define mp make_pair
#define sz(x) (int)(x.size())
const int oo = 1000000009;
const double eps = 1e-9;
#ifdef TRACE
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#else
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)
#endif
int n, k;
const int mx = 25;
int a[mx], b[mx], c[mx][mx];
int dp[mx][(1 << 10) + 10];
int solve(int i, int mask) {
if(i == n) return 0;
if(mask == (1 << k) - 1) return oo;
int &ret = dp[i][mask];
if(ret != -1) return ret;
ret = oo;
fr(nxt, k) if((mask & (1 << nxt)) == 0) {
int cur = 0;
re(j, i, n) {
cur += c[nxt][j];
ret = min(ret, cur + solve(j + 1, mask | (1 << nxt)));
}
}
return ret;
}
int main() {
scanf("%d %d", &n, &k);
fr(i, k) {
fr(j, n) scanf("%d", &c[i][j]);
}
ini(dp, -1);
printf("%d\n", solve(0, 0));
return 0;
}
Java rep HackerRank Solution
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int N = input.nextInt();
int K = input.nextInt();
int[][] price = new int[K][N];
for (int k=0; k<K; k++) {
for (int n=0; n<N; n++) {
price[k][n] = input.nextInt();
}
}
int limit = 1<<K;
int[][] dp = new int[N+1][limit+1];
for (int n=0; n<=N; n++) {
for (int x=0; x<=limit; x++) {
dp[n][x] = 1000000;
}
}
dp[0][0] = 0;
for (int n=1; n<=N; n++) {
for (int k=0; k<K; k++) {
int mask = 1 << k;
for (int from=1; from<=n; from++) {
for (int x=0; x<limit; x++) {
if ((x&mask) == 0) {
int newMask = x|mask;
int newValue = dp[from-1][x];
for (int i=from; i<=n; i++) {
newValue += price[k][i-1];
}
if (dp[n][newMask] > newValue) {
dp[n][newMask] = newValue;
}
}
}
}
}
}
int min = Integer.MAX_VALUE;
for (int value : dp[N]) {
min = Math.min(min, value);
}
System.out.println(min);
}
}
Python 3 rep HackerRank Solution
def bits_free(x, K):
res = []
for i in range(K):
if x % 2 == 0:
res.append(i)
x //= 2
return res
N, K = tuple(int(s) for s in input().strip().split())
costs = []
for i in range(K):
costs1 = [int(s) for s in input().strip().split()]
costs.append(costs1)
#print(costs)
dpmat = [[[1000000 for i in range(2**K)] for j in range(K)] for k in range(N)]
for mer in range(K):
dpmat[0][mer][1 << mer] = costs[mer][0]
#print(dpmat)
for gan in range(1,N):
for lastmer in range(K):
for mask in range(2**K):
if dpmat[gan-1][lastmer][mask] >= 1000000:
continue
dpmat[gan][lastmer][mask] = min(dpmat[gan][lastmer][mask], dpmat[gan-1][lastmer][mask] + costs[lastmer][gan])
for newmer in bits_free(mask, K):
newmask = mask | (1 << newmer)
dpmat[gan][newmer][newmask] = min(dpmat[gan][newmer][newmask], dpmat[gan-1][lastmer][mask] + costs[newmer][gan])
best = 1000000
for lastmer in range(K):
for mask in range(2**K):
if dpmat[N-1][lastmer][mask] < 0:
continue
best = min(best, dpmat[N-1][lastmer][mask])
#print(dpmat)
print(best)
Python 2 rep HackerRank Solution
#I want to use a dynamic program to solve this, since there are
#approximately 29!/20! or about 1.5*10^13 ways to arrange the
#mercenaries (with a slight overcounting of cases where not all
#mercenaries are used)
#I will traverse the list of enemies from start to finish. I will
#keep track of states which represent the mercenaries no longer
#available (2^10-1 cases, since the last guy used always remains
#available) x the last guy used, for about 10,000 active cases.
#For each mercenary and each case, consider the result if each
#available mercenary kills the next enemy, and store the one with
#the least cost in that state.
n,k=map(int,raw_input().strip().split())
costs=[]
for j in xrange(k):
costs.append(map(int,raw_input().strip().split()))
states={}
#initial state, last mercenary used is -1 to indicate none
states[(True,)*k+(-1,)]=0
for i in xrange(n):
newstates={}
for state in states:
for j in xrange(k):
#if mercenary j is still available
if state[j]:
#generate new state if he kills enemy i
nstate=list(state)
nstate[-1]=j
if state[-1]!=-1 and state[-1]!=j:
nstate[state[-1]]=False
nstate=tuple(nstate)
cost=states[state]+costs[j][i]
if nstate in newstates:
if cost<newstates[nstate]:
newstates[nstate]=cost
else:
newstates[nstate]=cost
states=newstates
#find cheapest result
cheapest=200001
for state in states:
if states[state]<cheapest:
cheapest=states[state]
print cheapest
C rep HackerRank Solution
#include <stdio.h>
#define set(c,d) ((1<<d)|(c))
#define isSet(c,d) ((1<<d)&(c))
int n, k;
int a[20][20];
int memo[20][20][2050];
int bestwithout(int i, int j, int without) {
int best;
int cp, x;
if(i == 0) {
// printf("best[%d][%d]: %d\n", i, j, a[i][j]);
return a[i][j];
}
cp = memo[i][j][without];
if(cp != -1) {
// puts("MEMO found!");
return cp;
}
best = bestwithout(i-1, j, without);
for(x=0;x<k;x++) {
if(!isSet(without,x)) {
cp = bestwithout(i-1, x, set(without,x));
if(cp < best)
best = cp;
}
}
// printf("best[%d][%d][%d]: %d\n", i, j, without, best);
best += a[i][j];
memo[i][j][without] = best;
return best;
}
int main(void) {
int i, j, h, cp, best;
scanf("%d %d", &n, &k);
//printf("%d %d\n", n, k);
for(i=0;i<k;i++)
for(j=0;j<n;j++)
scanf("%d", &a[j][i]);
//printf("%d\n", a[n-1][0]);
for(i=0;i<20;i++)
for(j=0;j<20;j++)
for(h=0;h<2050;h++)
memo[i][j][h] = -1;
best = bestwithout(n-1, 0, set(0,0));
for(i=1;i<k;i++) {
cp = bestwithout(n-1, i, set(0,i));
if(cp < best)
best = cp;
}
printf("%d\n", best);
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
