RTE on Testcase 9 -> 238C
source link: https://codeforces.com/blog/entry/117104
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK