Table of Contents
Dorsey Thief – 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 <fstream>
#include <iostream>
#include <vector>
using namespace std;
int n, W;
#define LUNBUFFER 22000000
int letti = -1;
char buff[LUNBUFFER];
int fast_read_int() {
register int let, n = 0;
let = letti;
do let++;
while (buff[let] < '0');
do {
n = (n << 3) + (n << 1) + (buff[let++] - '0');
} while (buff[let] >= '0');
letti = let;
return n;
}
vector<int>wt, val;
// A utility function that returns
// maximum of two integers
long long max(long long a, long long b) { return (a > b) ? a : b; }
// we can further improve the above Knapsack function's space
// complexity
long long knapSack(int W, int n)//int wt[], int val[],
{
int i, w;
long long K[2][5000 + 1], r1, r2;
// We know we are always using the the current row or
// the previous row of the array/vector . Thereby we can
// improve it further by using a 2D array but with only
// 2 rows i%2 will be giving the index inside the bounds
// of 2d array K
for (i = 0; i <= n; i++) {
//for (w = 0; w <= W; w++) {
for (w = W; w >= 0; w--) {
if (i == 0) {
if (w == 0)
K[i % 2][w] = 0;
else
K[i % 2][w] = -2;
}
else
if (wt[i - 1] <= w) {
r1 = K[(i - 1) % 2][w - wt[i - 1]];
r2 = K[(i - 1) % 2][w];
if (r1 < 0 && r2 < 0)
K[i % 2][w] = -2;
else
K[i % 2][w] = max(val[i - 1] + r1, r2);
}
else
K[i % 2][w] = K[(i - 1) % 2][w];
}
}
return K[n % 2][W];
}
int main()
{
//freopen("input.txt", "r", stdin);
fread(buff, sizeof(char), LUNBUFFER, stdin);//_unlocked
//freopen("output.txt", "w", stdout);
n = fast_read_int();
W = fast_read_int();
//scanf("%d%d", &n, &W);
//cin >> n >> W;
wt.resize(n);
val.resize(n);
for (int i = 0; i < n; i++) {
val[i] = fast_read_int();
wt[i] = fast_read_int();
//scanf("%d%d", &val[i], &wt[i]);
}
//cin >> val[i] >> wt[i];
long long r = knapSack(W, n);
if (r == -2)
cout << "Got caught!";
else
cout << r;
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
BufferedReader br;
PrintWriter out;
StringTokenizer st;
boolean eof;
void solve() throws IOException {
int n = nextInt();
int x = nextInt();
long[] max = new long[x + 1];
Arrays.fill(max, -1);
max[0] = 0;
long freeBonus = 0;
List<Integer>[] byNeed = new List[x + 1];
for (int i = 1; i <= x; i++) {
byNeed[i] = new ArrayList<>(0);
}
for (int i = 0; i < n; i++) {
int gain = nextInt();
int need = nextInt();
if (need == 0) {
freeBonus += gain;
continue;
}
if (need <= x) {
byNeed[need].add(gain);
}
}
for (int need = 1; need <= x; need++) {
List<Integer> cur = byNeed[need];
Collections.sort(cur);
Collections.reverse(cur);
for (int i = 0; (i + 1) * need <= x && i < cur.size(); i++) {
int gain = cur.get(i);
for (int j = x; j >= need; j--) {
if (max[j - need] != -1) {
max[j] = Math.max(max[j], max[j - need] + gain);
}
}
}
}
if (max[x] == -1) {
out.println("Got caught!");
} else {
out.println(max[x] + freeBonus);
}
}
Solution() throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
solve();
out.close();
}
public static void main(String[] args) throws IOException {
new Solution();
}
String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
eof = true;
return null;
}
}
return st.nextToken();
}
String nextString() {
try {
return br.readLine();
} catch (IOException e) {
eof = true;
return null;
}
}
int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
}
Python 3 rep HackerRank Solution
Python 2 rep HackerRank Solution
import heapq
def make_money(stolen, offers_dict):
offers = [(weight, value) for (weight, values) in offers_dict.items() for value in values]
offers.sort(key=lambda (weight, value): (weight, -value))
chart = [None for _ in xrange(stolen+1)] # map weight to max value
chart[0] = 0
for (weight, value) in offers:
no_more_expansions = True
for chart_weight, chart_value in enumerate(chart[:]):
if chart_value == None:
continue
new_weight = weight + chart_weight
if new_weight > stolen:
break
no_more_expansions = False
new_value = value + chart_value
if chart[new_weight] == None:
chart[new_weight] = new_value
else:
chart[new_weight] = max(chart[new_weight], new_value)
if no_more_expansions:
break
if chart[stolen] != None:
return chart[stolen]
else:
return "Got caught!"
def add_offer(offers, (value, weight), stolen):
if weight <= stolen:
if weight in offers:
if len(offers[weight]) >= stolen / weight:
heapq.heappushpop(offers[weight], value)
else:
heapq.heappush(offers[weight], value)
else:
offers[weight] = [value]
def main():
passengers, stolen = map(int, raw_input().strip().split(" "))
offers = {}
for _ in xrange(passengers):
offer = tuple(map(int, raw_input().strip().split(" ")))
add_offer(offers, offer, stolen)
print make_money(stolen, offers)
def test_speed():
import random
import cProfile
passengers = 1000
stolen = 1000
random.seed(0)
input_offers = ((random.randint(0, stolen), random.randint(0, stolen)) for _ in xrange(passengers))
offers = {}
for input_offer in input_offers:
add_offer(offers, input_offer, stolen)
print 'start profile'
cProfile.runctx('make_money(stolen, offers)', {'stolen': stolen, 'offers': offers, 'make_money': make_money}, {})
def test_cases():
stolen = 10
input_offers = [(460, 4), (590, 6), (550, 5), (590, 5)]
offers = {}
for input_offer in input_offers:
add_offer(offers, input_offer, stolen)
result = make_money(stolen, offers)
assert result == 1140, 'result: %s' % result
stolen = 9
input_offers = [(100, 5), (120, 10), (300, 2), (500, 3)]
offers = {}
for input_offer in input_offers:
add_offer(offers, input_offer, stolen)
result = make_money(stolen, offers)
assert result == 'Got caught!', 'result: %s' % result
stolen = 10
input_offers = [(460, 5), (900, 5), (550, 5), (600, 5)]
offers = {}
for input_offer in input_offers:
add_offer(offers, input_offer, stolen)
result = make_money(stolen, offers)
assert result == 1500, 'result: %s' % result
print 'pass cases'
if __name__ == '__main__':
main()
#test_cases()
#test_speed()
C rep HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
void sort_a2(int*a,long long*b,int size);
void merge2(int*a,int*left_a,int*right_a,long long*b,long long*left_b,long long*right_b,int left_size, int right_size);
int main(){
int N,X,i,j,k,*a,len,*index;
long long *dp,temp,*v;
scanf("%d%d",&N,&X);
a=(int*)malloc(N*sizeof(int));
v=(long long*)malloc(N*sizeof(long long));
dp=(long long*)malloc((X+1)*sizeof(long long));
index=(int*)malloc((X+1)*sizeof(int));
for(i=1;i<=X;i++){
dp[i]=-1;
index[i]=-1;
}
dp[0]=0;
for(i=0;i<N;i++)
scanf("%lld%d",v+i,a+i);
sort_a2(a,v,N);
for(i=0;i<N && a[i]<=X;i++)
if(i==0 || a[i]!=a[i-1])
index[a[i]]=i;
for(i=1;i<=X;i++){
if(index[i]==-1)
continue;
len=X/a[index[i]]+index[i];
for(k=index[i];k<len && k<N;k++){
if(k!=index[i] && a[k]!=a[k-1])
break;
for(j=X;j>=a[k];j--){
temp=(dp[j-a[k]]==-1)?-1:dp[j-a[k]]+v[k];
if(temp>dp[j])
dp[j]=temp;
}
}
}
if(dp[X]!=-1)
printf("%lld",dp[X]);
else
printf("Got caught!");
return 0;
}
void sort_a2(int*a,long long*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left_a,*right_a;
long long *left_b,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(long long*)malloc(m*sizeof(long long));
right_b=(long long*)malloc((size-m)*sizeof(long long));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,long long*b,long long*left_b,long long*right_b,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] < right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] == right_a[j]) {
if (left_b[i] <= right_b[j]) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
else{
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
}
}else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
