h3. problema medie, clasele 9-10

Calculam $A[i][j]$ = castigul maxim pe care-l obtine Varu daca repartizeaza $j$ ingrijitori primelor $i$ firme, unde $A[i][j]$ = $maxim(A[l][j-k])$ ($0 < l < i, 0 &le; k &le; j$).
O solutie care calcula in O($N^4^$) aceasta recurenta ar fi obtinut $16$ puncte.
O solutie care calcula in O($N^3^$), tiand $V[i][j]$ = $maxim(A[k][j])$ ($0 <  k < i$), obtinea $32$ de puncte.
O solutie care calcula in O($N^2^$), folosind un deque ce calcula in O($1$) maximul (pentru linia $i$ si coloana $j$) dintre $V{[i]}[1]$, $V[i][2]$, ..., $V[i][j-1]$, obtinea $100$ de puncte.

Calculam $A[i, j]$ = castigul maxim pe care-l obtine Varu daca repartizeaza $j$ ingrijitori primelor $i$ firme, unde $A[i, j]$ = $maxim(A[l, j-k])$ ($0 < l < i, 0 &le; k &le; j$).
O solutie care calcula in O({$N^4^$}) aceasta recurenta ar fi obtinut $16$ puncte.
O solutie care calcula in O({$N^3^$}), tiand $V[i, j]$ = $maxim(A[k, j])$ ($0 <  k < i$), obtinea $32$ de puncte.
O solutie care calcula in O({$N^2^$}), folosind un deque ce calcula in O($1$) maximul (pentru linia $i$ si coloana $j$) dintre $V{[i]}[1]$, $V[i, 2]$, ..., $V[i, j-1]$, obtinea $100$ de puncte.

h2. Fear

h3. problema grea, clasele 9-10 - problema medie, clasele 11-12

Incepem prin a normaliza toate numerele din sir si pe $A$ si $B$, adunand tuturor valoarea $200$. Astfel vom lucra numai cu numere pozitive. Apoi problema se rezolva prin programare dinamica. Sortam in ordine crescatoare elementele si apoi clauculam $A[i][j][k]$ = numarul minim de operatii ce se efectueaza asupra primelor $i$ numere a.i. sa obtinem exact $j$ elemente distincte iar ultimul element sa nu depaseasca valoarea $k$.
$A[i][j][k]$ se poate obtine ca fiind maximul dinntre:

Incepem prin a normaliza toate numerele din sir si pe $A$ si $B$, adunand tuturor valoarea $200$. Astfel vom lucra numai cu numere pozitive. Apoi problema se rezolva prin programare dinamica. Sortam in ordine crescatoare elementele si apoi clauculam $A[i, j, k]$ = numarul minim de operatii ce se efectueaza asupra primelor $i$ numere a.i. sa obtinem exact $j$ elemente distincte iar ultimul element sa nu depaseasca valoarea $k$.
$A[i, j, k]$ se poate obtine ca fiind maximul dinntre:

# $A[i-1][j][k-1]$ + $|Val_initiala[i]-k|$ (daca vrem ca valoarea initiala a celui de-al $i$-lea element sa fie $k$, dar sa nu-mi creeze un alt element distinct).
# $A[i-1][j-1][k-1]+|Val_initiala[i]-k|$ (daca vrem ca valoarea initiala a celui de-al $i$-lea element sa fie $k$ si sa-mi creez inca un element dinstinct)
# $A[i-1][j][k-1]$ (nu cresc nici valoarea elementului $i$, nici numarul de elemente distincte)

# $A[i-1, j, k-1]$ + $|Val_initiala[i]-k|$ (daca vrem ca valoarea initiala a celui de-al $i$-lea element sa fie $k$, dar sa nu-mi creeze un alt element distinct).
# $A[i-1, j-1, k-1]+|Val_initiala[i]-k|$ (daca vrem ca valoarea initiala a celui de-al $i$-lea element sa fie $k$ si sa-mi creez inca un element dinstinct)
# $A[i-1, j, k-1]$ (nu cresc nici valoarea elementului $i$, nici numarul de elemente distincte)

