Minimum Üçlük#12307

Minimum Üçlük (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Bizə bir permutasiya $p$ verilir və bir hərəkətdə $i < j < k$ i<j<k indeksləri üzərində $3$ -lü dövr tətbiq edə bilərik:

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

Məqsədimiz minimum sayda hərəkət edərək identiklik permutasiyasına çatmaqdır.

Qeyd edin ki, $3$ -lü dövr cüt permutasiya olduğundan

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

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

Beləliklə, permutasiya pariteti heç vaxt dəyişmir.

Permutasiyanın $c$ ayrılmış dövrə (sabit nöqtələr daxil olmaqla) ayrıldığını düşünək. Biz bilirik ki,

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

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

Beləliklə, əgər $(n - c)$ (n-c) təkdirsə, permutasiya təkdir və identikliyin əldə edilməsi mümkün deyil. Bu halda cavab $- 1$ -dir.

İndi $(n - c)$ (n-c) cütdürsə, fərz edək.

Hər dövrü müstəqil şəkildə işləyə bilərik, buna görə də bir dövrün uzunluğu $l$ olan dövrü pozmaq üçün nə qədər əməliyyat lazım olduğunu anlamaq kifayətdir.

Bir $3$ -lü dövr əməliyyatı dövrlərin sayını ən çox $2$ artırır. Bir uzunluğu $l$ olan dövrü $l$ sabit nöqtəyə çevirmək üçün dövrlərin sayını $(l - 1)$ (l-1) artırmalıyıq, buna görə də hərəkətlərin sayı ən azı

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

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

İndi bu sərhədin əldə oluna biləcəyini göstəririk.

Əgər $l$ təkdirsə, dövr özü cütdür. Biz yalnız bu dövrün elementlərindən istifadə edə bilərik və hər əməliyyat dövrlərin sayını $2$ artırır. $(l - 1) /2$ (l-1)/2 hərəkətdən sonra dövr tamamilə sabitləşir.
Əgər $l$ cütdürsə, dövr təkdir və tək başına sabitləşdirilə bilmir. Lakin, $(n - c)$ (n-c) cütdürsə, cüt uzunluqda başqa bir dövr (və ya əlavə elementlər) mövcuddur. Bunu istifadə edərək, dövr hələ də tam olaraq $l /2$ əməliyyatla sabitləşdirilə bilər.

Beləliklə, uzunluğu $l$ olan bir dövr dəqiq

⌊ \frac{l}{2} ⌋

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

hərəkət edir.

Uzunluqları $l_{1}, l_{2}, \dots, l_{c}$ l_1,l_2,\dots,l_c olan bütün dövrləri topladıqda, biz alırıq:

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

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

Əgər $(n - c)$ (n-c) təkdirsə, $- 1$ çıxarın, əks halda yuxarıdakı dəyəri çıxarın.

Mürəkkəblik $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