h2. Matrix
(problema grea clasa a 9-a, problema medie clasa a 10-a)
Primul pas al algoritmului este calcularea numarului de aparitii ale fiecarei litere in matricea de $N*N$. Prima idee care ne vine in minte este ca pentru toate submatricile posibile sa calculam numarul de aparitii ale fiecarei litere si sa comparam cu valorile care trebuie obtinute. Acest algoritm are complexitatea $O(M^2*(N+S)^)$, unde $S$ este dimensiunea alfabetului. Aceasta abordare obtine $50$ de puncte.
Primul pas al algoritmului este calcularea numarului de aparitii ale fiecarei litere in matricea de $N*N$. Prima idee care ne vine in minte este ca pentru toate submatricile posibile sa calculam numarul de aparitii ale fiecarei litere si sa comparam cu valorile care trebuie obtinute. Acest algoritm are complexitatea $O(M^2^*(N+S))$, unde $S$ este dimensiunea alfabetului. Aceasta abordare obtine $50$ de puncte.
Vom verifica pentru toate cele {@(M-N)@}$^2^$ matrici posibile daca sunt sau nu permutari ale matricii-template. Apoi, pentru fiecare litera a alfabetului, efectuam urmatoarea preprocesare pentru a putea calcula in $O(1)$ numarul de aparitii ale literei din orice submatrice: $T{~i,j~}$ = numarul de aparitii pe pozitii $(x, y)$ cu $1 ≤ x ≤ i$ si $1 ≤ y ≤ j$.
Relatia de recurenta este $T{~i,j~} = T{~i-1,j~}+T{~i,j-1~}-T{~i-1,j-1~}$, la care se adauga $1$ daca si numai daca pe pozitia $(i, j)$ se afla litera pe care o cautam. In aceste conditii, numarul de aparitii ale literei curente in submatricea cu colturile in $(i-N+1, j-N+1)$ si $(i, j)$ este $T{~i,j~}-T{~i-N,j~}-T{~i,j-N~}+T{~i-N,j-N~}$. Aceasta solutie are complexitatea $O(M^2*S^)$. Daca se foloseste $O(M^2*S^)$ memorie se obtin $70-80$ de puncte, iar pentru punctaj maxim este necesara reducerea la $O(M^2^)$. Acest lucru poate fi realizat folosind doua matrici, una in care tinem minte daca pentru o anumita pozitie s-a gasit vreo litera pentru care numarul de aparitii nu coincide cu cel dorit, si una in care se efectueaza preprocesarea pentru litera curenta. O alta optimizare, mult mai nesimnificativa, si care nu este necesara pentru $100$ de puncte, este renuntarea la verificarea pentru ultima litera, deoarece daca primele $25$ de litere s-au potrivit, iar numarul de litere este constant, e clar ca si cea de-a $26$-a litera se va potrivi.
Relatia de recurenta este $T{~i,j~} = T{~i-1,j~}+T{~i,j-1~}-T{~i-1,j-1~}$, la care se adauga $1$ daca si numai daca pe pozitia $(i, j)$ se afla litera pe care o cautam. In aceste conditii, numarul de aparitii ale literei curente in submatricea cu colturile in $(i-N+1, j-N+1)$ si $(i, j)$ este $T{~i,j~}-T{~i-N,j~}-T{~i,j-N~}+T{~i-N,j-N~}$. Aceasta solutie are complexitatea $O(M^2*S^)$. Daca se foloseste $O(M^2^*S)$ memorie se obtin $70-80$ de puncte, iar pentru punctaj maxim este necesara reducerea la $O(M^2^)$. Acest lucru poate fi realizat folosind doua matrici, una in care tinem minte daca pentru o anumita pozitie s-a gasit vreo litera pentru care numarul de aparitii nu coincide cu cel dorit, si una in care se efectueaza preprocesarea pentru litera curenta. O alta optimizare, mult mai nesimnificativa, si care nu este necesara pentru $100$ de puncte, este renuntarea la verificarea pentru ultima litera, deoarece daca primele $25$ de litere s-au potrivit, iar numarul de litere este constant, e clar ca si cea de-a $26$-a litera se va potrivi.
h2. Lista lui Andrei
