RTE on Testcase 9 -> 238C

Revision en1, by SriniV, 2023-06-08 04:34:50

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!

Tags help, runtime error, dp, please

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SriniV 2023-06-08 04:34:50 1128 Initial revision (published)