Official

E - Number of Cycles Editorial by evima


Consider swapping some two terms in \(x\). This also corresponds to a swap in \(y\). A swap changes the value of \(f(x)\) by \(\pm 1\) and \(f(y)\) by \(\pm 1\).

Thus, the parity of \(f(x)+f(y)\) does not depend on \(x\) and is constant. Below, we assume that \(K\) satisfies this parity condition.

Consider the maximum value of \(f(x)+f(y)\). This can be achieved by \(x=(1,2,\cdots,N)\). If the maximum is achieved by an \(x\) such that \(f(x)<N\), one can do a swap that increases \(f(x)\) by \(1\). This yields a solution with a greater value of \(f(x)\) without decreasing \(f(x)+f(y)\). By repeating this operation, one can obtain a solution such that \(f(x)=N\), that is, \(x=(1,2,\cdots,N)\).

Consider the minimum value of \(f(x)+f(y)\). We will see that it is \(2\) or \(3\) (depending on parity). Here is a specific way to construct a solution.

  • Prepare graphs \(G\) and \(H\) consisting of \(N\) vertices.
  • For \(i=1,2,N-2\) in this order, choose \(x_i\) to be the value \(v\) that satisfies the following conditions. Then, add an edge \((i,v)\) to \(G\) and an edge \((i,P_v)\) to \(H\).
    • Vertex \(i\) and vertex \(v\) are now disconnected in \(G\).
    • Vertex \(i\) and vertex \(P_v\) are now disconnected in \(G\).
  • For \(i=N-1\), choose \(x_i\) to be the value \(v\) that satisfies the following condition.
    • Vertex \(i\) and vertex \(v\) are now disconnected in \(G\).

We can see that the above operations are feasible, that is, one can always take \(v\) that satisfies the conditions, as follows. \(G\) is always a set of paths and cycles, and there is only one \(v\) that does not satisfy the condition for \(G\). The same goes for \(H\). Therefore, if there are three candidates available for \(v\), one can always find one that satisfies both conditions. The same goes for \(i=N-1\).

The above operations clearly result in three or fewer cycles. Thus, the minimum value of \(f(x)+f(y)\) is \(2\) or \(3\).

Below, we assume that \(K\) is between the minimum and maximum values of \(f(x)+f(y)\).

Let \(xmax\) be an \(x\) that maximizes \(f(x)+f(y)\), and \(xmin\) be an \(x\) that minimizes \(f(x)+f(y)\). Let \(xmax=A_0 \to A_2 \to \cdots \to A_s = xmin\) be some sequence of swaps of two terms that changes \(xmax\) to \(xmin\). Here, the number of swaps \(s\) can be anything that is \(O(N)\).

Let \(g(i)\) be the value of \(f(x)+f(y)\) for \(x=A_i\). Since \(g(i+1)-g(i)=-2,0,2\), \(g(0) \geq K \geq g(s)\), and \(K \equiv g(i) \mod 2\), there is always an \(i\) that satisfies \(K=g(i)\), which can be found by binary search. \(g(i)\) can be computed in \(O(N)\), so the answer can be found in \(O(N \log N)\) in total.

Sample solution

posted:
last update: