Zhily and Cycle

The graph looks scary, but every row is just a suffix. That kills most of the complexity dead.

Observation 1: the whole problem is about prefixes

A directed edge $i \to j$ exists iff $j \ge a_i$.

So for a fixed $k$, the only vertices that can point into the prefix $[1..k]$ are exactly the vertices with $a_i \le k$.

Let

$$c_k = |\{i : a_i \le k\}|.$$

Now suppose a Hamiltonian cycle exists.

• Every vertex in $[1..k]$ needs one incoming edge, so we need at least $k$ possible predecessors: $c_k \ge k.$
• But if $k<n$ and $c_k = k$, then those $k$ vertices are the only ones that can point into $[1..k]$. Since the cycle gives exactly one incoming edge to each of the $k$ vertices in $[1..k]$, all outgoing edges of those $k$ vertices are forced to stay inside $[1..k]$. Then this set becomes closed, so you cannot have one cycle going through all $n$ vertices. Game over.

Therefore the necessary condition is actually

$$c_k > k \quad \text{for all } 1 \le k < n.$$

That is also sufficient. Yep, that simple. The rest is just construction.

If you sort $a$ increasingly into $b_1 \le b_2 \le \dots \le b_n$, this condition is equivalent to

$$b_1 = 1, \qquad b_i < i \text{ for } i \ge 2.$$

Very parking-function-ish. Cute, but we still need the actual cycle.

Observation 2: build predecessors in increasing order

Instead of deciding the cycle order directly, decide for each vertex $j$ who points to it.

Process destinations $j = 1,2,\dots,n$. At step $j$, we want to choose some vertex $u$ and add the edge

$$u \to j.$$

What must be true?

1. $u$ must satisfy $a_u \le j$.
2. $u$ must not have been used before as a predecessor, otherwise it would get two outgoing edges.
3. We must avoid creating a cycle too early.

This screams: keep the chosen edges as a bunch of disjoint directed paths.

Key invariant: chosen edges form disjoint directed paths

Initially, every vertex is an isolated path.

Suppose after processing $1..j-1$, all chosen edges form disjoint directed paths. Then:

• a vertex is still usable as a predecessor iff it has no chosen outgoing edge yet;
• inside a directed path, the only vertex with no outgoing edge is the tail.

So each current component contributes at most one usable predecessor.

Also, vertex $j$ has not been processed as a destination yet, so nobody points to $j$ yet. Thus $j$ has indegree $0$, which means it is the head of its current path.

Therefore, if we connect a tail $u$ from a different component to $j$,

$$u \to j,$$

we simply glue two paths into one larger path. No cycle appears. Nice and clean.

Why the condition $c_k > k$ is enough

At step $j$, all vertices with $a_i \le j$ are already allowed to be predecessors. There are exactly $c_j$ such vertices.

Among them, exactly $j-1$ have already been used as predecessors in earlier steps, so the number of currently available predecessors is

$$c_j - (j-1).$$

Now for $j<n$:

$$c_j - (j-1) > 1.$$

So there are at least $2$ available vertices. Since each component contributes at most one available tail, at most one available vertex can lie in the same component as $j$. Hence there is always some available tail in a different component. Use it.

This merges two components, so after steps $1,2,\dots,n-1$ we have merged components exactly $n-1$ times:

$$n \to n-1 \to \dots \to 1.$$

So right before step $n$, there is exactly one path containing all vertices.

At step $n$, the number of available predecessors is

$$c_n - (n-1) = n - (n-1) = 1.$$

That one remaining available vertex is the tail of the big path. Vertex $n$ is its head (nobody pointed to $n$ earlier). Connecting tail to head closes the path into one Hamiltonian cycle.

Done. No black magic, just a stubborn invariant.

Implementation details

We need two things:

1. A DSU to know whether two vertices are already in the same current path component.
2. A container of currently available vertices.

A vertex becomes available exactly when we reach $j = a_i$. So we bucket vertices by value $a_i$ and add bucket $j$ when processing destination $j$.

A super handy fact: each component has at most one available vertex. So if we store available vertices in a simple vector, then:

• usually we take the last one;
• if that one happens to be in the same component as $j$ and $j<n$, then the second last one is automatically in a different component.

That gives an $O(n\alpha(n))$ construction per test case.

Correctness sketch

• The prefix condition $c_k > k$ for $k<n$ is necessary by the prefix incoming-edge argument.
• The algorithm always finds a valid predecessor for each $j<n$ because the number of available predecessors is at least $2$.
• Every chosen edge connects the tail of one path to the head of another path, so before the last step we never create a cycle.
• After $n-1$ merges, all vertices lie in one path.
• The final edge closes that path into a single directed cycle containing all vertices.

So the algorithm outputs No iff impossible, otherwise outputs a Hamiltonian cycle.

Complexity

For each test case:

• checking the condition: $O(n)$,
• construction with DSU: $O(n\alpha(n))$.

Total over all test cases:

$$O\left(\sum n\,\alpha(n)\right),$$

which is easily fine for $\sum n \le 10^6$.

Pretty elegant, honestly. The graph tries to look intimidating, but it’s mostly just suffixes and bookkeeping.