Soluţia problemei Twinperms

Subtask 1: p_i = q_i

Pentru acest subtask, răspunsul va fi 0, deoarece putem sorta direct vectorul şi nu vom avea inversiuni. În mod evident, acesta este răspunsul minim.

Subtask 2: p_i + q_i = N + 1

Pentru acest subtask, observăm că dacă ne uităm la oricare două poziţii i şi j şi le interschimbăm, atunci suma totală de inversiuni nu se schimbă. Astfel, răspunsul va fi acelaşi, oricum am aplica operaţii. Aplicând operaţii astfel încât permutarea p să fie [1, 2, 3, ..., N], atunci permutarea q va fi [N, N - 1, N - 2, ..., 1]. Cum în p nu avem nicio inversiune, iar în q oricum am alege două elemente, ele vor fi în inversiune, răspunsul pentru acest subtask va fi N * (N - 1) / 2.

Subtask 3: 1 ≤ N ≤ 9

Pentru simplitate, vom considera cele două permutări ca şi un şir de perechi, unde x_i = (p_i, q_i). O interschimbare între două elemente i şi j este echivalentă cu interschimbarea perechilor x_i şi x_j. O observaţie ar fi că prin multiple operaţii de interschimbare, problema este echivalentă cu a reordona cele N perechi de numere, astfel încât dacă luăm în ordine primul număr din fiecare pereche şi în ordine cel de-al doilea număr, suma numărului de interschimbări să fie minimă. Astfel, o soluţie este să încercăm toate permutările posibile ale vectorului de perechi x. Putem calcula asta folosind un algoritm recursiv de generare al tuturor permutrilor.

Subtask 4: 1 ≤ N ≤ 16

Pentru acest subtask, putem folosi tehnica programării dinamice pe stări exponenţiale. Fie dp[mask] numărul minim de inversiuni în care toate elementele care aparţin mulţimii reprezentate de mask formează un prefix ("am folosit până acuma toate elementele din mask"). Putem să iterăm prin toate elementele din mask, iar pentru fiecare element, îl scoatem din mask şi verificăm câte inversiuni noi se formează dacă elementul ales este pus după toate celălalte elemente din mask, iar dintre toate variantele, alegem pe cea minimă. Complexitatea acestui algoritm va fi O(2^N * N²).

Subtask 5: 1 ≤ N ≤ 3.000

Putem clasifica elementele lui x în două tipuri de perechi:

• Perechile care contează cum sunt ordonate: dacă avem două perechi (a, b) şi (c, d) care respectă condiţiile a < c şi b < d, atunci contează în ce ordine le punem, deoarece dacă le punem în ordine inversă, obţinem două inversiuni, faţă de zero inversiuni.
• Perechile care nu conteaza în ce ordine sunt aşezate: două perechi (a, b) şi (c, d) unde a > c şi b < d nu contează în ce ordine le punem, deoarece ele vor forma de fiecare dată o singură inversiune.

Observăm că dacă sortăm elementele după oricare dintre permutări, atunci toate perechile de tipul 1 vor fi puse în ordinea potrivită. Astfel, putem să numărăm câte perechi avem de tipul 2 în complexitate O(N²)

Subtask 6: 1 ≤ N ≤ 100.000

Folosindu-ne de observaţiile de la subtaskul precedent, putem să sortăm toate perechile după unul dintre numere. Una din permutări, şi anume cea după care am sortat va genera zero inversiuni. Pentru cealaltă permutare, putem folosi mai multe metode clasice de a număra inversiunile dintr-o permutare, fie cu un Merge Sort modificat, fie cu structuri de date precum arbori de intervale sau arbori indexati binar.