T[i] = T[i - 1] + T[i - 3] + 2 * (i - 2)
==
Pentru cei mai curiosi din fire, vom demonstra cum se ajunge la aceasta formula. Fie $A{~i~}$ numarul permutarilor de lungime $i$ care au $1$ pe prima sau ultima pozitie, adica dublul numarului permutarilor care au $1$ pe prima pozitie (exceptie face, ca in toti pasii care vor urma, permutarea de lungime {$1$}). De asemenea, fie $B{~i~}$ numarul permutarilor de lungime $i$ care nu au $1$ pe prima sau ultima pozitie. Evident, {$T{~i~} = A{~i~} + B{~i~}$}. Primele valori sunt
== code(cpp) |A[1] = 1, B[1] = 0
Pentru cei mai curiosi din fire, vom demonstra cum se ajunge la aceasta formula. Fie A[i] numarul permutarilor de lungime i care au 1 pe prima sau ultima pozitie, adica dublul numarului permutarilor care au 1 pe prima pozitie (exceptie face, ca in toti pasii care vor urma, permutarea de lungime 1). De asemenea, fie B[i] numarul permutarilor de lungime i care nu au 1 pe prima sau ultima pozitie. Evident, T[i] = A[i] + B[i]. Primele valori sunt
A[1] = 1, B[1] = 0
A[2] = 2, B[2] = 0
A[3] = 4, B[3] = 2
A[4] = 8, B[4] = 4
==
Pentru calculul lui $A$ consideram urmatoarele cazuri:
# incepem permutarea cu $1, 2$ => avem $A{~i-1~}$ posibilitati
# incepem permutarea cu $1, 3, 2, 4$ => avem $A{~i-3~}$ posibilitati
# incepem permutarea cu $1, 3$ dar nu continuam cu $2$ => vom mai avea o singura posibilitate, de forma ({$1, 3, 5, 7, 9, 8, 6, 4, 2$}). Adica ``urcam'' cu numerele impare si ``coboram'' cu cele pare pana la {$2$}. Bineinteles, aceasta posibilitate poate fi considerata si in sens invers.
Deci {$A{~i~} = A{~i-1~} + A{~i-3~} + 2$}.
Pentru calculul lui $B$ incepem cu numarul $1$ si observam ca celelalte numere pot fi completate doar alternativ (stanga-dreapta sau dreapta-stanga) pana la un anumit pas, si incepand de pe pozitia la care ne-am oprit, in unul din modurile calculate precedent. Pentru $i = 7$ incepand cu $1$ avem cazurile:
* ({$3, 1, 2$}) => in continuare A{~5~} moduri
* ({$3, 1, 2, 4$}) => in continuare A{~4~} moduri
* ({$5, 3, 1, 2, 4$}) => in continuare A{~3~} moduri
* ({$5, 3, 1, 2, 4, 6$}) => in continuare A{~2~} moduri
* ({$7, 5, 3, 1, 2, 4, 6$}) => in continuare A{~1~} moduri
Observam ca valorile calculate precedent in $A$ sunt de fapt dublul celor de care avem noi nevoie, dar considerand si modul invers de completare alternativa, rezultatul obtinut va fi cel corect.
Deci {$B{~i~} = A{~i-2~} + A{~i-3~} + ... + A{~1~}$}, adica {$B{~i~} = B{~i-1~} + A{~i-2~}$}.
Pentru calculul lui A consideram urmatoarele cazuri:
1) incepem permutarea cu 1, 2 => avem A[i - 1] posibilitati
2) incepem permutarea cu 1, 3, 2, 4 => avem A[i - 3] posibilitati
3) incepem permutarea cu 1, 3 dar nu continuam cu 2 => vom mai avea o singura posibilitate, de forma (1, 3, 5, 7, 9, 8, 6, 4, 2). Adica ``urcam'' cu numerele impare si ``coboram'' cu cele pare pana la 2. Bineinteles, aceasta posibilitate poate fi considerata si in sens invers.
Deci A[i] = A[i - 1] + A[i - 3] + 2.
Pentru calculul lui B incepem cu numarul 1 si observam ca celelalte numere pot fi completate doar alternativ (stanga-dreapta sau dreapta-stanga) pana la un anumit pas, si incepand de pe pozitia la care ne-am oprit, in unul din modurile calculate precedent. Pentru i = 7 incepand cu 1 avem cazurile:
(3, 1, 2) => in continuare A[5] moduri
(3, 1, 2, 4) => in continuare A[4] moduri
(5, 3, 1, 2, 4) => in continuare A[3] moduri
(5, 3, 1, 2, 4, 6) => in continuare A[2] moduri
(7, 5, 3, 1, 2, 4, 6) => in continuare A[1] moduri
Observam ca valorile calculate precedent in A sunt de fapt dublul celor de care avem noi nevoie, dar considerand si modul invers de completare alternativa, rezultatul obtinut va fi cel corect.
Deci B[i] = A[i - 2] + A[i - 3] + .. + A[1], adica B[i] = B[i - 1] + A[i - 2].
Am ajuns la urmatoarele 2 siruri recurente:
A[i] = A[i - 1] + A[i - 3] + 2
B[i] = B[i - 1] + A[i - 2]
Mai facem urmatoarea observatie: A[i] - B[i - 1] = (A[i - 1] + A[i - 3] + 2) - (B[i - 2] + A[i - 3]) = A[i - 1] - B[i - 2] + 2, ceea ce inseamna ca A[i] - B[i - 1] = 2 * (i - 1) (demonstratie prin inductie, tinand cont de faptul ca A[2] + B[1] = 2).
In sfarsit, sa calculam sirul T[i] = A[i] + B[i].
T[i] = A[i] + B[i] = A[i - 1] + A[i - 3] + 2 + B[i - 1] + A[i - 2] = (A[i - 1] + A[i - 3]) + (B[i - 1] + B[i - 3]) + (A[i - 2] - B[i - 3]) + 2 = T[i - 1] + T[i - 3] + (A[i - 2] - B[i - 3]) + 2. Dupa cum am observat mai devreme A[i - 2] - B[i - 3] = 2 * (i - 3) => T[i] = T[i - 1] + T[i - 3] + 2 * (i - 2), ceea ce ne propusesem sa demonstram.
Punctajele se obtin in modul urmator:
-O(N^2) timp, O(N) memorie ~ 50%
-O(N) timp, O(N) memorie ~ 70%
-O(N) timp, O(1) memorie ~ 90-100%
* $A{~i~} = A{~i-1~} + A{~i-3~} + 2$
* $B{~i~} = B{~i-1~} + A{~i-2~}$
Mai facem urmatoarea observatie: {$A{~i~} - B{~i-1~} = (A{~i-1~} + A{~i-3~} + 2) - (B{~i-2~} + A{~i-3~}) = A{~i-1~} - B{~i-2~} + 2$}, ceea ce inseamna ca {$A{~i~} - B{~i-1~} = 2 * (i - 1)$} (demonstratie prin inductie, tinand cont de faptul ca {$A{~2~} + B{~1~} = 2$}).
In sfarsit, sa calculam sirul {$T{~i~} = A{~i~} + B{~i~}$}.
{$T{~i~} = A{~i~} + B{~i~} = A{~i-1~} + A{~i-3~} + 2 + B{~i-1~} + A{~i-2~} = (A{~i-1~} + A{~i-3~}) + (B{~i-1~} + B{~i-3~}) + (A{~i-2~} - B{~i-3~}) + 2 = T{~i-1~} + T{~i-3~} + (A{~i-2~} - B{~i-3~}) + 2$}. Dupa cum am observat mai devreme $A{~i-2~} - B{~i-3~} = 2 * (i - 3)$ => {$T{~i~} = T{~i-1~} + T{~i-3~} + 2 * (i - 2)$}, ceea ce ne propusesem sa demonstram.
Punctajele se obtin in modul urmator:
* $O(N^2^)$ timp, $O(N)$ memorie ~ $50%$
* $O(N)$ timp, $O(N)$ memorie ~ $70%$
* $O(N)$ timp, $O(1)$ memorie ~ $90-100%$
Desc
h2. Desc
(clasa a 10-a problema grea, clasele 11-12 problema usoara)
h3. (clasa a 10-a problema grea, clasele 11-12 problema usoara)
Problema se rezolva folosind metoda programarii dinamice. Notam D numarul de divizori ai lui N si tinem vectorul dvz[i] sortat cu divizorii lui N. Vom construi matricea A[i][j] cu semnificatia numarul de descompuneri ale lui dvz[i] cu cei mai mari j divizori.
Vom procesa divizorii de la cel mai mare la cel mai mic. Cand procesam divizorul i il vom inmulti cu toti ceilalti divizori, iar pentru aceia pentru care obtinem un divizor al lui N actualizam matricea.
Aceasta se poate construi in complexitate O(d^2 log d) (daca folosim cautare binara pentru a afla al cate-lea divizor este x) sau se poate reduce la O(d^2) folosind hash. Evident solutia se va gasi in A[d][1].
Pentru a gasi cea a K-a descompunere ne vom folosi de aceasta matrice. Cand punem divizorul dvz[i] pe prima pozitie vom avea A[poz(N/dvz[i])][i] posibilitati unde poz(x) returneaza indicele la care se gaseste x in vectorul dvz.
O observatie evidenta ar fi faptul ca in cadrul produsului nu vor aparea decat divizorii lui {$N$}. De aceea vom creea vectorul $dvz$ care contine toti cei $D$ divizori ai lui N. In continuare se va construi matricea {$A$}, unde elementul {$A{~i,j~}$} va retine numarul de posibilitati de a obtine divizorul {$i$}, folosind divizorii {$j$}, {$j+1$}, ..., $D$. Aceasta se va construi in ordine descrescatoare a coloanelor. Initial $A{~i,j~}= A{~i,j+1~}$ deoarce se vor folosi aceleasi moduri de descompunere folosind divizorii {$j+1$}, {$j+2$}, ..., {$D$}, apoi vom lua in considerare cazul in care se foloseste divizorul {$j$}. Pentru asta trebuie ca {$dvz{~j~}$} sa divida pe {$dvz{~i~}$}, iar in acest caz vom adauga la $A{~i,j~}$ pe $A{~X,j~}$ unde $X$ este indicele divizoului {$dvz{~i~}/dvz{~j~}$}. Procesarea unei coloane trebuie sa se faca crescator deoarece {$X < i$}. Cautarea lui X se poate face fie binar, dar daca ne uitam mai atent vom observa ca valorile lui {$X$} sunt crescatoare deci putem continua cautarea liniar de la pasul la care ne oprisem pentru {$i-1$}. Acest lucru va asigura o complexitate totala {$O(D)$} pentru fiecare coloana a matricii. Complexitatea totala rezultand {$O(D^2^)$}. Singura initializare care trebuie facuta va fi {$A{~0,i~} = 1$} pentru {$1 ≤ i ≤ D$} deoarce se considera ca se poate obtine produsul $1$ intr-un singur mod, iar rezultatul se va gasi in {$A{~D,1~}$}.
Pentru a gasi cea de a {$K$}-a descompunere a lui $N$ ne vom folosi de aceasta matrice. Incercam pe rand sa punem fiecare divizor pe prima pozitie. Cand punem divizorul $i$ pe prima pozitie vom avea $A{~X,i~}$ posibilitati unde $X$ reprezinta indicele divizorului {$N/dvz{~i~}$}. Daca numarul acestor posibilitati este mai mic strict decat $K$ se va scadea acest numar din $K$ deoarece toate descompunerile care incep cu $dvz{~i~}$ sunt mai mici lexicografic decat varianta cautata de noi. Daca numarul acestor posibilitati este mai mare sau egal cu $K$ atunci descompunerea cautata de noi incepe cu {$dvz{~i~}$} si vom cauta in continuare a {$K$}-a descompunere pentru $N/dvz{~i~}$ folosind insa divizori mai mari decat {$dvz{~i~}$}.
h2.Struti
Struti
h3. (clasele 11-12 problema medie)
(clasele 11-12 problema medie)
Vom incerca sa rezolvam fiecare oferta in O(M*N), complexitatea finala a algoritmului fiind astfel O(P*M*N). Matricea de altitudini o vom nota cu mat. Intai vom determina maximul pe portiuni dreptunghiulare de forma [i,j]-[i+DX-1,j+DY-1], iar apoi, prin aceeasi metoda vom afla si minimul. Pentru a afla maximul pe astfel de portiuni, vom nota cu
MAX[i][j] = max{mat[i][j], mat[i+1][j].... mat[i+DX-1][y]}. Pentru fiecare coloana, vom utiliza o stiva sortata crescator dupa linii si descrescator dupa valoare altitudinilor. Stiva va retine elemente situate pe pozitii intre i si i+DX-1, cu altitudinile sortate descrescator.
