twinperms

Twinperms

h2. Restricţii
* Permutările sunt indexate de la $1$ până la $N$.

* $1 ≤ N ≤ 500.000.$
* Pentru 20 de puncte, avem $p{~i~} = q{~i~}$ pentru toate $i$, unde $1 ≤ i ≤ N$.
* Pentru alte 20 de puncte, avem $p{~i~} + q{~i~} = N + 1$ pentru toate $i$, unde $1 ≤ i ≤ N$.
* Pentru alte 40 de puncte, avem $1 ≤ N ≤ 1.000$.

* $1 ≤ N ≤ 100.000.$
* Pentru 10 puncte, avem $p{~i~} = q{~i~}$ pentru toate $i$, unde $1 ≤ i ≤ N$.
* Pentru alte 10 puncte, avem $p{~i~} + q{~i~} = N + 1$ pentru toate $i$, unde $1 ≤ i ≤ N$.
* Pentru alte 10 puncte, avem $1 ≤ N ≤ 9$.
* Pentru alte 15 puncte, avem $1 ≤ N ≤ 16$.
* Pentru alte 35 de puncte, avem $1 ≤ N ≤ 3.000$.

* O permutare de mărime $N$ este un şir de $N$ elemente unde fiecare număr de la $1$ până la $N$ apare exact o dată.
* Numărul de inversiuni dintr-o permutare $p$ este numărul de perechi $i, j$, unde $1 &le; i < j &le; N$, cu proprietatea că $p{~i~} > p{~j~}$.

| 4
3 4 1 2
1 4 2 3

| 4

| 2

|
h3. Explicaţie

Dacă interschimbăm elementele de pe poziţiile 2 şi 4, o să obţinem permutările $p = [3, 2, 1, 4]$ şi $q = [1, 3, 2, 4]$. Cum $p$ are 3 inversiuni, iar $q$ are o inversiune, suma totală este de 4 inversiuni. Aceasta este suma minimă.

Putem să interschimbăm elementele de pe poziţiile $1$ şi $3$, astfel permutările devin: $p = [1, 4, 3, 2]$ şi $q = [2, 4, 1, 3]$. După asta, putem interschimba elementele de pe poziţiile $2$ şi $3$, astfel permutările devin: $p = [1, 3, 4, 2]$ şi $q = [2, 1, 4, 3]$. La sfârşit, putem interschimba elementele de pe poziţiie $3$ şi $4$. Permutările vor ajunge în final: $p = [1, 3, 2, 4]$ şi $q = [2, 1, 3, 4]$. Cum prima permutare are o inversiune, şi anume cea de pe poziţiile $2$ şi $3$, iar a doua permutare are tot o singură inversiune, şi anume cea de pe poziţiile $1$ şi $2$, numărul total de inversiuni va fi 2. Această sumă este minimă.

== include(page="template/taskfooter" task_id="twinperms") ==