Concursul s-a dovedit a fi o adevarata proba de foc, o batalie cu fum de creiere din plin si cu multe iesiri la toaleta (vezi "Cronica":preoni-2006/finala/cronica). Problemele, la limita imposibilului. Comisia a nascocit cele mai nastrusnice provocari pentru o finala in care participau concurenti adevarati, gata sa dea peste cap toate topurile Olimpiadelor ce vor voni. Muschi incordati, "trac, tensiune, stress". La sfarsit, punctaje reflectand truda demna de admirat a unor campioni alergand pe ultima suta de metri a unei curse in 5 acte. Castigatorii au fost sa fie, de acesta data, Cosmin Gheorghe la clasa a IX a, Simion Alexandru la clasa a X a si Marin Radu la clasele XI-XII. Ii felicitam pe ei si, in aceeasi masura, pe toti participantii care, desi au ratat premiile, cu siguranta au castigat prieteni noi.

Sa trecem la analiza problemelor cu care cei 29 concurenti nazdravani au avut de-a face in cele 5 ore ale finalei. Orice sugestie sau corectie privind articolul, solutiile problemelor v-o puteti exprima pe "forum":http://infoarena.ro/forum.

Sa trecem la analiza problemelor cu care cei 29 concurenti nazdravani au avut de-a face in cele 5 ore ale finalei. Orice sugestie sau corectie privind articolul, solutiile problemelor v-o puteti exprima pe "forum":forum.

h2. DivK
h3. (problema usoara clasa a IX-a, problema usoara clasa a X-a)

Exista solutii evidente $O(N * (A-B))$ si $O(N * K)$ care obtin punctaje partiale si asupra carora nu se va insista in acest articol. Solutia care obtine insa $100$ de puncte este $O(N)$ si nu este greu de gasit, bazandu-se pe cateva observatii. Sa notam cu $S{~i~}$ suma primelor $i$ numere din sir. Pentru ca subsecventa intre pozitiile $i$ si $j$ sa aiba suma elementelor divizibila cu $K$, atunci $S{~j~}-S{~i-1~}$ trebuie sa fie divizibil cu $K$, sau altfel spus, $S{~i-1~}$ si $S{~j~}$ sa aiba acelasi rest la impartirea cu $K$. Daca stim sa aflam raspunsul problemei pentru subsecvente de lungime maxim $L$ si minim {$1$}, aplicand de doua ori algoritmul pentru $B$ si pentru $A-1$ si scazand cele doua valori obtinute vom obtine numarul de subsecvente cu proprietatea ceruta intre $A$ si $B$ inclusiv. Pentru a afla raspunsul pentru lungimea maxim $L$ procedam astfel: introducem in lista $LISTA{~r~}$ alocata dinamic pozitiile $i$ pentru care $S{~i~}$ da restul $r$ la impartirea cu $K$, in ordine crescatoare. Pentru fiecare rest de la $0$ la $K-1$ parcurgem lista
corespunzatoarea, si, daca ne aflam pe un element cu valoarea $p2$ si elementul cel mai din stanga din lista curenta are valoarea $p1$ astfel incat $p2-p1 ≤ L$, atunci cand avansam in lista nu mai este necesar sa incepem iterarea listei de la inceput pentru aflarea valorii cea mai din stanga, fiind suficient sa reluam cautarea din dreptul valorii $p1$. Astfel complexitatea algoritmului pentru o lista este $O(LUNGIME)$, unde $LUNGIME$ este lungimea unei liste, deci complexitatea intregului algoritm va fi $O(N)$, pentru ca lungimea tuturor listelor este $N$.

Exista solutii evidente $O(N * (A-B))$ si $O(N * K)$ care obtin punctaje partiale si asupra carora nu se va insista in acest articol. Solutia care obtine insa $100$ de puncte este $O(N)$ si nu este greu de gasit, bazandu-se pe cateva observatii. Sa notam cu $S{~i~}$ suma primelor $i$ numere din sir. Pentru ca subsecventa intre pozitiile $i$ si $j$ sa aiba suma elementelor divizibila cu $K$, atunci $S{~j~}-S{~i-1~}$ trebuie sa fie divizibil cu $K$, sau altfel spus, $S{~i-1~}$ si $S{~j~}$ sa aiba acelasi rest la impartirea cu $K$. Daca stim sa aflam raspunsul problemei pentru subsecvente de lungime maxim $L$ si minim {$1$}, aplicand de doua ori algoritmul pentru $B$ si pentru $A-1$ si scazand cele doua valori obtinute vom obtine numarul de subsecvente cu proprietatea ceruta intre $A$ si $B$ inclusiv. Pentru a afla raspunsul pentru lungimea maxim $L$ procedam astfel: introducem in lista $LISTA{~r~}$ alocata dinamic pozitiile $i$ pentru care $S{~i~}$ da restul $r$ la impartirea cu $K$, in ordine crescatoare. Pentru fiecare rest de la $0$ la $K-1$ parcurgem lista corespunzatoarea, si, daca ne aflam pe un element cu valoarea $p2$ si elementul cel mai din stanga din lista curenta are valoarea $p1$ astfel incat $p2-p1 ≤ L$, atunci cand avansam in lista nu mai este necesar sa incepem iterarea listei de la inceput pentru aflarea valorii cea mai din stanga, fiind suficient sa reluam cautarea din dreptul valorii $p1$. Astfel complexitatea algoritmului pentru o lista este $O(LUNGIME)$, unde $LUNGIME$ este lungimea unei liste, deci complexitatea intregului algoritm va fi $O(N)$, pentru ca lungimea tuturor listelor este $N$.

