HackerRank The Indian Job Problem Solution
In this Post, we will solve HackerRank The Indian Job Problem Solution.
It is the Indian version of the famous heist “The Italian Job”. N robbers have already broken into the National Museum and are just about to get inside the main vault which is full of jewels. They were lucky that just as they broke into the museum, the guard was leaving the museum for exactly G minutes. But there are other problems too. The main vault has heat sensors that if at any moment of time there are more than two people present in the vault, the alarm goes off.
To collect the jewels, the ith robber needs to be inside the vault for exactly A[i] minutes, 0 <= i < N, in one continuous stretch. As guard will return after G minutes, they have to finish their tasks within G minutes. The robbers want to know if there exists any arrangement such that demands of each robber is satisfied and also they are not caught?
Gotchas
If a robber goes inside the vault at a time “X” and at the same time another robber comes out, it’s equivalent to saying they were never in the vault at the same time.
Similarly, when the guard gets inside vault at time G and a robber comes out exactly at time G, the guard will not be able see the robber.
Input Format
The first line contains an integer T denoting the number of testcases. T testcases follow. Each testcase consists of two lines. First line contains two space separated integers denoting N and G denoting the number of thieves and duration for which guard leaves the museum.
The next line contains N space separated numbers where the ith integer, A[i] represents the time the ith robber needs to be in the vault.
Constraints
1 <= T <= 20
1 <= N <= 100
0 <= G <= 1000000 (106)
0 <= A[i] <= 100
Output Format
For each testcase print YES if there exists such an arrangement or NO otherwise in a newline.
Sample Input
2
3 4
2 4 2
3 2
2 4 2
Sample Output
YES
NO
Explanation
Test case #00: In first testcase, one possible arrangement is:
at t=0, robber1 goes inside and comes out at t=2
at t=0, robber2 goes inside and comes out at t=4
at t=2, robber3 goes inside and comes out at t=4
Test case #01: No possible arrangement is possible in second testcase.
The Indian Job C Solution
#include<stdio.h>
#include<math.h>
int knapsack(int N, int G,int A[]);
int max(int a,int b);
int main(){
int T, N, G;
scanf("%d", &T);
while(T>0) {
scanf("%d %d", &N, &G);
int A[N],total=0;
for(int i = 0; i < N; i++) {
scanf("%d", &A[i]);
total+=A[i];
}
int k = knapsack(N,G,A);
if(total >G*2)
printf("NO\n");
else if(total-k<=G)
printf("YES\n");
else
printf("NO\n");
T--;
}
return 0;
}
int max(int a,int b){
if(a>b)
return a;
else
return b;
}
int knapsack(int N, int G,int A[]) {
int DP[N+1][G+1] ;
for(int i = 0; i <= N; i++) {
for(int w = 0; w <= G; w++) {
if(i == 0 || w == 0)
DP[i][w] = 0;
else if(A[i - 1] > w)
DP[i][w] = DP[i - 1][w];
else
DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - A[i - 1]] + A[i - 1]);
}
}
return DP[N][G];
}The Indian Job C++ Solution
#include <bits/stdc++.h>
using namespace std;
int main() { int T; cin >> T; while(T-->0) {
int n, g; cin >> n >> g;
int tot = 0;
vector<int> ws(n); for (int i=0;i<n;++i) { cin >> ws[i]; tot += ws[i]; }
vector<vector<int>> dp(n+1,vector<int>(10000+1,-1));
function<int(int,int)> dfs = [&] (int n, int w) {
int& ans = dp[n][w];
if (ans != -1) return ans;
if (n == 0) ans = (w==0);
else {
ans = dfs(n - 1, w);
if (ws[n-1] <= w)
ans |= dfs(n - 1, w - ws[n - 1]);
}
return ans;
};
int minval = tot / 2;
int maxval = min(g, tot);
bool f = false;
for (int w = maxval; w >= minval; --w) {
if (dfs(n, w)) { f = true; break; }
}
if (f) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}}The Indian Job C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
/*
* Complete the indianJob function below.
*/
static string indianJob(int g, int[] arr) {
var total = arr.Sum(a => (long)a);
var n = arr.Length;
if (total / 2 > g)
return "NO";
var sum = new bool[g+1];
var max = 0;
sum[0] = true;
for(int i=0; i<n; i++) {
var time = arr[i];
if (time == 0)
continue;
for(int s=g-time; s>=0; s--)
if (sum[s]) {
sum[s+time] = true;
max = Math.Max(max, s+time);
//Console.WriteLine(s+time);
}
}
if (total - max > g)
return "NO";
return "YES";
}
static void Main(string[] args) {
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int t = Convert.ToInt32(Console.ReadLine());
for (int tItr = 0; tItr < t; tItr++) {
string[] ng = Console.ReadLine().Split(' ');
int n = Convert.ToInt32(ng[0]);
int g = Convert.ToInt32(ng[1]);
int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), arrTemp => Convert.ToInt32(arrTemp))
;
string result = indianJob(g, arr);
textWriter.WriteLine(result);
}
textWriter.Flush();
textWriter.Close();
}
}The Indian Job Java Solution
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
/*
* Complete the indianJob function below.
*/
static String indianJob(int g, int[] arr) {
/*
* Write your code here.
*/
int n = arr.length;
int[][] dp = new int[n+1][g+1];
int sum = 0;
for (int i=0; i<n; i++ )
{
sum += arr[i];
}
for (int i=1; i<=n; i++)
for (int j=1; j<=g; j++)
if (arr[i-1] <= j)
dp[i][j] = Math.max(dp[i-1][j],
arr[i-1] + dp[i-1][j-arr[i-1]]);
else
dp[i][j] = dp[i-1][j];
if(sum-dp[n][g] <= g) {
return "YES";
} else {
return "NO";
}
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = Integer.parseInt(scanner.nextLine().trim());
for (int tItr = 0; tItr < t; tItr++) {
String[] ng = scanner.nextLine().split(" ");
int n = Integer.parseInt(ng[0].trim());
int g = Integer.parseInt(ng[1].trim());
int[] arr = new int[n];
String[] arrItems = scanner.nextLine().split(" ");
for (int arrItr = 0; arrItr < n; arrItr++) {
int arrItem = Integer.parseInt(arrItems[arrItr].trim());
arr[arrItr] = arrItem;
}
String result = indianJob(g, arr);
bufferedWriter.write(result);
bufferedWriter.newLine();
}
bufferedWriter.close();
}
}The Indian Job JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the indianJob function below.
*/
function indianJob(g, arr) {
let arrSum = arr.reduce((a, b) => a + b, 0)
if (arrSum > 2 * g) return "NO"
const sumList = Array(arrSum).fill(0)
sumList[0] = 1
for (let i = 0; i < arr.length; i++) {
for (let j = sumList.length - 1; j >= 0; j--) {
if (sumList[j]) sumList[arr[i] + j] = 1
}
}
console.log(sumList)
for (let i = Math.ceil((arrSum / 2)); i < Math.min(g, arrSum) + 1; i++) {
if (sumList[i]) return "YES"
}
return "NO"
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const t = parseInt(readLine(), 10);
for (let tItr = 0; tItr < t; tItr++) {
const ng = readLine().split(' ');
const n = parseInt(ng[0], 10);
const g = parseInt(ng[1], 10);
const arr = readLine().split(' ').map(arrTemp => parseInt(arrTemp, 10));
let result = indianJob(g, arr);
ws.write(result + "\n");
}
ws.end();
}The Indian Job Python Solution
num_tests = int(input())
for _ in range(num_tests):
num_thieves, duration = map(int, input().split())
thief_times = [int(i) for i in input().split()]
total_thief_time = sum(thief_times)
if total_thief_time > 2 * duration:
print("NO")
continue
if total_thief_time < duration:
print("YES")
continue
prev_can_sum_to = [True] + [False] * duration
for time in thief_times:
can_sum_to = [True]
for i in range(1, duration + 1):
can_sum_to.append(prev_can_sum_to[i] or (i - time >= 0 and prev_can_sum_to[i - time]))
prev_can_sum_to = can_sum_to
if any(can_sum_to[total_thief_time - duration:]):
print("YES")
else:
print("NO")
