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
b such that at least 3 of these 4 edges exist:
v-b. In particular, this means either
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