Evident că vom vrea să efectuăm swap-uri care vor scădea numărul de inversiuni, deoarece vrem să ajungem la 0 inversiuni cât mai repede. Şi deci cum un swap poate scădea cu maxim 1 numărul de inversiuni, rezultă că numărul minim de swap-uri necesare pentru a sorta permutarea este egal cu numărul de inversiuni ale permutării. Q.E.D.
Rămâne acum să vedem cum putem număra numărul de inversiuni. O primă soluţie ar fi chiar să observăm că algoritmul bubblesort rezolvă optim problema de mai sus şi sa aplicăm bubblesort pe Bt şi să numărăm numărul de swap-uri. Această soluţie are complexitate O(N ^ 2) şi ar trebui să obţină 70-80 de puncte.

Pentru 100p va trebui să numărăm inversiunile mai inteligent, folosind un arbore indexat binar/arbore de intervale sau algoritmul mergesort, însă ideile din spatele lor nu le voi mai prezenta în acest articol, ele putând fi găsite printr-o simplă căutare pe google. Astfel se obţine complexitatea dorită O(NlogN). De menţionat că şi o soluţie în O(Nsqrt(N))) ia punctaj maxim.

Pentru 100p va trebui să numărăm inversiunile mai inteligent, folosind un arbore indexat binar/arbore de intervale sau algoritmul mergesort, însă ideile din spatele lor nu le voi mai prezenta în acest articol, ele putând fi găsite printr-o simplă căutare pe google. Astfel se obţine complexitatea dorită O(NlogN).

h2. "PS":https://www.infoarena.ro/problema/ps