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.
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.
h2. Doipe
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]
* 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,..,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^$).
