The last contest's D question, I came up to a solution which got accepted by I do not have the proof the solution. What I did was, First I did a DFS to give colours to the node(here colours means the parity like in bipartite graphs) and maintain two sets for even parity and odd parity. Now, if i came up to any adjacent nodes which have same colour assigned, I just removed any node from the set, given that both nodes are in the set. Now for the answer, I checked whether the bigger set have atleast K / 2 elements or not. If yes, the print the answer and exit and if not, I did another dfs to find cycles, and print it if its length is atmax k.

Solution

Anyone with some proof or willing to discuss or even hack it will sure help me. Thanks.

I'm doing dynamic programming problems and I have found a weird thing that if I change the order of the for loops in the tabulation DP, one of my solution gives TLE whereas by changing the order of loops, it got accepted.

Here's the problem im doing E. Tree Queries from recent div 3 contest. In this question I'm pre calculating LCA using binary lifting but during precalculation, the change in order of loops gives tle and other got accepted.

here's the accepted version 74428570 and here's the TLE solution 74926625. The only difference is in find_ancestor function where I changes the order of the for loop.

If changing order of for loop do matter then why I got TLE instead of WA?

Thanks