O alta solutie de aceeasi complexitate dar mai rapida este urmatoarea: daca notam cu @v[r]@ de cate ori apare restul $r$ in numerele $S{~i-B~}...S{~i-A+1~}$ pentru pasul curent $i$, atunci la pasul $i+1$ este suficient sa decrementam $v[S{~i-B+1~}%K]$ si sa incrementam $v[S{~i-A+2~}%K]$. La fiecare pas $i$ vom aduna la solutia finala numarul $v[S{~i~}%K]$.
h2. Lupul Urias si Rau

O rezolvare ce aduce 100 de puncte se bazeaza pe metoda greedy. Pentru fiecare valoare $j$ de la $T_max$ la $1$ se adauga intr-o multime toate cantitatile de lana $A{~i~}$ pentru oile cu {$T{~i~}=j$}, apoi se extrage valoarea maxima care se adauga la solutie, restul valorilor pastrandu-se in multime pentru pasul urmator. Atentie, se va extrage valoarea maxima chiar daca la acest pas nu s-au introdus valori noi in multime. Pentru a implementa eficient aceste operatii ne vom folosi un heap care suporta operatiile de extragere maxim si adaugare element in {$O(log n)$}. Complexitatea finala a algoritmului va fi de {$O(n log n)$}. Demonstratia intuitiva a faptului ca algoritmul conduce la solutie optima este ca la fiecare pas $j$ se alege valoarea maxima dintre cele care nu vor mai putea fi alese la pasul {$j+1$}.

O alta solutie tot greedy a problemei este sortarea descrescatoare dupa cantitatile de lana. Pentru fiecare valoare apoi se vede cel mai mare timp mai mic sau egal cu {$T{~i~}$} si la care nu a mai fost aleasa nici o alta oaie. Daca exista un astfel de timp se adauga valoare respectiva la solutie. Acest lucru se poate realiza cu o cautare binara a acestui timp. O alternativa la acest lucru ar fi folosirea multimilor disjuncte. Initial se considera fiecare moment de timp o multime. Notam $X$ = minimul din multimea care il contine pe {$T{~i~}$}. Daca alegem $A{~i~}$ pentru a-l aduaga la solutie se va reuni multimea care il contine pe $X$ cu multimea care il contine pe {$X-1$}. Aceasta rezolvare insa este considerata peste nivelul mediu al clasei a 9-a.

O alta solutie tot greedy a problemei este sortarea descrescatoare dupa cantitatile de lana. Pentru fiecare valoare apoi se vede cel mai mare timp mai mic sau egal cu {$T{~i~}$} si la care nu a mai fost aleasa nici o alta oaie. Daca exista un astfel de timp se adauga valoare respectiva la solutie. Acest lucru se poate realiza cu o cautare binara a acestui timp. O alternativa la acest lucru ar fi folosirea multimilor disjuncte. Initial se considera fiecare moment de timp o multime. Notam $X$ = minimul din multimea care il contine pe {$T{~i~}$}. Daca alegem $A{~i~}$ pentru a-l adauga la solutie se va reuni multimea care il contine pe $X$ cu multimea care il contine pe {$X-1$}. Aceasta rezolvare insa este considerata peste nivelul mediu al clasei a 9-a.

h2. Overlap
h3. (problema grea clasa a IX-a)

