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

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.

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.