//Articolul nu este complet ediat. O sa-l editez maine, acum ma duc sa ma culc pt ca sunt rupt :D Somn usor tuturor.

In numele echipei Winter Challenge 2007 felicit toti participantii si le urez succes in viitoare confruntari. Totodata tin sa multumesc lui Mugurel Ionut Andreica si lui Sorin Stancu-Mara pentru ca au acceptat sa propuna subiecte alaturi de mine. Nu in ultimul rand tin sa multumesc echipei infoarena pentru suportul tehnic acordat si sa-i rog sa ma ierte daca i-am stresat (prea tare).

In numele echipei Winter Challenge 2007 felicit toti participantii si le urez succes in viitoare confruntari. Totodata tin sa multumesc lui Mugurel Ionut Andreica si lui Sorin Stancu-Mara pentru ca au acceptat sa propuna subiecte alaturi de mine. Nu in ultimul rand multumesc intregii "echipe infoarena":http://infoarena.ro/echipa-infoarena pentru suportul tehnic acordat si sa-i rog sa ma ierte daca i-am stresat (prea tare).

Mult noroc in continuare,
Bogdan A. Stoica

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).

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.
h2. Mall

h3. problema usoara, clasele 11-12

In ciuda proprietatii un pic ciudate care priveste valoarea fricii dintr-o intersectie, problema se reduce la aflarea fluxul maxim avand orasul $1$ ca sursa si orasul $N$ ca destinatie. Pentru a realiza acest lucru vom logaritma (in baza $2$, $e$ sau $10$) costurile muchiilor ce se dau in fisierul de intrare. Dintre toate aceste noi costuri o vom lua pe cea maxima ({$vmax$}). Algoritmul va fi urmatorul:

In ciuda proprietatii un pic nenaturala care priveste valoarea fricii dintr-o intersectie, problema se reduce la aflarea fluxul maxim avand orasul $1$ ca sursa si orasul $N$ ca destinatie. Pentru a realiza acest lucru vom logaritma (in baza $2$, $e$ sau $10$) costurile muchiilor ce se dau in fisierul de intrare. Dintre toate aceste noi costuri o vom lua pe cea maxima ({$vmax$}). Algoritmul va fi urmatorul:

# vom trimite frica (din orasul $1$) cu o valoare $V$ (initial, $V$ = $vmax$) pana cand frica nu va mai putea ajunge la destinatie.
# injumatatim pe $V$ si reluam algoritmul de la pasul $1$.

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.

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]$

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^$}).