Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Solution to Amazing-test problem from hackerearth

#Problem

The essence of the problem is given a collection of n items of varying size, let Tsum be the sum of all item sizes. we need to able to answer the question, does a subset of items exist such that the sum of the items in the sumset is equal to K. where K is some integer that satisfies the constraints K <= Tmax and (total-K) <= Tmax . Where Tmax is the maximum time allowed.

#Solution

Brute force approach would be iterate through all the subsets of the items.

Let S1, S2 ... S2n all subsets, we iterate through each subset to see if there exist a subset Sk such that the sum of Sk = K. This approach is guarenteed to be correct, however it is impossibly slow because we have to iterate 2n subsets. since the number of items in the collection can reach 100, in the worst case we would have to examine 2100 subsets this is clearly intractable.

Another way to approach this is take advantage of the fact that the size of any item is not going to exceed 100, and we only have at the most 100 of these items. The total sum of sizes cannot exceed 10000. Given all subsets generated, there can only be at the most 10000 unique sums generated by these subsets. Let Ti be the sum of all items in subset Si , if a solution exists , there must be some Ti , where Ti <= Tmax and (Tsum -Ti) <= Tmax. We also know that for any subset si the sum Si is in the range 0<= Si <= Totalset <= 10000.

Now to solve the problem we just need to find, the different sums that can be generated by the subsets. Let A be the collection of items, A[i] being the cost of the ith item. if there is just a single item in A, unique sums generated is [0,A[i]] , let S(n-1) be the set of all the unique sums generated by all subset of n-1 items, suppose we are given this can we extend it to find all unique sums generated by subsets of n items ?

if A[n] is the cost of nth item , then


S(n) = S(n-1) union [ s+A[n] for s in S(n-1) ]

Given we know all sums generated by subsets of n items, we iterate throung each k and check if there exists a subset si such that has a sum(Si) = k and (k <= Tmax and (Totalset - k) <= Tmax) . This is clearly tractable since the search space is just 10000 * 100 in the worst case. Which an easily be computed in the given time limits.

 
for i in 1 to n:
    for k in 0 to Totalmax :
        if exist_subset(i, k) and  (k <= Tmax and (Totalset - k) <= Tmax)          
            return True
return False    

#Implementation

An optimization would be to check if K exists while we are generating the Set of unique sums. We use a BitArray as our set implementation, kth is set if , there exist a subset with sum k.

Final code in C# is given below

using System;
using System.Linq;
using System.Collections;
class MyClass
{
static void Main(string[] args)
{
int t = int.Parse(Console.ReadLine())
string line = null;
do
{
line = Console.ReadLine();
var countTime = line.Split(' ');
var maxtime = int.Parse(countTime[1]);
var items = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
if(CanFill(items,maxtime))
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}
t--;
} while (t > 0);
}
private static bool CanFill(int[] items, int maxtime)
{
var total = items.Sum();
if (total <= maxtime) return true;
if (total / 2 > maxtime) return false;
BitArray sums_i = new BitArray(total+1);
BitArray sums_i_minus = new BitArray(total+1);
sums_i_minus.Set(0, true);
foreach (var qty in items)
{
for(var sum=0; sum<=total; sum++)
{
if(sums_i_minus[sum] || (sum >= qty && sums_i_minus[sum-qty]))
{
sums_i.Set(sum,true);
if(sum <= maxtime && (total-sum) <= maxtime)
{
return true;
}
}
}
var tmp = sums_i;
sums_i = sums_i_minus;
sums_i_minus = tmp;
}
return false;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment