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, 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:

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: