 # Need editorial for CHEFINS COOK77

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.