Minimum Triple#12307

Minimum Triple (Editorial)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

We are given a permutation $p$ and in one move we can apply a $3$ -cycle on indices $i < j < k$ i<j<k in either direction:

(p_{i}, p_{j}, p_{k}) \leftarrow (p_{j}, p_{k}, p_{i}) or (p_{i}, p_{j}, p_{k}) \leftarrow (p_{k}, p_{i}, p_{j}) .

(p_i,p_j,p_k)\leftarrow(p_j,p_k,p_i) \quad\text{or}\quad (p_i,p_j,p_k)\leftarrow(p_k,p_i,p_j).

Our goal is to reach the identity permutation using minimum number of moves.

Notice that a $3$ -cycle is an even permutation, since

(a b c) = (a c) (a b) .

(a\,b\,c)=(a\,c)(a\,b).

Thus parity of the permutation never changes.

Let the permutation decompose into $c$ disjoint cycles (including fixed points). We know that

sgn (p) = (- 1)^{n - c} .

\operatorname{sgn}(p)=(-1)^{n-c}.

Hence, if $(n - c)$ (n-c) is odd, the permutation is odd and it is impossible to reach the identity. In this case the answer is $- 1$ .

Now assume $(n - c)$ (n-c) is even.

We can process each cycle independently, so it is enough to understand how many operations are needed to break a single cycle of length $l$ .

Observe that one $3$ -cycle operation can increase the number of cycles by at most $2$ . To transform a cycle of length $l$ into $l$ fixed points, we need to increase the number of cycles by $(l - 1)$ (l-1), so the number of moves is at least

⌈ \frac{l - 1}{2} ⌉ = ⌊ \frac{l}{2} ⌋ .

\left\lceil \frac{l-1}{2} \right\rceil = \left\lfloor \frac{l}{2} \right\rfloor.

Now we show this bound is achievable.

If $l$ is odd, the cycle itself is even. We can use only elements of this cycle and each operation increases the number of cycles by $2$ . After $(l - 1) /2$ (l-1)/2 moves, the cycle is completely fixed.
If $l$ is even, the cycle is odd and cannot be fixed alone. However, since $(n - c)$ (n-c) is even, there exists another even-length cycle (or extra elements) to pair with. Using this, the cycle can still be fixed using exactly $l /2$ operations.

Thus, a cycle of length $l$ contributes exactly

⌊ \frac{l}{2} ⌋

\left\lfloor \frac{l}{2} \right\rfloor

moves.

Summing over all cycles with lengths $l_{1}, l_{2}, \dots, l_{c}$ l_1,l_2,\dots,l_c, we get:

answer = i = 1 \sum c ⌊ \frac{l _{i}}{2} ⌋ .

\text{answer} = \sum_{i=1}^{c} \left\lfloor \frac{l_i}{2} \right\rfloor.

If $(n - c)$ (n-c) is odd, output $- 1$ , otherwise output the value above.

Complexity $O (n)$ .

for _ in range(int(input())):
    n=int(input())
    p=[0]+list(map(int,input().split()))
    vis=[0]*(n+1)
    ans=0
    c=0
    for i in range(1,n+1):
        if vis[i]: continue
        c+=1
        cur=i
        l=0
        while not vis[cur]:
            vis[cur]=1
            cur=p[cur]
            l+=1
        ans+=l//2
    print(-1 if ((n-c)&1) else ans)

Python