h1. preONI 2005 runda #3 - solutii

(Creat de ==user(user="domino" type="tiny")== la data de _2005-03-20_ categoria _Competitii_, autor(i) _Echipa devNet_)

(Categoria _Competitii_, autor(i) _Echipa devNet_)

Articolul contine ideile de rezolvare ale problemelor propuse la ultima runda a concursului preONI ce s-a desfasurat pe data de 20 martie 2005, cat si comentarii legate de concurs. Si de aceasta data numarul de participanti a fost impresionat, cu siguranta datorita faptului ca in numai 5 zile incepe ONI!

Setul de probleme a fost mai greu de data aceasta, special pentru a testa concurentii cu probleme cat mai asemanatoare cu stilul ONI. Speram ca fiecare participant a invatat cate ceva in urma acestui concurs si asteptam pareri si sugestii pentru viitor pe "forum":http://www.infoarena.ro/Forum.

Setul de probleme a fost mai greu de data aceasta, special pentru a testa concurentii cu probleme cat mai asemanatoare cu stilul ONI. Speram ca fiecare participant a invatat cate ceva in urma acestui concurs si asteptam pareri si sugestii pentru viitor pe "forum":http://infoarena.ro/forum/.

h2. Clasele 9-10
h3. Clasament

==Rankings(rounds="preoni53a" display_entries="7" pager_style="none")==

==Rankings(rounds="preoni53a" display_entries="6" pager_style="none")==

h3. Barman

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 multimea 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.

* 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.

Cele doua matrice 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":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
h3. Clasament

==Rankings(rounds="preoni53b" display_entries="6" pager_style="none")==

==Rankings(rounds="preoni53b" display_entries="5" pager_style="none")==

Setul de probleme, mai greu de data aceasta, se pare ca a pus in dificultate majoritatea concurentilor. Desi problemele Critice si Poligon nu erau foarte dificile in faza de concepere a algoritmului se pare ca implementarea a fost cea care i-a speriat pe multi dintre participanti.

* {$A{~i,j~} = max(A{~i,j-1~}, A{~i-1,k~} + S{~j~} - S{~k~})$}, pentru fiecare $k<j$

Al doilea termen este de forma $A{~i-1,k~} - S{~k~}$ (termen independent de {$j$}) + {$S{~j~}$}. Astfel din linia $i-1$ a matricii de dinamica pentru fiecare $j$ ne trebuie valoarea maxima $A{~i-1,k~}-S{~k~}$ cu {$k<j$}. O prima idee ar fi ca pe masura ce construim linia i sa inseram elementele din linia $i-1$ intr-un max-heap astfel reducand complexitatea la {$O(N*lgN*K)$}.

Al doilea termen este de forma $A{~i-1,k~} - S{~k~}$ (termen independent de {$j$}) + {$S{~j~}$}. Astfel din linia $i-1$ a matricei de dinamica pentru fiecare $j$ ne trebuie valoarea maxima $A{~i-1,k~}-S{~k~}$ cu {$k<j$}. O prima idee ar fi ca pe masura ce construim linia i sa inseram elementele din linia $i-1$ intr-un max-heap astfel reducand complexitatea la {$O(N*lgN*K)$}.

Cei care au rezolvat probleme precum "secventa":http://www.infoarena.ro/task/secventa de pe info-arena, "trans":http://www.infoarena.ro/task/trans de la barajul de la ONI 2004 sau divide de la USACO Ianuarie 2005 vor realiza imediat ca putem reduce complexitatea la $O(N*K)$ folosind structura necesara in rezolvarea acelor probleme si anume o coada (in literatura de specialitate se intalneste ca "deque with heap order"). Aceasta structura a mai fost tratata si in solutiilor problemelor prezentate mai sus, deci nu voi intra in detalii. Este evident ca un algoritm de complexitate $O(N*K)$ se incadreaza in timp, dar mai apare in calcul faptul ca sirul este circular. Un algoritm $O(N*K)$ care nu trateaza acest lucru ia $40$ de puncte. O prima idee ar fi sa aplicam acelasi algoritm pe fiecare permutare circulara dar se ridica complexitatea iar la {$O(N^2^*K)$}. Aceasta abordare ar trebui sa obtina intre $50$ si $60$ de puncte. Putem trata circularitatea sirului tot in $O(N*K)$ incercand sa obtinem o secventa care contine elemente $N$ si {$1$}. Putem realiza acest lucru astfel:

Cei care au rezolvat probleme precum "secventa":problema/secventa de pe infoarena, "trans":problema/trans de la barajul de la ONI 2004 sau divide de la USACO Ianuarie 2005 vor realiza imediat ca putem reduce complexitatea la $O(N*K)$ folosind structura necesara in rezolvarea acelor probleme si anume o coada (in literatura de specialitate se intalneste ca "deque with heap order"). Aceasta structura a mai fost tratata si in solutiilor problemelor prezentate mai sus, deci nu voi intra in detalii. Este evident ca un algoritm de complexitate $O(N*K)$ se incadreaza in timp, dar mai apare in calcul faptul ca sirul este circular. Un algoritm $O(N*K)$ care nu trateaza acest lucru ia $40$ de puncte. O prima idee ar fi sa aplicam acelasi algoritm pe fiecare permutare circulara dar se ridica complexitatea iar la {$O(N^2^*K)$}. Aceasta abordare ar trebui sa obtina intre $50$ si $60$ de puncte. Putem trata circularitatea sirului tot in $O(N*K)$ incercand sa obtinem o secventa care contine elemente $N$ si {$1$}. Putem realiza acest lucru astfel:

* dupa ce realizam prima data dinamica, reinitializam linia $1$ astfel $A{~1,i~} = S{~i~}$
* aplicam din nou dinamica -> de data aceasta algoritmul va fi obligat sa intoarca rezultate care contin neaparat elementul $1$ intr-o secventa din cauza initializarii

Astfel, problema este rezolvabila in complexitate {$O(N*K)$}.

h3. Poligon

h3(#poligon). Poligon

Problema cere sa determinam cate puncte din cele $M$ sunt in interiorul poligonului. O abordare imediata a acestei probleme ar fi sa determinam pentru fiecare punct in $O(N)$ daca este sau nu in interiorul poligonului. Exista mai multe moduri de a rezolva acest lucru. Un mod ar fi sa ducem o semidreapta pornind din punctul nostru si sa vedem de cate ori intersecteaza laturile poligonului: daca intersecteaza poligonul de un numar par de ori atunci inseamna ca punctul este in exterior, iar daca ea intersecteaza de un numar impar de ori laturile poligonului inseamna ca punctul este in interior. O alta modalitate: calculam suma unghiurilor pe care le fac extremele laturilor cu punctul nostru (unghiurile sunt luate pozitive sau negative dupa cum cele $3$ puncte ce formeaza unghiul sunt in sens trigonometric sau orar), daca suma unghiurilor pentru toate laturile e $0$ atunci punctul e in exteriorul poligonului, iar daca suma unghiurilor e $2*Pi$ atunci punctul e in interiorul poligonului, pentru mai multe detalii puteti
sa va uitati pe urmatoarele pagini: "[1]":http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html "[2]":http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm