Auto comment: topic has been updated by shubhamgoyal__ (previous revision, new revision, compare).

Good day to you

Here is mine solution — following description of it.

Firstly, let us think about it in "most" naive way. Let us have all the numbers and try Dynamic Programming [classical knapsack problem]. You simply try to ask ALL lower solutions for answer (i.e., having dyn(10), with numbers "1,2,3,4,5", you ask dyn(10-1),dyn(10-2),dyn(10-3),dyn(10-4),dyn(10-5) for answer). This works correctly, yet obviously you will get TLE, since it is O(N*K) which is too much (yet — we have good approach)

So lets improve a little bit. We can use principal of sieve. Lets iterate over all numbers (in ascending order) removing all its multiples (you know that you can obtain them sooner or later). This helped much — from (at most) 200 000 numbers, we can have at most "17985" numbers. Yet the complexity is still (K*17985), which is way to much.

But is it really "way too much"? Lets have little observation. As there will be low numbers (among our numbers) we will get "positive" answer from dynamic calls almost surely (lets consider 1 in there — then we won. Lets consider 2 — we just need some odd number [or nothing if it is already even]. Lets consider 3 — [if the answer is congruent with 3, then we are done, otherwise we "just" need a number with that "remainder" {and low size obv.}]). This argument is kinda "strong" BUT in fact, it costs almost nothing. It just says, that we have to iterate ONLY to numbers up-to actual knapsack size AND as soon as we find positive answer, we have to stop.

This argument means: If there are big numbers, then it might not stop soon, but there will be only few iteration on each call. If there are low numbers, it will most probably stop very soon.

Obviously, don't recalculate the DP, so the query could be O(1).

Sorry for the long post here is a potato! [Hopefully the code will be more understandable then my explanation]

Good Luck & Have Nice Day

You can checkout my solution for the problem at https://www.codechef.com/viewsolution/12298767. I have basically used the fact that "If we can form a integer X from the given set of integers A, so that implies we can form all its multiples as well" (can be related to sieve approach), this helps us to optimise the solution which is based on basic boolean dp, that is DP[X] = DP[X-A[0]] | DP[X-A[1]] | DP[X-A[2]].....

Still, for passing the test cases further optimisation was needed. For that, I reduced the given array A(after sorting) to a new array such that if it contains some A[i] then it will not contain any other multiple of A[i]. For implementation details, you can refer the code.

Not sure of the complexity of my solution :/