//Articolul nu este complet ediat. O sa-l editez maine, acum ma duc sa ma culc pt ca sunt rupt :D Somn usor tuturor.
h1. Solutii
h1. Chiftea (problema usoara, clasele 9-10)
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":echipa-infoarena pentru suportul tehnic acordat si ii rog sa ma ierte daca i-am stresat (prea tare).
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.
Mult noroc in continuare,
Bogdan A. Stoica
h1. Mall (problema medie, clasele 9-10)
h2. Chiftea
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 ≤ k ≤ 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.
h3. problema usoara, clasele 9-10
h1. Fear (problema usoara, clasele 11-12)
Vom nota cu P{~k~}, perimetrul minim al figurii ce contine $k$ patratele de latura unitate. In mod evident, acesta depinde numai de patratelele ce formeaza marginea figurii.
Vom trata intai cazul in care $N$ este patrat perfect pornind de la $N = 1$, cu $P{~1~} = 4$. Pentru $N = 4$, construind toate figurile posibile se observa ca cea de perimetru minim are forma unui patrat cu latura $2$, deci $P{~4~} = 4*2 = 8$. Continuand procedeul, se demonstreaza cu ajutorul principiului inducitei matematice ca $P{~t~} = 4*[radical(t)]$ (cu $[x]$ s-a notat partea intreaga a lui $x$), oricare ar fi $t$ patrat perfect.
Pentru al doilea caz, cel in care $N$ nu este patrat perfect, figura noastra porneste tot de la un patrat de latura $[radical(N)]$. Este evident faptul ca pentru ca $P{~N~}$ sa fie minim, trebuie sa avem cat mai putine patratele (pe margine) carora li se aduna mai mult de o latura la perimetru (cu alte cuvinte trebuie sa avem cat mai putine patratele care sa formeze colturi). Va trebui, deci, sa adaugam pe marginile patratului format $N-[radical(N)]*[radical(N)]$ patratele. Astfel solutia devine $4*[radical(N)]$ pentru $N$ patrat perfect, $4*[radical(N)]+2$ pentru cazul in care acoperim maxim o latura cu patratele sau $4*[radical(N)]+4$ pentru cazul in care acoperim maxim 2 laturi cu patratele.
O solutie care calcula aceste valori in O({$N$}) nu ar fi obtinut punctaj maxim.
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.
h2. Mall
h1. Smen (problema grea, clasele 9-10 - problema medie, clasele 11-12)
h3. problema medie, clasele 9-10
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)
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).
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]+Castig[l, k])$ ({$0 < l < i$}, {$0 ≤ k ≤ j$}), unde $Castig[i, j]$ = castigul pe care-l obtine Varu de la firma $i$ daca acesteia ii repratizaza exact $j$ ingrijitori.
O solutie care calcula in O({$N^4^$}) aceasta recurenta ar fi obtinut $16$ puncte.
O solutie care calcula in O({$N^3^$}), folosind matricea $V[i, j]$ = $maxim(A[k, j]+Castig[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.
h1. 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.
h2. Smen
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)).
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.
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 calculam $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 dintre:
h1. Doipe (problema grea, clasele 11-12)
# $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)
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,..,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^).
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 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$})).
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 nenaturale care priveste valoarea fricii dintr-o intersectie, problema se reduce la aflarea fluxului maxim avand orasul $1$ ca sursa si orasul $N$ ca destinatie. Pentru realizarea acestui 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$.
Aceasta metoda poarta denumirea de "Flux maxim prin scalare". O alta abordare care ar fi mers la fel de bine este cea folosind algoritmul de flux maxim Ford Fulkerson.
h2. Doipe
h3. problema grea, clasele 11-12
Prima solutie corecta este de complexitate O(N*2^N^). Se calculeaza o matrice $P[i, R]$ = numarul de permutari cu $i$ elemente, care respecta sirul de relatii $R$ ({$R$} este un numar binar de $i - 1$ biti, care codifica un sir de relatii). Putem calcula aceste valori pe baza valorilor calculate pentru $P[i - 1, R']$, variind pozitia in care este asezat in cadrul permutarii cel de-al $i$-lea element. Aceasta solutie nu se incadreaza, insa, nici in limita de timp, nici in cea de memorie.
Ideea solutiei de punctaj maxim este urmatoarea: 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^$}).
