Can anyone suggest me the approach for solving the above problem.
We can solve this question using standard DP approach plus some optimization. Let us define dp[x] as true if x can be written as sum and false if cannot.
So pseudo-code for this problem is
**for x = 1 ; x< maxLimit ; x++
dp[x] = false
for i = 0 ; i < n ; i++
dp[x] = dp[x] | dp[x-arr[i]]
**
Here | is logical OR. And arr is array of values which can be used to generate sum.
Now you can handle any queries in O(1).
But problem here is above pseudo-code runs for O(N^2).
But now we will use some optimization here.
First optimization is that for solving dp[x] we will only use that values from array which are less than equal to x.
Second optimization is that we will preprocess the array of values such that there is no value in the array that can be written as sum of other values in the array. That is we will remove the redundant entries from the array. This will make the array small.
Thus based on this two optimizations, I was able to solve the problem.
My solution : Link
2 Likes
You can approch the question in the following way Maybe:
arrange the allowed numbers in assending order and then take up the smallest number among them. then try writing the querry as the sum of the smallest number. If you cant do it then there must be remainder. Eg: let N = 4 , K = 2 ,let the allowed numbers be 2 and 3 , let the querry to be handeled be 7 . Now according to the method suggested we need to break 7 in sum of 2 hence it may be written as 2+2+2+1. now from the right side look if the last no. is one of the allowed number. If not then add it to the 2nd last no. and then check if the new number is in an allowed no. if not the add the last 3 no. and check…and hence forth.
if you get the orignal number again impyling that you have added all the numbers then the answer is no!
Here’s the editorial for the problem: https://discuss.codechef.com/questions/89073/chefins-editorial