Samsung R&D Institute Bangalore Question

I was invited to give the test and the following question was asked.

There is a weighing scale and we have an array X of integers which represents weights we are having with us. We can measure all weights which can be formed by various combinations of these weights. Suppose array is {7,9,28} then we can measure 7,9,28,2,19,16, etc. Now we are given a range [A,B], we need to tell if we can measure all weights in the range. If we can’t measure all weights in range [A,B] then we can use one extra weight which is not in the given array. Lets call it W. If there are more than one W which can be used, select the one with lowest weight.

Input : First line no of Test Cases (Less than or equal to 10)
Every test case is as follows:
First Line contains N i.e. no of given weights (N<=30)
Next line contains array X (All weights are in the range 1 to 500)
Next Line contains two space separated integers A and B (1<=A<=B<=10000 or 20000 don’t remember exactly)

Also the weight W is from range 1 to 500.

Output :
Print YES if we can measure all the weights in the range. Print the lowest W in next line.
If we can’t measure all the weights in the range print NO

For some cases constraints were somewhat smaller like N<=20, range [A,B] was lesser, etc.

I thought of trying meet in the middle and generate all possible sums and differences but for N=30 I don’t know will it work.

Help Please :grin:


Just a little hint. It is a dp problem. Say dp[i][w] represents a bool value which is true when we can reach the weight ‘w’ using first ‘i’ weights.

How do you solve the later part? Finding the smallest W such that…

It is like when we generated the whole dp table, if we get dp[n][w] to be false, we then check dp[n][w-1], then dp[n][w-2]… till we hit the first number to be true. say dp[n][w-k]. Then our answer would be k.

1 Like

I don’t know much DP, could you please provide solution link if possible

I think we need re-build the DP table for the new added weight, this requires O(W) complexity in the worst case. Now for the newly added weight once we have re-built the DP table(note- the new size of the DP table is (n+1) * W) we check if all the weight in [A, B] are set to true, if not we choose some different weight and repeat the process of rebuilding the DP table for this new weight and running a check for if all weights in the range [A, B] can be done.
More formally, select every weight in [1, 500], rebuild the DP table to (n+1) * W state and check if all weights in the range [A, B] can be done.
It would take O(W^2) in the worst case. Which is acceptable since W <= 500

Google for Subset Sum Problem.

BTW how were you selected for the test?

From HackerEarth Contest

Do you have the link to the question?

A simple subset sum implementation would suffice.

I gave it at their selected venue

Ok, so the complexity will be somewhat approx :

30*10000(Max value of B)+ (500-n)*100000

Am I right?