$$$2800$$$

dsu, maths, constructive

When $$$N$$$ is odd, it is always impossible.

Proving it might be an inspiration at some situations. It is highly recommended that readers can prove it themselves.

The proof of this is also at the end of the blog.

Print out the all possible next nodes, does some nodes have the same next nodes?

From hint 2, we can notice that node $$$i$$$ and node $$$i + \frac {N} {2}$$$ is actually the same. So, we can simply set $$$i$$$ goes to $$$(2i) mod N$$$ and $$$i + \frac {N} {2}$$$ goes to $$$(2i + 1) mod N$$$.

Then we can magically notice that these nodes will form cycles. Hence, our task now is to merge the cycles into one (because we want all nodes to be in a cycle).

Imagine now we have two cycles: $$$C1$$$ and $$$C2$$$. $$$C1$$$ contains $$$i \rightarrow (2 * i)$$$ $$$mod$$$ $$$N$$$ and $$$C2$$$ contains $$$i + \frac {N} {2} \rightarrow (2 * i + 1)$$$ $$$mod$$$ $$$N$$$.

By crossing the edges, we can see that the cycles are merged! Hence, in order to merge two cycles, we can simply swap the next steps of $$$i$$$ and $$$i+\frac {N} {2}$$$.

In order to maintain cycles, we can use a dsu to maintain whether two nodes are already in the same cycle.

Proof:

We will prove that: when $$$N$$$ is odd, it is impossible to build a path by looking at $$$\frac {N - 1} {2}$$$.

What goes to $$$0$$$ is either $$$0$$$ or $$$\frac {N - 1} {2}$$$. Since if we started from $$$0$$$ and ends at $$$0$$$ immediately, it cannot be the answer. Thus, the next step of $$$\frac {N - 1} {2}$$$ must be $$$0$$$.

What goes to $$$N - 1$$$ is either from $$$(N - 1)$$$ or $$$\frac {N - 1} {2}$$$. Similarly, the next step of $$$\frac {N - 1} {2}$$$ must be $$$N - 1$$$.

Since the next step of $$$\frac {N - 1} {2}$$$ can only be one of $$$0$$$ or $$$N - 1$$$, it is impossible to build the path.