Solution to Amazing-test problem from hackerearth

Amazing-test-solution.md

#Problem

The essence of the problem is given a collection of n items of varying size, let T_sum 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 <= T_max and (total-K) <= T_max . Where T_max is the maximum time allowed.

#Solution

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

Let S₁, S₂ ... S_2ⁿ all subsets, we iterate through each subset to see if there exist a subset S_k such that the sum of S_k = K. This approach is guarenteed to be correct, however it is impossibly slow because we have to iterate 2ⁿ subsets. since the number of items in the collection can reach 100, in the worst case we would have to examine 2¹⁰⁰ 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 T_i be the sum of all items in subset S_i , if a solution exists , there must be some T_i , where T_i <= T_max and (T_sum -T_i) <= T_max. We also know that for any subset s_i the sum S_i is in the range 0<= S_i <= Total_set <= 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 i^th 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 n^th 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 s_i such that has a sum(S_i) = k and (k <= T_max and (Total_set - k) <= T_max) . 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, k^th is set if , there exist a subset with sum k.

Final code in C# is given below

amazing_test.cs

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;

    }
}