h3. problema usoara, clasele 9-10
Se observa ca figura se obtine dintr-un patrat de latura $radical(N)$, la care se mai adauga niste patratele, solutia fiind $4*radical(N)$ (pentru $N$ patrat perfect) sau $4*(radical(N)+1)$ ({$-2$}, dupa caz :p).

O solutie care calcula aceste valori in O(n) nu ar fi obtinut punctaj maxim.

O solutie care calcula aceste valori in O(($N$}) nu ar fi obtinut punctaj maxim.

h2. Mall

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.