Мінімальний трійник#12307

Мінімальний трійник (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Розв'язок

Нам дано перестановку $p$ , і за один хід ми можемо застосувати $3$ -цикл на індексах $i < j < k$ i<j<k в будь-якому напрямку:

(p_{i}, p_{j}, p_{k}) \leftarrow (p_{j}, p_{k}, p_{i}) або (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{або}\quad (p_i,p_j,p_k)\leftarrow(p_k,p_i,p_j).

Наша мета - досягти ідентичної перестановки, використовуючи мінімальну кількість ходів.

Зверніть увагу, що $3$ -цикл є парною перестановкою, оскільки

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

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

Отже, парність перестановки ніколи не змінюється.

Нехай перестановка розкладається на $c$ неперетинних циклів (включаючи фіксовані точки). Ми знаємо, що

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

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

Отже, якщо $(n - c)$ (n-c) непарне, перестановка є непарною, і досягти ідентичності неможливо. У цьому випадку відповідь - $- 1$ .

Тепер припустимо, що $(n - c)$ (n-c) парне.

Ми можемо обробляти кожен цикл незалежно, тому достатньо зрозуміти, скільки операцій потрібно, щоб розбити один цикл довжини $l$ .

Зверніть увагу, що одна операція $3$ -цикла може збільшити кількість циклів максимум на $2$ . Щоб перетворити цикл довжини $l$ у $l$ фіксованих точок, нам потрібно збільшити кількість циклів на $(l - 1)$ (l-1), тому кількість ходів становить щонайменше

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

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

Тепер ми покажемо, що ця межа досяжна.

Якщо $l$ непарне, сам цикл є парним. Ми можемо використовувати лише елементи цього циклу, і кожна операція збільшує кількість циклів на $2$ . Після $(l - 1) /2$ (l-1)/2 ходів цикл повністю фіксується.
Якщо $l$ парне, цикл є непарним і не може бути зафіксований самостійно. Однак, оскільки $(n - c)$ (n-c) парне, існує інший цикл парної довжини (або додаткові елементи) для парування. Використовуючи це, цикл все ще може бути зафіксований за точно $l /2$ операцій.

Отже, цикл довжини $l$ вносить точно

⌊ \frac{l}{2} ⌋

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

ходів.

Підсумовуючи по всіх циклах з довжинами $l_{1}, l_{2}, \dots, l_{c}$ l_1,l_2,\dots,l_c, ми отримуємо:

відповідь = i = 1 \sum c ⌊ \frac{l _{i}}{2} ⌋ .

\text{відповідь} = \sum_{i=1}^{c} \left\lfloor \frac{l_i}{2} \right\rfloor.

Якщо $(n - c)$ (n-c) непарне, виведіть $- 1$ , в іншому випадку виведіть значення вище.

Складність $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