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://http://forum.infoarena.ro/.

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

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

* {$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":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:

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