### SriniV's blog

By SriniV, history, 4 months ago, 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. help, dp, Comments (3)