Pentru reconstituire vom lucra cu o matrice $B[i][j][k]$ care ia valori din multimea {$0$, $1$, $2$}, semnificand conditia din care a provenit starea ($i$,$j$,$k$). Se observa ca aceasta solutie ar fi obtinut foloseste foarte multa memorie (O($N*K*$($B$-$A$)) si ar fi obtinut doar $40%$ din punctaj.

Pentru reconstituire vom lucra cu o matrice $B[i, j, k]$ care ia valori din multimea {$0$, $1$, $2$}, semnificand conditia din care a provenit starea ($i$,$j$,$k$). Se observa ca aceasta solutie ar fi obtinut foloseste foarte multa memorie (O($N*K*$($B$-$A$)) si ar fi obtinut doar $40%$ din punctaj.

Solutia $100$ de puncte incepe prin a observa ca, la un pas, nu sunt folosite decat "linia" curenta si "linia" anterioara din matricea $A$. Pentru reconstituire se poate folosi urmatorul smen: retinem din $14$ in $14$ "linii" informatiile din matricea $A$ (cea de la prima solutie), adica $R[1][j][k]$ =  $A[1][j][k]$ ($1 ≤ j ≤ K$ si $A+200 ≤ k ≤ B+200$), $R[2][j][k]$ = $A[15][j][k]$ ($1 ≤ j ≤ K$ si $A+200 ≤ k ≤ B+200$), $R[3][j][k]$ = $A[29][j][k]$ ($1 ≤ j ≤ K$ si $A+200 ≤ k ≤ B+200$), etc. Dupa ce am completat matricea $R$, reluam dinamica de la coada la cap si ne vom folosi doar de matricea $R$. Astfel la pasul $i$ vom reconstitui doar liniile care se afla intre liniile $R[i][j][k]$ si $R[i-1][j][k]$ ($1 ≤ j ≤ K$ si $A+200 ≤ k ≤ B+200$), adica intre ($i-1$)$*14+1$ si $i*14+1$ in matricea de la prima solutie. Astfel o sa avem o memorie de O($14*K*$($B-A$)).

Solutia $100$ de puncte incepe prin a observa ca, la un pas, nu sunt folosite decat "linia" curenta si "linia" anterioara din matricea $A$. Pentru reconstituire se poate folosi urmatorul smen: retinem din $14$ in $14$ "linii" informatiile din matricea $A$ (cea de la prima solutie), adica $R[1, j, k]$ =  $A[1, j, k]$ ($1 ≤ j ≤ K$ si $A+200 ≤ k ≤ B+200$), $R[2, j, k]$ = $A[15, j, k]$ ($1 ≤ j ≤ K$ si $A+200 ≤ k ≤ B+200$), $R[3, j, k]$ = $A[29, j, k]$ ($1 ≤ j ≤ K$ si $A+200 ≤ k ≤ B+200$), etc. Dupa ce am completat matricea $R$, reluam dinamica de la coada la cap si ne vom folosi doar de matricea $R$. Astfel la pasul $i$ vom reconstitui doar liniile care se afla intre liniile $R[i, j, k]$ si $R[i-1, j, k]$ ($1 ≤ j ≤ K$ si $A+200 ≤ k ≤ B+200$), adica intre ($i-1$)$*14+1$ si $i*14+1$ in matricea de la prima solutie. Astfel o sa avem o memorie de O($14*K*$($B-A$)).

O alta solutie care obtinea punctaj maxim este transformarea problemei intr-una de cuplaj de cost minim. Cele doua multimi de noduri se construiau in felul urmator: prima multime era reprezentata de sirul initial, iar cea de-a doua era reprezentata de valorile intregi cuprinse in intervalul $[A, B]$. Se introduc $N*$($B-A$) muchii de capacitate $1$, o muchie de la un nod ce leaga elementul $X$ din prima multime si elementul $Y$ din a doua multime avand costul $|X-Y|$. Prima multime se leaga de o sursa fictiva prin muchii de cost $0$ si capacitate $1$, iar cea de-a doua multime de o destinatie fictive prin muchii de cost $0$ si capacitate $1$. Tinandu-se cont ca in destinatie trebuie sa se obtina fluxul minim $K$, se aplica acest algoritm avand grija sa minimizam costul.

h3. problema grea, clasele 11-12

	Vom calcula $P[i][j]$ = numarul de permutari ale multimii {$1$,$2$,..,$i$} care respecta primele $i-1$ relatii ale sirului de relatii si in care ultimul numar al permutarii este numarul $j$. In mod evident, rezultatul dorit va fi dat de suma $P[N][1]$ + $P[N][2]$ + .. + $P[N][N]$.
	Pentru calculul lui $P[i][j]$ vom observa ca, eliminand numarul $j$ din permutare, obtinem $i-1$ numere distincte care pot fi renumerotate pentru a forma o permutare a multimii {$1$,$2$,..,$i-1$}. Mai exact, orice numar $x$ mai mare decat $j$ este renumerotat cu valoarea $x-1$. In conditiile acestei renumerotari, avem urmatoarele $2$ cazuri:

	Vom calcula $P[i, j]$ = numarul de permutari ale multimii {$1$,$2$,..,$i$} care respecta primele $i-1$ relatii ale sirului de relatii si in care ultimul numar al permutarii este numarul $j$. In mod evident, rezultatul dorit va fi dat de suma $P[N, 1]$ + $P[N, 2]$ + .. + $P[N, N]$.
	Pentru calculul lui $P[i, j]$ vom observa ca, eliminand numarul $j$ din permutare, obtinem $i-1$ numere distincte care pot fi renumerotate pentru a forma o permutare a multimii {$1$,$2$,..,$i-1$}. Mai exact, orice numar $x$ mai mare decat $j$ este renumerotat cu valoarea $x-1$. In conditiile acestei renumerotari, avem urmatoarele $2$ cazuri:

* daca relatia $i-1$ este "$<$", atunci $P[i, j]$ = $P[i-1, 1]$ + $P[i-1, 2]$ + .. + $P[i-1, j-1]$
* daca relatia $i-1$ este "$>$", atunci $P[i, j]$ = $P[i-1, j]$ + $P[i-1, j+1]$ + .. + $P[i-1, i-1]$

Cazul "de baza" este $P[1][1]$ = $1$. Relatiile date sunt corecte, deoarece pentru orice permutare ce corespunde lui $P[i-1][x]$ se poate aplica operatia de renumerotare inversa (relativ la $j$), obtinand un sir de $i-1$ numere distincte din multimea {$1$,$2$,..,$i$}\{$j$} care respecta primele $i-2$ relatii. La sfarsitul acestui sir se poate adauga numarul $j$, obtinand o permutare cu $i$ elemente care respecta primele $i-1$ relatii.
	Implementarea imediata a relatiilor de recurenta mentionate se poate realiza foarte usor in complexitate O({$N^3^$}). Memorand sumele partiale $SP[x]$ = $P[i-1][1]$ + $P[i-1][2]$ + .. + $P[i-1][x]$ putem calcula $P[i][j]$ in timp O($1$), reducand complexitatea la O($N^2^$).

Cazul "de baza" este $P[1, 1]$ = $1$. Relatiile date sunt corecte, deoarece pentru orice permutare ce corespunde lui $P[i-1, x]$ se poate aplica operatia de renumerotare inversa (relativ la $j$), obtinand un sir de $i-1$ numere distincte din multimea {$1$,$2$,..,$i$}\{$j$} care respecta primele $i-2$ relatii. La sfarsitul acestui sir se poate adauga numarul $j$, obtinand o permutare cu $i$ elemente care respecta primele $i-1$ relatii.
	Implementarea imediata a relatiilor de recurenta mentionate se poate realiza foarte usor in complexitate O({$N^3^$}). Memorand sumele partiale $SP[x]$ = $P[i-1, 1]$ + $P[i-1, 2]$ + .. + $P[i-1, x]$ putem calcula $P[i, j]$ in timp O($1$), reducand complexitatea la O($N^2^$).