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.