Today for problem 1391E - Pairs of Pairs I didn't come up with the clever DFS tree solution, but I found an interesting constructive algorithm instead:
The main idea is to build a path and a pairing at the same time. We will eventually include every node in either the path or the pairing, at which point we're done.
We keep a set of unused nodes, and we repeatedly try to extend the end of our path by adding one of these unused nodes to the end. We can keep making progress until the end node of our path u only has neighbors that are either already in our path or already in our pairing. When this occurs, we take u and pair it with any unused node v, and then we add this pair to our pairing.
What if this makes the pairing invalid? In that case, since none of our pairs have an edge directly in between them, there must be two other nodes a and b such that at least 3 of these 4 edges exist: u-a, u-b, v-a, v-b. In particular, this means either u-a-v or u-b-v exists as a path, so we can remove the a, b pair and use this to extend our path instead. We can show that this process will monotonically make progress toward our goal state of having every node in either the path or the pairing. But how do we check efficiently whether the pairing becomes invalid? Instead of iterating over every pair, we can iterate over the neighbors of u and check only the pairs containing any of those neighbors.
The potential issue here is that we could iterate over the neighbors of the same node many times, if we repeatedly get it at the end of our path. So it may be possible to TLE the solution. Can anyone find a case to hack this? Here's the link: 89441355
If you manage to hack it, see whether you can also hack this version that does a bunch of random shuffling to make things less predictable: https://mirror.codeforces.com/contest/1391/submission/89459188
I'm also curious whether anyone has a way to fix the solution and make it faster.
I was able to hack both with simple test cases resembling star graphs. The central vertex, with its many dead-end neighbors, is frequently at the end of the working path, and so your code scans over its neighbors many times to find a candidate extension. Result: TLE.
It's definitely possible to modify your solution to pass this kind of testcase, for example by remembering the last candidate extension tried. (See 89463936, test cases 87 and 88.) But I'm not convinced this is enough to avoid more subtle hack attempts.
I see, nice! I had thought that a star graph wouldn't be enough to hack this, but it turns out it actually works. Surprising that the system tests don't have anything like this.
scott_wu and I were looking more at this case and thought of an idea to random shuffle the adjacency lists on the fly: 89473574. It should only take $$$n \log n$$$ iterations on average to handle a star graph. My guess is this version should be a good amount harder to hack.
I did another random sol 89458561 during testing, I have an extra log because I was lazy to code linear sort, but it seems pretty fast, my idea is: take a random dfs tree find the diameter or try pairing consecutive nodes(ordered by depth).