==Rankings(rounds="preoni53a" display_entries="7" pager_style="none")==
Primele doua locuri din clasament sunt "ocupate" de "veterani", Dan Fechete fiind clasa a 12-a, iar Mugurel Ionut student. In rest, in clasament si-au facut loc concurenti destul de "celebri", unii dintre ei premianti la ONI in anii trecuti.
h3. Barman
(solutie corecta oferita de Dan Spatarel, 20 noiembrie 2005)
(solutie corecta oferita de ==user(user="spatarel" type="tiny")==, 20 noiembrie 2005)
Metoda folosita este una brute-force si se bazeaza pe cateva observatii. Pentru a determina solutia optima sortam sirul valorilor bauturilor si ii generam toate permutarile circulare in vectorul obt. De aici, problema noastra ramane transformarea de cost minim a vectorului initial a in vectorul obt folosind operatiile permise. Dintre toate permutarile circulare, evident o vom alege pe cea care cere un cost minim al operatiilor. In primul rand se observa ca nu are nici un rost sa deranjam camerele care au bautura ceruta (a[i] = obt[i]), deci pe Paftenie nu il vor preocupa acestea. In al doilea rand este de remarcat ca ar fi inutil ca Paftenie sa deplaseze mai mult de un pahar intre doua camere deoarece am considera un caz redundant. De ce? Ar fi libere numai camerele c1 si c2, din care provin cele doua pahare de pe tava. Cu doua pahare pe tava ar putea sa mearga intr-o camera c3 diferita de c1 si c2, dar ar fi inutil, caci nici pe tava nici in camera nu mai poate depozita vreun pahar.
Metoda folosita este una brute-force si se bazeaza pe cateva observatii. Pentru a determina solutia optima sortam sirul valorilor bauturilor si ii generam toate permutarile circulare in vectorul obt. De aici, problema noastra ramane transformarea de cost minim a vectorului initial a in vectorul obt folosind operatiile permise. Dintre toate permutarile circulare, evident o vom alege pe cea care cere un cost minim al operatiilor. In primul rand se observa ca nu are nici un rost sa deranjam camerele care au bautura ceruta ({$a{~i~} = obt{~i~}$}), deci pe Paftenie nu il vor preocupa acestea. In al doilea rand este de remarcat ca ar fi inutil ca Paftenie sa deplaseze mai mult de un pahar intre doua camere deoarece am considera un caz redundant. De ce? Ar fi libere numai camerele $c{~1~}$ si {$c{~2~}$}, din care provin cele doua pahare de pe tava. Cu doua pahare pe tava ar putea sa mearga intr-o camera $c{~3~}$ diferita de $c{~1~}$ si {$c{~2~}$}, dar ar fi inutil, caci nici pe tava nici in camera nu mai poate depozita vreun pahar.
Astfel, problema se reduce la a gasi, pentru fiecare bautura care nu se afla pe locul ei, o pozitie optima, pe care daca o asezam, vom obtine un cost global minim. Pentru simplitate, in continuare voi numi "cuplaj" mutarea unei bauturi pe o alta masa. Se poate oberva ca problema se poate imparti in mai multe sub-probleme independente: fiecare sub-problema va calcula cuplajul optim pentru toate bauturile de aceeasi valoare. Problemele sunt independente, deoarece pentru a pastra solutia optima globala, trebuie sa cuplam o bautura cu o masa pe care trebuie plasata acelasi tip de bautura.
O metoda ar fi greedy: pentru fiecare bautura care nu e la locul ei, cautam cea mai apropiata masa pe care se poate pune - insa aceasta metoda este gresita.
O alta metoda este cuplajul intr-un graf bipatit. Desi aceasta rezolvare este corecta, nu se incadreaza in timpul de executie. Deoarece trebuie efectuate N cuplaje cu cate 2*N noduri fiecare, vom obtine o complexitate de O(N^5), supraestimata. Este posibil, totusi, ca in urma unor optimizari puternice, si aceasta metoda sa obtina punctaj mare.
O alta metoda este cuplajul intr-un graf bipatit. Desi aceasta rezolvare este corecta, nu se incadreaza in timpul de executie. Deoarece trebuie efectuate $N$ cuplaje cu cate $2*N$ noduri fiecare, vom obtine o complexitate de {$O(N^5^)$}, supraestimata. Este posibil, totusi, ca in urma unor optimizari puternice, si aceasta metoda sa obtina punctaj mare.
Totusi, mai exista si o alta metoda mult mai simpla si mai rapida, care se bazeaza pe cateva observatii suplimentare: datorita sortarii pe care am efecutat-o la inceputul algoritmului si a permutarilor circulare, mesele pe care trebuie plasata aceeasi bautura, sunt plasate fie secvential, fie in doua secvente, de la 1 la k si de la l la N. De asemenea, deoarece am eliminat cazurile in care a[i] = obt[i], cele doua cazuri, fara a pirde dingeneralitate, se reduc la unul singur: in intervalul 1 - k exista numai bauturi care trebuie cuplate; in intervalul k+1 - l exista numai mese care trebuie cuplate; in intervalul l+1 - N exista numai bauturi care trebuie cuplate. (Al doilea caz este simetric, si deoarece mesele pot fi privite ca bauturi, si invers, putem reduce al doilea caz la primmul.)
Totusi, mai exista si o alta metoda mult mai simpla si mai rapida, care se bazeaza pe cateva observatii suplimentare: datorita sortarii pe care am efecutat-o la inceputul algoritmului si a permutarilor circulare, mesele pe care trebuie plasata aceeasi bautura, sunt plasate fie secvential, fie in doua secvente, de la $1$ la $k$ si de la $l$ la {$N$}. De asemenea, deoarece am eliminat cazurile in care {$a{~i~} = obt{~i~}$}, cele doua cazuri, fara a pirde dingeneralitate, se reduc la unul singur: in intervalul $1$ - $k$ exista numai bauturi care trebuie cuplate; in intervalul $k+1$ - $l$ exista numai mese care trebuie cuplate; in intervalul $l+1$ - $N$ exista numai bauturi care trebuie cuplate. (Al doilea caz este simetric, si deoarece mesele pot fi privite ca bauturi, si invers, putem reduce al doilea caz la primmul.)
Problema se rezolva partitionand mulmimea meselor in doua secvente: mesele din prima secventa se vor cupla cu bauturile din intervalul 1 - k, iar mesele din a doua secventa cu bauturile din intervalul l+1 - N. Se poate observa ca oricum s-ar realiza cele doua cuplaje, costul golbal va fi acelasi. In plus, orice alt cuplaj global care nu tine cont de aceasta impartire va obtine un const global mai mare. Astfel, se garanteaza ca aceasta metoda va calcula corect costul minim global.
Problema se rezolva partitionand mulmimea meselor in doua secvente: mesele din prima secventa se vor cupla cu bauturile din intervalul $1$ - {$k$}, iar mesele din a doua secventa cu bauturile din intervalul $l+1$ - {$N$}. Se poate observa ca oricum s-ar realiza cele doua cuplaje, costul golbal va fi acelasi. In plus, orice alt cuplaj global care nu tine cont de aceasta impartire va obtine un const global mai mare. Astfel, se garanteaza ca aceasta metoda va calcula corect costul minim global.
Algoritmul care impleneteaza acest cuplaj este foarte simplu: pentru fiecare bautura care nu se alfa la locul ei (a[i] = obt[i]), se cauta prima masa necuplata pe care se poate plasa bautura.
Algoritmul care impleneteaza acest cuplaj este foarte simplu: pentru fiecare bautura care nu se alfa la locul ei ({$a{~i~} = obt{~i~}$}), se cauta prima masa necuplata pe care se poate plasa bautura.
h3. Cifre
Pentru a afla probabilitatea ceruta trebuie sa aflat cate numere exista in intervalul [A..B] cu cel putin K cifre de C. Pentru asta vom construi o functia f(x) care va returna cate numere sunt in intervalul [0..x-1] care au cel putin K cifre de C. Astfel rezultatul va fi f(B+1)-f(A). Functia f(x) va rula in complexitate O(lg x) parcurgand numarul x cifra cu cifra. Ca sa realizam acest lucru avem nevoie de urmatoarele informatii:
cnt(i, j) = cate numere intre 0 si 10^i-1 contin j cifre de C (vom considera ca numerele pot avea 0-uri in fata, de exemplu: 0003 are 3 cifre de 0)
Acest numar se poate calcula fie printr-o formula matematica folosind combinari sau cu o relatia de recurenta (independenta de variabila C):
cnt(i, j) = 9 * cnt(i-1, j) + cnt(i-1, j-1)
Pentru a afla probabilitatea ceruta trebuie sa aflat cate numere exista in intervalul [{$A..B$}] cu cel putin $K$ cifre de {$C$}. Pentru asta vom construi o functia $f(x)$ care va returna cate numere sunt in intervalul [{$0..x-1$}] care au cel putin $K$ cifre de {$C$}. Astfel rezultatul va fi {$f(B+1)-f(A)$}. Functia $f(x)$ va rula in complexitate $O(lg x)$ parcurgand numarul $x$ cifra cu cifra. Ca sa realizam acest lucru avem nevoie de urmatoarele informatii:
$cnt(i, j)$ = cate numere intre $0$ si $10^i^-1$ contin $j$ cifre de $C$ (vom considera ca numerele pot avea {$0$}-uri in fata, de exemplu: $0003$ are $3$ cifre de {$0$})
Acest numar se poate calcula fie printr-o formula matematica folosind combinari sau cu o relatia de recurenta (independenta de variabila {$C$}):
* $cnt(i, j) = 9 * cnt(i-1, j) + cnt(i-1, j-1)$
De asemenea mai avem nevoie de urmatoarele informatii:
cnt0(i, j) = cate numere care nu au 0-uri in fata intre 0 si 10^i-1 contin j cifre de C
Relatia de recurenta va fi in functie de C:
daca C=0 atunci cnt0(i, j) = cnt0(i-1, j) + 9 * cnt(i-1, j)
altfel cnt0(i, j) = cnt0(i-1, j) + 8 * cnt(i-1, j) + cnt(i-1, j-1)
Cele doua matrici au marimi lgB*K deci construirea lor va avea complexitate O(lg B*K). Odata disponibile aceste informatii se poate realiza destul de usor functia f(x). Nu voi prezenta aici toate detaliile deoarecere apar mai multe cazuri (in special cand C = 0), lasand ca exercitiu pentru cititor. O alta rezolvare posibila ar fi calcularea functiei f(x) in O(2^lg10(x)*lg10(x)) astfel: pe fiecare pozitie intre 0 si lg10(x) avem doua variante, fie punem cifra C, fie alta cifra. Pentru fiecare astfel de configuratie cu cel putin K cifre de C se poate determina dintr-o parcurgere cate numere exista < x care au cifre de C in pozitiile respective.
$cnt0(i, j)$ = cate numere care nu au {$0$}-uri in fata intre $0$ si $10^i^-1$ contin $j$ cifre de {$C$}. Relatia de recurenta va fi in functie de {$C$}:
* daca $C=0$ atunci $cnt0(i, j) = cnt0(i-1, j) + 9 * cnt(i-1, j)$
* altfel $cnt0(i, j) = cnt0(i-1, j) + 8 * cnt(i-1, j) + cnt(i-1, j-1)$
Cele doua matrici au marimi $lgB*K$ deci construirea lor va avea complexitate {$O(lg B*K)$}. Odata disponibile aceste informatii se poate realiza destul de usor functia {$f(x)$}. Nu voi prezenta aici toate detaliile deoarecere apar mai multe cazuri (in special cand {$C = 0$}), lasand ca exercitiu pentru cititor.
O alta rezolvare posibila ar fi calcularea functiei $f(x)$ in $O(2^lg10(x)^*lg10(x))$ astfel: pe fiecare pozitie intre $0$ si $lg10(x)$ avem doua variante, fie punem cifra {$C$}, fie alta cifra. Pentru fiecare astfel de configuratie cu cel putin $K$ cifre de $C$ se poate determina dintr-o parcurgere cate numere exista $< x$ care au cifre de $C$ in pozitiile respective.
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" de la .campion 2005, 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:
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:
1, 2, 3, ... N-M, N, N-1, N-2, ... N-M+1
$1, 2, 3, ... N-M, N, N-1, N-2, ... N-M+1$
Cele K inversiunile apar in ultimele M elemente. Daca in aceasta permutare mutam un element N-x imediat inaintea lui N numarul de inversiuni scade cu x. Astfel, daca K>M*(M-1)/2 construim permutarea
Cele $K$ inversiuni apar in ultimele $M$ elemente. Daca in aceasta permutare mutam un element $N-x$ imediat inaintea lui $N$ numarul de inversiuni scade cu {$x$}. Astfel, daca $K>M*(M-1)/2$ construim permutarea
1, 2, 3, ... N-M-1, N, N-1, N-2, ... N-M
$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 minim lexicografica. Algoritmul descris are complexitate {$O(N)$}.
h2. Clasele 11-12