Observam ca exista doar $4$ rotatii posibile ale planului, facand abstractie de translatii. Daca $CMAX$ este coordonata maxima, atunci punctul ({$i, j$}) se transforma in ({$CMAX-j, i$}), iar dupa $4$ aplicari ale acestei transformari se ajunge din nou la punctul initial. Asadar, vom incerca pe rand fiecare dintre aceste posibilitati. Avand fixata o rotatie, stim ca punctul $1$ se transforma intr-un alt punct $i$ ({$i > 1$}), sau ca un punct $i$ se transforma in el. Cel de-al doilea caz este redundant, deoarece aplicand transformarea {$P{~i~} -> {{~1~}$}, vom lua in considerare si transformarea inversa. De exemplu, daca rotind planul cu $k*90$ de grade si translatandu-l cu $shift_X$ si $shift_y$ obtinem $P{~i~}$ din {$P{~j~}$}, atunci rotind planul cu $(4-k)*90$ grade si translatandu-l cu {$-shift_x$}, {$-shift_y$} vom obtine $P{~j~}$ din {$P{~i~}$}.

Observam ca exista doar $4$ rotatii posibile ale planului, facand abstractie de translatii. Daca $CMAX$ este coordonata maxima, atunci punctul ({$i, j$}) se transforma in ({$CMAX-j, i$}), iar dupa $4$ aplicari ale acestei transformari se ajunge din nou la punctul initial. Asadar, vom incerca pe rand fiecare dintre aceste posibilitati. Avand fixata o rotatie, stim ca punctul $1$ se transforma intr-un alt punct $i$ ({$i > 1$}), sau ca un punct $i$ se transforma in el. Cel de-al doilea caz este redundant, deoarece aplicand transformarea {$P{~i~} -> P{~1~}$}, vom lua in considerare si transformarea inversa. De exemplu, daca rotind planul cu $k*90$ de grade si translatandu-l cu $shift_X$ si $shift_y$ obtinem $P{~i~}$ din {$P{~j~}$}, atunci rotind planul cu $(4-k)*90$ grade si translatandu-l cu {$-shift_x$}, {$-shift_y$} vom obtine $P{~j~}$ din {$P{~i~}$}.

Odata fixata rotatia pe care o consideram (inclusiv cea de $0$ grade), presupunem pe rand pentru fiecare punct $i > 1$ ca $P{~1~}$ se transforma in {$P{~i~}$}, si verificam daca aceasta presupunere conduce la o solutie valida. Presupunerea facuta stabileste in mod unic care este translatia efectuata. Retinem un vector $P{~i~}$ = punctul in care se transforma al {$i$}-lea punct dupa aplicarea rotatiei fixate si a translatiei determinate, sau $-1$ daca punctul transformat nu se regaseste printre cele initiale. Pentru a realiza in mod eficient aceasta operatie, la inceputul algoritmului punctele se sorteaza cu o functie de comparare oarecare si la fiecare pas punctul dorit se cauta binar in acest vector, in {$O(log N)$}. Eventual s-ar putea folosi un tabel de dispersie, insa consideram ca aceasta structura de date este prea complicata pentru nivelul clasei a 9-a si nu era necesara pentru obtinerea punctajului maxim.
Avand vectorul {$P$}, va exista o structura de lanturi si cicluri rezultata in urma aplicarii repetate {$P[P[..P[i]]]$} asupra diverselor puncte. Se poate demonstra usor ca exista solutie daca si numai daca toate lanturile si toate ciclurile au lungime para; in acest caz solutia se poate obtine etichetand alternativ punctele consecutive dintr-un lant sau ciclu.

Pentru a calcula {$A[k, i, j]$} ne vom uita fie in {$A[k-1]$} daca {$S1[i] = S2[j] = S3[k]$}, fie in {$A[k]$} ({$S1[i] = S2[j]$}, {$S1[i] != S3[k]$}). Se vor aduna valorile {$A[k (sau k-1), p, q]$} cu {$p<i$}, {$q<j$} si {$S1[p] &le; S1[i]$}.

h3. Solutia O(N*M^2*P) - 50 puncte

h3. Solutia O(N*M^2^*P) - 50 puncte

Se porneste de la solutia anterioara si se observa faptul ca pentru fiecare $q$ care se considera se poate preprocesa suma {$A[k (sau k-1), p, q]$} pentru $p < i$ intr-un tablou {$S$}. Dupa ce se calculeaza {$A[k, i, j]$} considerand doar acele $q$ pentru care {$S2[q] &le; S2[j]$}, se actualizeza {$S[k, j]$}.

h3. Solutia O(N*M*P*lgSigma) - 100 puncte

Solutia de $100$ este asemantoare cu solutia de $75$ de puncte, singura diferenta fiind folosirea unui arbore indexat binar pentru a face in $O(lg Sigma)$ operatiile desccrise mai sus.

Solutia de $100$ este asemantoare cu solutia de $75$ de puncte, singura diferenta fiind folosirea unui arbore indexat binar pentru a face in $O(lg Sigma)$ operatiile descrise mai sus.