h1. Solutii

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 ii rog sa ma ierte daca i-am stresat (prea tare :P).

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 ii rog sa ma ierte daca i-am stresat (prea tare).

Mult noroc in continuare,
Bogdan A. Stoica

O solutie care calcula in O({$N^3^$}), folosind matricea $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 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$.
 

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

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. Fear
 
h3. problema usoara, clasele 11-12
 
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$.
 

h2. Doipe
h3. problema grea, clasele 11-12