Hello! I have been trying to find the cause of RTE in this submission: 208940837 and have unfortunately been highly unsuccessful in doing so, hence this plea for help.

Here is my logic behind the program:

Note that each of the "queries" form a directed graph that has max indeg across all nodes as 1.

Any cycles made in this graph mean that is impossible -> 0.

Now, if some value a is more used than another value b, then it is obvious that at minimum #a's used is at least 1 more than #b's used.

This holds for longer paths -> a>b>c>d -> at minimum we use 3 a , 2 b , 1 c , 0 d

After we find coins that must be used using the above idea, since we must maintain any inequality a > b, if we use a coin of type b, we must use a coin of type a as well, so we can merge these two values together into a+b, and repeat doing so for longer paths -> a>b>c>d -> a+b , a+b+c , a+b+c+d

After collecting all possible coin values, it is a simple dp knapsack problem.

I am not sure if my logic is completely wrong and hence the RTE or what I am missing.

Please do let me know!

Take a look at Ticket 16867 from

CF Stressfor a counter example.If you are still unable to debug, here's the corrected AC Submission.

Thank you so much! Is the only thing you changed the dp?

I only handled overflows using a hack. See https://www.diffchecker.com/

To fix it in a proper way, you would need to go through the code in detail and figure out possible areas for overflow.