Official

D - Yet Another Sorting Problem Editorial by evima


Consider a directed graph with edges \(i \rightarrow p_i\). We paint Vertices \(1,\ldots, N\) red and Vertices \(N+1,\ldots,N+M\) blue.

To get straight to the point, the answer is \(N+M-K+2 \max(R, B)\), where \(K\) is the number of connected components in this graph, \(R\) is the number of connected components of size \(2\) or greater consisting of red vertices, and \(B\) is the number of connected components of size \(2\) or greater consisting of blue vertices. We can compute it in \(O(N+M)\) time, which is fast enough.

Below, we will show the validity of the above.

First, the operation in the original problem corresponds to choosing vertices \(i\) and \(j\) with different colors and doing the four actions below.

  • Remove the edge \(i \rightarrow p_i\).
  • Remove the edge \(j \rightarrow p_j\).
  • Add an edge \(i \rightarrow p_j\).
  • Add an edge \(j \rightarrow p_i\).

As a result, the number of connected components increases by \(1\) if \(i\) and \(j\) belonged to the same connected components before the operation, and decreases by \(1\) otherwise.

We will show that we need at least \(N+M-K+2 \max(R, B)\) operations. Let us define \(K_i,R_i,B_i\) as follows. We want to find the minimum \(n\) such that we can have \(K_n = N+M, R_n = 0, B_n=0\).

  • \(K_i\): The number of connected components when the \(i\)-th operation is done.
  • \(R_i\): The number of connected components of size \(2\) or greater consisting of red vertices when the \(i\)-th operation is done.
  • \(B_i\): The number of connected components of size \(2\) or greater consisting of blue vertices when the \(i\)-th operation is done.

From the properties of the operations, \(|K_{i+1} - K_i| =1, |R_{i+1} - R_{i}| \leq 1, |B_{i+1} - B_{i}| \leq 1\) must hold. Additionally, we can have \(R_{i+1} - R_{i} =1\) only if \(K_{i+1} - K_i = 1\). Similarly, we can have \(R_{i+1} - R_{i} =-1\) only if \(K_{i+1} - K_i = -1\). The same goes for \(B_i\).

Here, it is possible to prove that \(f(i) \leq f(i+1)\) holds where \(f(i) = i+N+M-K_i + 2 \max(R_i,B_i)\). From this, we can state that we need at least \(N+M-K_0+2 \max(R_0,B_0)\) operations.

This lower bound can be achieved with the following greedy strategy.

  1. Repeat the following as long as it can be done.
    • If there are a connected component of size \(2\) or greater consisting of red vertices and a connected component of size \(2\) or greater consisting of blue vertices, do the operation between them.
  2. Repeat the following as long as it can be done.
    • If there is a connected component of size \(2\) or greater consisting of red vertices, choose any two connected components both of which contain blue vertices and do the operation.
  3. Repeat the following as long as it can be done.
    • If there is a connected component of size \(2\) or greater consisting of blue vertices, choose any two connected components both of which contain red vertices and do the operation.
  4. Repeat the following as long as it can be done.
    • Choose \(i\) such that \(i\) and \(p_i\) have different colors and doing the operation with \(i\) and \(p_i\) would not create a connected component of size \(2\) or greater consisting of vertices in a single color, and do the operation with \(i\) and \(p_i\). (Such an \(i\) always exists.)

posted:
last update: