When I was solving the problem D from the last contest Codeforces Round 1070 (Div. 2), in the contest i wrote the dp arguments like (vertex v, parent of vertex v), it gave TLE see my submission, and using some optimizations i reduced the dp arguments to just 1 and it was the index of the edge, and same it gave TLE :-(
in the contest I was able to optimize this solution using segment tree and binary search and finally it gave AC!
but after the contest I just changed a small thing in my first submission instead of having arguments like (vertex v, parent of vertex v), I changed it to (vertex v, the value of the parent of vertex v) and it was passed!!, see my submission
Can anyone tell me how that happened?
Thanks!
sometimes it happens
Actually I need an explaining for that, I don't need to just see the AC to a particular problem and move on, these small things mean alot to me
The reason is that you started depending on the value of the previous number, not on the node index itself, and that’s why the solution got AC.
Why?
Because in the test cases, they are forced to use a small number of values. The Fibonacci sequence up to (10^{18}) has only about 88 numbers. So if they want to make you go deep in recursion, they must follow the Fibonacci sequence correctly.
They cannot force you to walk through something like 1000 different steps, because that’s impossible with Fibonacci values limited to (10^{18}).
That’s why when the DP depends on the value of the node instead of the node number, the number of states becomes very small, and the solution becomes much more efficient, which leads to AC.
Got it thanks!
I had a similar experience with this problem, your comment helped me, thank you.
Lets say you have this graph:
(In the picture:
a(b)means node with indexahas valueb)Then your TLE code stores
{node 2, parent 1}, {node 2, parent 4}. But your AC code stores{node 2, value 1}which just reduces the time & space!Oh I see!, Thanks alot