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).
Mult noroc in continuare,

Bogdan A. Stoica

Bogdan A. Stoica $

h2. Chiftea
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 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 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 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:

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

# 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$.

h2. Smen
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 sis a-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.