Solutia care ar fi obtinut punctajul maxim se bazeaza pe reducerea problemei la nivel de vector, descrisa in paragraful precedent. Fie {$SEC = sqrt(N)$}. Putem imparti vectorul de lungime $N$ in $SEC$ secvente de lungime {$SEC$}. Vom mai folosi 3 vectori $A[1..N]$ reprezentand sumele pe fiecare element ce au fost adunate la inceputul secventelor de lungime {$SEC$}, $C[1..SEC]$ reprezinta sumele ce s-au adunat pe intregile secvente, iar $P[1..SEC][1..1 000 000]$ este o matrice binara unde $P[i][j] = 1$ daca exista un element din secventa $i$ astfel incat {$A[element] = j$}. Aceasta idee ne ajuta sa rezolvam problema intr-o complexitate de $O(sqrt(n))$ atat pentru query cat si pentru update. Pentru ca memoria folosita sa fie rezonabila implementarea matricii $P$ se face pe biti.
h2. Pedefe
(problema grea clasele XI-XII)
h3. (problema grea clasele XI-XII)
Problema cere determinarea numarului de subsiruri comune crescatoare al sirurilor $S1$ si $S2$ , care-l contin pe $S3$ ca subsir. Pentru a rezolva vom folosi metoda programarii dinamice. Se va construi un tabel $A$ cu semnificatia:
$A[k,i,j]$ = cate subsiruri comune crescatoare exista tinand cont doar de primele $i$ valori ale lui {$S1$}, primele $j$ valori ale lui {$S2$}, si care sa contina ca subsir primele $k$ caractere din {$S3$}, iar ultima valoare din aceste subsiruri sa fie {$S1[i]$}. Valorile din tablou se vor calcula doar atunci cand {$S1[i] = S2[j]$}, in rest valorile vor fi {$0$}. In implementare, se vor pastra doar ultimele doua linii din tabloul {$A$}, {$A[k-1]$} si {$A[k]$}.
Problema cere determinarea numarului de subsiruri comune crescatoare al sirurilor S1 si S2 , care-l contin pe S3 ca subsir. Pentru a rezolva vom folosi metoda programarii dinamice. Se va construi un tabel A cu semnificatia:
A[k,i,j] = cate subsiruri comune crescatoare exista tinand cont doar de primele i valori ale lui S1, primele j valori ale lui S2, si care sa contina ca subsir primele k caractere din S3, iar ultima valoare din aceste subsiruri sa fie S1[i]. Valorile din tablou se vor calcula doar atunci cand S1[i] = S2[j], in rest valorile vor fi 0. In implementare, se vor pastra doar ultimele doua linii din tabloul A, A[k-1] si A[k].
In continuare se vor prezenta mai multe implementari bazate pe aceasta idee cu diferite complexitati si care aduc punctaje diferite.
h3. Solutia O(N^2^*M^2^*P) - 30 puncte
* Solutia O(N^2*M^2*P) - 30 puncte
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] <= S1[i].
* 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] <= S2[j], se actualizeza S[k, j].
* Solutia O(N*M*P*Sigma) - 75 puncte
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] ≤ S1[i]$}.
In cazul cel mai devaforabil numarul de valori distincte din siruri este min(N, M), dar se garanteaza in enunt ca Sigma (numarul de valori distincte) este <= 20 pentru inca 25% din teste. Pornind de la solutia anterioara, se observa ca , parcurgand j-ul de la 1 la M, nu este necesar sa consideram de fiecare data toate valorile q < j, aceste informatii putand fi actualizate in O(1). Deoarece trebuie sa numaram doar valorile cu S2[q] <= S2[j], se pastreaza intr-un vector V[x] , suma q-urilor < j , cu S2[q] <= x. Calculul lui A[k,i,j] se face in O(Sigma), iar dupa aceasta se actualizeaza vectorul V in O(1).
h3. Solutia O(N*M^2*P) - 50 puncte
* Solutia O(N*M*P*lgSigma) - 100 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] ≤ S2[j]$}, se actualizeza {$S[k, j]$}.
Solutia de 100 este asemantoare cu solutia de 75 de puncte, singura diferenta fiind folosirea unui arbore indexat binar pentru a face in O(lgSigma) operatiile desccrise mai sus.
h3. Solutia O(N*M*P*Sigma) - 75 puncte
References
In cazul cel mai devaforabil numarul de valori distincte din siruri este {$min(N, M)$}, dar se garanteaza in enunt ca $Sigma$ (numarul de valori distincte) este $≤ 20$ pentru inca $25%$ din teste. Pornind de la solutia anterioara, se observa ca , parcurgand {$j$}-ul de la $1$ la {$M$}, nu este necesar sa consideram de fiecare data toate valorile {$q < j$}, aceste informatii putand fi actualizate in {$O(1)$}. Deoarece trebuie sa numaram doar valorile cu {$S2[q] ≤ S2[j]$}, se pastreaza intr-un vector {$V[x]$} , suma {$q$}-urilor {$< j$} , cu {$S2[q] ≤ x$}. Calculul lui {$A[k,i,j]$} se face in {$O(Sigma)$}, iar dupa aceasta se actualizeaza vectorul $V$ in {$O(1)$}.
Visible links
1. http://infoarena.devnet.ro/forum/index.php/topic,935.0.html
2. http://infoarena.devnet.ro/forum/index.php/topic,999.0.html
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.
