h3. Farfurii

Problema cere construirea unei permutari de lungime $N$ cu $K$ inversiuni, minim lexicografica. O prima rezolvare de complexitate $O(N^2^)$ ar fi construirea permutarii element cu element. Cu cat un element este mai mare pe o anumita pozitie cu atat formeaza mai multe inversiuni, astfel ca incercam sa punem pe fiecare pozitie un element cat mai mic astfel: pe pozitia {$i$}, daca $K ≤ (N-i)*(N-i-1)/2$ putem pune cel mai mic element disponibil (pentru ca in bucata de $N-i$ ramasa putem construi cel putin {$(N-i)*(N-i-1)/2$} inversiuni), altfel punem al {$K-(N-i)*(N-i-1)/2$} element disponibil. Aceasta modalitate de constructie garanteaza ca permutarea este minim lexicografic. O implementare directa, cum am zis, are complexitate $O(N^2)$ si ia {$40-60p$}. Pentru $100p$ se poate folosi un arbore de intervale (ca la problema "concurs":http://campion.edu.ro/problems.php?mode=view_round&group_number=3&year=2004&round_number=9 de la .campion 2004, runda 9) reducand complexitate la {$O(N*lg N)$}. O asemenea solutie, desi lua {$100p$}, necesita cunostiinte de structuri de date avansate care depasesc nivelul de cunostiinte general al unui concurent pentru clasele {$9-10$}. O rezolvare $O(N)$ mult mai simpla se bazeaza pe urmatoarea observatie:

Problema cere construirea unei permutari de lungime $N$ cu $K$ inversiuni, minima lexicografic. O prima rezolvare de complexitate $O(N^2^)$ ar fi construirea permutarii element cu element. Cu cat un element este mai mare pe o anumita pozitie cu atat formeaza mai multe inversiuni, astfel ca incercam sa punem pe fiecare pozitie un element cat mai mic astfel: pe pozitia {$i$}, daca $K ≤ (N-i)*(N-i-1)/2$ putem pune cel mai mic element disponibil (pentru ca in bucata de $N-i$ ramasa putem construi cel putin {$(N-i)*(N-i-1)/2$} inversiuni), altfel punem al {$K-(N-i)*(N-i-1)/2$} element disponibil. Aceasta modalitate de constructie garanteaza ca permutarea este minima lexicografic. O implementare directa, cum am zis, are complexitate $O(N^2)$ si ia {$40-60p$}. Pentru $100p$ se poate folosi un arbore de intervale (ca la problema "concurs":http://campion.edu.ro/problems.php?mode=view_round&group_number=3&year=2004&round_number=9 de la .campion 2004, runda 9) reducand complexitatea la {$O(N*lg N)$}. O asemenea solutie, desi ia {$100p$}, necesita cunostiinte de structuri de date avansate care depasesc nivelul de cunostiinte general al unui concurent pentru clasele {$9-10$}. O rezolvare $O(N)$ mult mai simpla se bazeaza pe urmatoarea observatie:

O permutare de lungime $i$ are cel mult $i*(i-1)/2$ inversiuni cand numerele sunt in ordine descrescatoare.

Astfel, daca $K$ e de forma $M*(M-1)/2$ permutarea minim lexicografica cu $K$ inversiuni va fi:

Astfel, daca $K$ e de forma $M*(M-1)/2$ permutarea minima lexicografic cu $K$ inversiuni va fi:

$1, 2, 3, ... N-M, N, N-1, N-2, ... N-M+1$

$1, 2, 3, ... N-M-1, N, N-1, N-2, ... N-M$

(care are $(M+1)*M/2$ inversiuni) si mutam elementul {$N-((M+1)*M/2-K$}) imediat inaintea lui {$N$}, astfel scadem numarul de inversiuni la {$K$}. Este evident ca permutarea astfel construita este minim lexicografica. Algoritmul descris are complexitate {$O(N)$}.

(care are $(M+1)*M/2$ inversiuni) si mutam elementul {$N-((M+1)*M/2-K$}) imediat inaintea lui {$N$}, astfel scadem numarul de inversiuni la {$K$}. Este evident ca permutarea astfel construita este minima lexicografic. Algoritmul descris are complexitate {$O(N)$}.

h2. Clasele 11-12