SriniV's blog

By SriniV, history, 4 months ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Take a look at Ticket 16867 from CF Stress for a counter example.

If you are still unable to debug, here's the corrected AC Submission.

  • »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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