Diferente pentru preoni-2006/runda-4/solutii intre reviziile #21 si #27

Nu exista diferente intre titluri.

Diferente intre continut:

Una peste alta, s-a incheiat o etapa frumoasa a concursului in care am pus mult suflet. Normal, pot fi doar 30 de participanti fericiti de rezultate. Ii felicitam pe cei calificati si abia asteptam sa-i vedem in finala. Ii felicitam si pe ceilalti care nu au putut sa-si tina suflul pana in final, pierzand locurile calificabile. Noi le uram cat mai multe succese, sa mai alerge vreo cateva sute de probleme (incepand cu cele din Arhiva noastra) si sa ne intalnim cu ei mult mai pregatiti la startul urmatorului preONI.
In urmatoarele pagini vom incerca sa explicam solutiile problemelor. Asa cum v-ati obisnuit, va puteti lamuri orice vi se pare neclar sau vag explicat intreband pe "forum":http://forum.infoarena.ro/, unde vom incerca sa raspundem cat mai promt. Va asteptam cu intrebari si sugestii (asigurati-va ca pareririle va sunt auzite!)
In urmatoarele pagini vom incerca sa explicam solutiile problemelor. Asa cum v-ati obisnuit, va puteti lamuri orice vi se pare neclar sau vag explicat intreband pe "forum":http://forum.infoarena.ro/, unde vom incerca sa raspundem cat mai prompt. Va asteptam cu intrebari si sugestii (asigurati-va ca pareririle va sunt auzite!)
h2. NextSeq
(problema simpla clasa a 9-a)
$A = T{~1~}^R1 * Q^ * ... * T{~K~}^RK * Q^$
Al doilea pas este sa observam ca daca aflam pentru fiecare $T{~i~}$, $B{~i~}$ astfel incat $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$ atunci $B$ (numarul cautat in problema) este maximul dintre $B{~i~}$. Implicatia imediata e ca putem sa ne ocupam de fiecare numar prim in parte fara sa tinem cont de celelalte.
Al treilea pas consta in determinarea $B{~i~}$-urilor cu ajutorul cautarii binare. Pentru o valoare candidata $X$ (din cautarea binara) trebuie sa calculam puterea lui $T{~i~}$ in descompunerea lui $X!$. Acest lucru se afla simplu ca fiind $[X/T{~i~}] + [X/T{~i~}^2^] + ...$ (unde prin $[x]$ intelegem partea intreaga a lui $x$). Cautarea binara se poate optimiza observand ca $B{~i~}$ este intotdeauna divizibil cu $T{~i~}$, ba mai mult nu va fi mai mare decat $(R{~i~} * Q) * T{~i~}$ (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga $K$ in intervalul $[1, R{~i~} * Q]$ astfel incat $B{~i~} = K * T{~i~}$ sa aiba propietata ca $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$. Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare $X$ are propietatea ca $X!$ se divide la $Y$ (unde lui $X$ si $Y$ le putem da semnificatiile dorite de noi) atunci, evident, si $(X + 1)!$ se divide la $Y$.
Al treilea pas consta in determinarea $B{~i~}$-urilor cu ajutorul cautarii binare. Pentru o valoare candidata $X$ (din cautarea binara) trebuie sa calculam puterea lui $T{~i~}$ in descompunerea lui $X!$. Acest lucru se afla simplu ca fiind $[X/T{~i~}] + [X/T{~i~}^2^] + ...$ (unde prin $[x]$ intelegem partea intreaga a lui $x$). Cautarea binara se poate optimiza observand ca $B{~i~}$ este intotdeauna divizibil cu $T{~i~}$, ba mai mult nu va fi mai mare decat $(R{~i~} * Q) * T{~i~}$ (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga $K$ in intervalul $[1, R{~i~} * Q]$ astfel incat $B{~i~} = K * T{~i~}$ sa aiba propietatea ca $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$. Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare $X$ are propietatea ca $X!$ se divide la $Y$ (unde lui $X$ si $Y$ le putem da semnificatiile dorite de noi) atunci, evident, si $(X + 1)!$ se divide la $Y$.
Solutia finala va avea complexitatea $O(√P * log Q * log Q)$. Exista o serie de solutii intermediare care permiteau obtinerea de punctaje suficient de mari si de aceea problema a fost considerata medie desi rezolvarea completa este destul de dificila.
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

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.