h1. Solutii Happy Coding 2007   !happy-coding-2007/solutii?hc2007-logo.gif!

(toc){margin-left:0px}*{text-align:center} *Lista de probleme:*

(toc)*{text-align:center} *Lista de probleme*

* 'Abc2':happy-coding-2007/solutii#abc2
* 'Tritzi':happy-coding-2007/solutii#tritzi
* 'Regine 2':happy-coding-2007/solutii#regine2

h3. Solutia 2

Vom incerca sa calculam valorile $pmin[i]$ treptat. Vom parcurge pozitiile de la $1$ la $N$ si vom incerca sa incepem un palindrom avand centrul in pozitia $i$ (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile $i$ si $i+1$ (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia $i$, toate valorile $pmin[j]$, cu $j < i$ au fost calculate, iar valorile $pmin[k]$, $k > i$, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei $i$ (respectiv pozitiilor $i$ si {$i+1$}); la fiecare pas de extindere, vom incerca sa incrementam palindromul de la lungimea curenta $L$, la lungimea $L+2$ (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea $pmin[i-(L+1)/2]+1$ sa fie folosita pentru a micsora valoarea lui $pmin[i+(L+1)/2-1]$ (pentru cazul lungimii impare), respectiv valoarea $pmin[i-L/2]+1$ poate fi folosita pentru a micsora valoarea lui $pmin[i+L/2]$ (pentru cazul lungimii pare).

Vom incerca sa calculam valorile $pmin[i]$ treptat. Vom parcurge pozitiile de la $1$ la $N$ si vom incerca sa incepem un palindrom avand centrul in pozitia $i$ (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile $i$ si $i+1$ (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia $i$, toate valorile $pmin[j]$, cu $j < i$ au fost calculate, iar valorile $pmin[k]$, $k > i$, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei $i$ (respectiv pozitiilor $i$ si {$i+1$}); la fiecare pas de extindere, vom incrementa palindromul de la lungimea curenta $L$, la lungimea $L+2$ (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea $pmin[i-(L+1)/2]+1$ sa fie folosita pentru a micsora valoarea lui $pmin[i+(L+1)/2-1]$ (pentru cazul lungimii impare), respectiv valoarea $pmin[i-L/2]+1$ poate fi folosita pentru a micsora valoarea lui $pmin[i+L/2]$ (pentru cazul lungimii pare).

Complexitatea ambelor solutii este $O(N^2^)$, insa a doua solutie merge mai repede, in practica, deoarece ia in considerare numai palindroamele valide (care pot fi cel mult {$O(N^2^)$}).

Pentru fiecare punct $i$, se sorteaza toate celelalte $N-1$ puncte in jurul punctului $i$ (in functie de unghi). Parcurgand apoi punctele in ordinea sortata, vom determina numarul maxim de puncte avand acelasi unghi fata de $i$ (folosind o precizie corespunzatoare, de $10^-8^$, de exemplu). Fie acest numar $MAX{~i~}$. Raspunsul cautat este $maxim{MAX{~i~} + 1}$ si se obtine in complexitate $O(N^2^*logN)$.

*Cosmin:* problema s-a dat si la algoritmus. Acolo limita de timp era foarte stransa si solutiile ce au luat punctaj maxim aveau complexitate $O(N^2^)$. Ajungem la complexitatea aceasta, folosind un hash table pentru a determina numarul maxim de puncte cu acelasi unghi fata de $i$ in loc sa sortam punctele.
 

Solutia de complexitate $O(N^3^)$, in care se fixeaza $2$ puncte si se determina in $O(N)$ numarul de puncte ce se afla pe dreapta determinata de cele $2$ puncte, nu se incadreaza in timp.
h3. Probleme asemanatoare

h2(#cascaval). 'Cascaval':problema/cascaval

Rezolvarea problemei incepe cu o observatie ne neaparat evidenta. Sa presupunem ca in luna $j$, compania are $X$ kilograme de cascaval (produse in luna respectiva sau in lunile anterioare si stocate pana in luna $j$). Sa presupunem, de asemenea, ca aceste $X$ kilograme provin din productia de cascaval din $2$ luni diferite, $i1$ si $i2$. Vom calcula costurile obtinerii celor $X1$ si celor $X2$ kilograme de cascaval:

Rezolvarea problemei incepe cu o observatie nu neaparat evidenta. Sa presupunem ca in luna $j$, compania are $X$ kilograme de cascaval (produse in luna respectiva sau in lunile anterioare si stocate pana in luna $j$). Sa presupunem, de asemenea, ca aceste $X$ kilograme provin din productia de cascaval din $2$ luni diferite, $i1$ si $i2$. Vom calcula costurile obtinerii celor $X1$ si celor $X2$ kilograme de cascaval:

* $C1 = F{~i1~} + C{~i1~} * X1 + (S{~i1~} + S{~i1+1~} + .. + S{~j-1~}) * X1 = A1 + B1 * X1$
* $C2 = F{~i2~} + C{~i2~} * X2 + (S{~i2~} + S{~i2+1~} + .. + S{~j-1~}) * X2 = A2 + B2 * X2$

==code(c) |
cmin[ 0 ] = 0
pentru i de la 1 la N

cmin[i]=infinit
pentru j de la 1 la i
  cost_total = cmin[j-1] + F[j] + C[j] * D[j]
  cost_stocare=S[j]
  pentru k de la j+1 la i
    cost_total = cost_total + (C[j]+cost_stocare) * D[k]
    cost_stocare = cost_stocare + S[k]
  daca cost_total < cmin[i] atunci
    cmin[i]=cost_total

  cmin[i]=infinit
  pentru j de la 1 la i
    cost_total = cmin[j-1] + F[j] + C[j] * D[j]
    cost_stocare=S[j]
    pentru k de la j+1 la i
      cost_total = cost_total + (C[j]+cost_stocare) * D[k]
      cost_stocare = cost_stocare + S[k]
    daca cost_total < cmin[i] atunci
      cmin[i]=cost_total

==
	Se variaza valoarea lui $i$ de la $1$ la $N$ si pentru fiecare valoare incercam sa calculam $cmin[i]$. Pentru aceasta, incercam toate valorile $j ≤ i$ care pot reprezenta luna in care sunt produse kilogramele de cascaval necesare in luna $i$. Apoi calculam costul total pentru cazul in care luna $j$ produce cantitatea de cascaval necesara pentru a satisface cererile din lunile $j, j+1, .., i$. In cele din urma vom avea in $cmin[i]$ minimul dintre costurile corespunzatoare fiecarei variante de alegere a lunii $j$. Costul total minim pentru toate cele $N$ luni il avem in $cmin[N]$. Bineinteles, aceasta solutie nu se incadreaza in limita de timp.
h3. Programare dinamica cu complexitatea $O(N^2^)$

Algoritmul descris anterior are complexitatea $O(N^3^). El se poate optimiza, insa, usor la complexitatea $O(N^2^)$.

Algoritmul descris anterior are complexitatea $O(N^3^)$. El se poate optimiza, insa, usor la complexitatea $O(N^2^)$.

==code(c) |
cmin[ 0 ] = 0

  pentru j de la i la 1
    cost_stocare = cost_stocare + S[j] * dtotal
    dtotal = dtotal + D[j]

    cost_productie = F[j] + C[j]    dtotal

    cost_productie = F[j] + C[j] * dtotal

    cost_total = cmin[j-1] + cost_productie + cost_stocare
    daca cost_total < cmin[i] atunci
      cmin[i]=cost_total

Vom calcula valorile $Tmin[i][j]$, reprezentand numarul minim de pasi necesari pentru a distribui mesajul tuturor nodurilor din subarborele nodului $i$, considerand ca au fost efectuati primii $j$ pasi din cadrul strategiei optime a nodului $i$ si ca au fost taiate din subarborele lui $i$ toti subarborii primelor $j$ noduri care au primit mesajul direct de la nodul $i$. Evident, cand $i=1$, in $Tmin[ 1 ][ 0 ]$ vom avea numarul minim de pasi necesari pentru distributia mesajului la toate nodurile din arbore.

Vom calcula, in ordine (de la $j=0$), toate valorile $Tmin[i][j]$. Sa observam intai (pentru cazul $j=0$), ca $Tmin[i][0]$ trebuie sa fie mai mare sau cel putin egal cu $Tmin[f][ 0 ]$, unde $f$ este fiu al lui $i$. Vom cauta binar aceasta valoare, intre maximul dintre valorile $Tmin[f][0]$ si $N-1$. Sa presupunem ca am fixat, in cadrul cautarii binare, $T$ unitati de timp. Vom initializa fiecare fiu $f$ al lui $i$ ca aflandu-se in starea $s(f)=0$ (adica nu s-a efectuat nici o mutare din cadrul strategiei sale optime). Vom considera fiul $f$ al lui $i$ care are valoarea $Tmin[f][s(f)]$ maxima. Daca $T > Tmin[f][s(f)]$, atunci trimitem mesajul nodului $f$, scadem din T o unitate de timp si mergem mai departe (ignorand nodul $f$ de acum inainte). Daca, la un moment dat, avem $T = Tmin[f][s(f)]$, atunci se demonstreaza (nu foarte usor, dar nici prea greu) ca nodul $i$ trebuie sa trimita mesaj nodului $j$ care este al $s(f)+1$-lea nod la care ar trimite mesaj nodul $f$ in cadrul strategiei sale optime. In felul acesta, taiem subarborele nodului $j$, scadem $T$ cu $1$ unitate si trecem nodul $f$ din starea $s(f)$ in starea $s(f)+1$ (pentru ca deja s-a efectuat o mutare din cadrul strategiei sale optime). Daca, la un moment dat, $T < Tmin[f][s(f)]$, atunci trebuie incercata o valoare mai mare in cadrul cautarii binare.

Vom calcula, in ordine (de la $j=0$), toate valorile $Tmin[i][j]$. Sa observam intai (pentru cazul $j=0$), ca $Tmin[i][ 0 ]$ trebuie sa fie mai mare sau cel putin egal cu $Tmin[f][ 0 ]$, unde $f$ este fiu al lui $i$. Vom cauta binar aceasta valoare, intre maximul dintre valorile $Tmin[f][ 0 ]$ si $N-1$. Sa presupunem ca am fixat, in cadrul cautarii binare, $T$ unitati de timp. Vom initializa fiecare fiu $f$ al lui $i$ ca aflandu-se in starea $s(f)=0$ (adica nu s-a efectuat nici o mutare din cadrul strategiei sale optime). Vom considera fiul $f$ al lui $i$ care are valoarea $Tmin[f][s(f)]$ maxima. Daca $T > Tmin[f][s(f)]$, atunci trimitem mesajul nodului $f$, scadem din T o unitate de timp si mergem mai departe (ignorand nodul $f$ de acum inainte). Daca, la un moment dat, avem $T = Tmin[f][s(f)]$, atunci se demonstreaza (nu foarte usor, dar nici prea greu) ca nodul $i$ trebuie sa trimita mesaj nodului $j$ care este al $s(f)+1$-lea nod la care ar trimite mesaj nodul $f$ in cadrul strategiei sale optime. In felul acesta, taiem subarborele nodului $j$, scadem $T$ cu $1$ unitate si trecem nodul $f$ din starea $s(f)$ in starea $s(f)+1$ (pentru ca deja s-a efectuat o mutare din cadrul strategiei sale optime). Daca, la un moment dat, $T < Tmin[f][s(f)]$, atunci trebuie incercata o valoare mai mare in cadrul cautarii binare.

Inainte de a calcula $Tmin[i][j+1]$ dupa ce am calculat $Tmin[i][j]$, memoram in $Mut[i][j]$ nodul la care a trimis mesaj nodul $i$ prima data (adica al $j+1$-lea nod din cadrul strategiei optime a nodului $i$) si in $F[i][j]$ fiul din subarborele caruia face parte nodul $Mut[i][j]$. De asemenea, starile fiiilor nodului $i$ se seteaza la valorile pe care le aveau inainte de a calcula $Tmin[i][j]$, incrementand doar starea fiului $F[i][j]$ cu $1$ (sau eliminand de tot fiul $F[i][j]$, daca $F[i][j] = Mut[i][j]$). Vom termina calculul acestor valori atunci cand $Tmin[i][j]=0$.

Pe langa alegerea uneia dintre cele $2$ metode, sunt necesare cateva optimizari suplimentare, precum:
* ridicarea la puterea $P$ trebuie realizata folosind exponentiere logaritmica; in plus, chiar si in cadrul exponentierii logaritmice, putem sa nu efectuam toti pasii daca, la un moment dat, numarul de cifre ale numarului obtinut depaseste numarul de cifre ale lui $N$

* efectuarea tuturor calculelor intr-o baza mai mare decat $10$ (solutia oficiala foloseste baza ${10^4^$}), deoarece, astfel, numarul de cifre ale numerelor ce intervin in calcule scade simtitor.

* efectuarea tuturor calculelor intr-o baza mai mare decat $10$ (solutia oficiala foloseste baza $10^4^$), deoarece, astfel, numarul de cifre ale numerelor ce intervin in calcule scade simtitor.

* in cazul cautarii binare, intervalul initial de cautare nu trebuie sa fie $[1,N]$, ci un interval mai restrans (de exemplu, $[10^(X/P)-1^, 10^(X/P)+1^]$), unde $X$ este numarul de cifre ale numarului N dat.
O alta optimizare care ar fi putut avea un impact simtitor asupra timpului de executie este inmultirea a doua numere mari in complexitate $O(C*logC)$, unde $C$ este numarul de cifre ale acestora,  insa implementarea unei astfel de operatii ar fi fost mai complicata (si nu era necesara pentru a obtine punctaj maxim la problema) (vezi 'aici':http://numbers.computation.free.fr/Constants/Algorithms/fft.html)

h2(#tramvai). 'Tramvai':problema/tramvai

Se construieste un graf al punctelor de intersectie dintre oricare $2$ drepte. Acest graf are $O(N^2^)$ noduri, insa fiecare nod are cel mult $4$ vecini (cate $2$ pe fiecare din cele $2$ drepte care il determina). Problema se reduce acum la determinarea drumului minim intre $2$ puncte in acest graf. Algoritmul folosit de solutia oficiala este 'Dijkstra':http://en.wikipedia.org/wiki/Dijkstra's_algorithm cu heap, care are complexitatea $O(N^2^*logN)$, insa se poate folosi cu succes si algoritmul 'Bellman-Ford':http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, implementat folosind o coada (aceasta varianta, cunoscuta ca algoritmul Bellman-Ford-Moore, are o complexitate teoretica mare, dar, in practica, merge foare bine; este, posibil, insa, ca, in cazul acestei probleme, sa fie necesare unele optimizari pentru a se incadra in limita de timp - de exemplu, folosirea euristicii "parent checking").

Se construieste un graf al punctelor de intersectie dintre oricare $2$ drepte. Acest graf are $O(N^2^)$ noduri, insa fiecare nod are cel mult $4$ vecini (cate $2$ pe fiecare din cele $2$ drepte care il determina). Problema se reduce acum la determinarea drumului minim intre $2$ puncte in acest graf. Algoritmul folosit de solutia oficiala este 'Dijkstra':http://en.wikipedia.org/wiki/Dijkstra's_algorithm cu heap, care are complexitatea $O(N^2^*logN)$, insa se poate folosi cu succes si algoritmul 'Bellman-Ford':http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, implementat folosind o coada. Aceasta varianta, cunoscuta ca algoritmul Bellman-Ford-Moore, are o complexitate teoretica mare, dar, in practica, merge foare bine; este, posibil, insa, ca, in cazul acestei probleme, sa fie necesare unele optimizari pentru a se incadra in limita de timp - de exemplu, folosirea euristicii "parent checking". Aceasta euristica se refera la urmatoarea situatie: Sa presupunem ca am extras din coada nodul $X$ (primul nod din coada) si urmeaza sa incercam sa facem update-uri la distantele tuturor vecinilor nodului $X$, folosind distanta calculata pana acum pentru $X$. De asemenea, sa presupunem ca nodul care i-a facut update la distanta minima nodului $X$ este $T$ ({$T$} mai este numit si parintele lui $X$, deoarece este nodul chiar dinaintea lui $X$ de pe drumul minim pana la $X$). Inainte sa incercam sa facem update pentru toti vecinii lui $X$, verificam daca nodul $T$ se afla in coada. Daca se afla in coada, atunci nu mai facem update folosind nodul $X$ si trecem la urmatorul nod din coada. Motivul este urmatorul: Daca nodul $T$ se afla in coada, el a fost introdus acolo dupa ce i-a facut update distantei pana la nodul $X$; noua valoarea a distantei minime pana la $T$ este mai mica decat in momentul cand s-a calculat distanta minima pana la $X$, astfel ca, atunci cand vom extrage din coada nodul $T$, se va micsora in mod sigur si distanta pana la $X$. Prin urmare, nu are rost sa facem acum update-uri folosind nodul $X$, deoarece acesta are calculata o distanta despre care stim sigur ca va fi micsorata in curand.
 
 

h2(#biti3). 'Biti3':problema/biti3

Vom considera bitii fiecarui sir numerotati de la $N$ la $1$ (de la stanga la dreapta) si vom calcula $num[i, j]$ = numarul de siruri de $i$ biti, continand exact $j$ biti de $1$. $num[i, 0] = 1$. Pentru $j > i$, avem $num[i, j] = 0$ ; altfel, $num[i, j] = num[i-1, j] + num[i, j-1]$ (cele $2$ variante corespund deciziei de a plasa un bit de $0$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se afla $j$ biti de $1$, respectiv un bit de $1$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se mai afla doar $j-1$ biti de $1$). Alt mod de a calcula aceste valori este urmatorul: $num[i,j] = Combinari de i luate cate j$.

Vom considera bitii fiecarui sir numerotati de la $N$ la $1$ (de la stanga la dreapta) si vom calcula $num[i, j]$ = numarul de siruri de $i$ biti, continand exact $j$ biti de $1$. $num[i, 0] = 1$. Pentru $j > i$, avem $num[i, j] = 0$ ; altfel, $num[i, j] = num[i-1, j] + num[i-1, j-1]$ (cele $2$ variante corespund deciziei de a plasa un bit de $0$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se afla $j$ biti de $1$, respectiv un bit de $1$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se mai afla doar $j-1$ biti de $1$). Alt mod de a calcula aceste valori este urmatorul: $num[i,j] = Combinari de i luate cate j$.

Folosind aceste valori, vom determina bitii celui de-al $M$-lea sir, unul cate unul, pornind de la al $N$-lea bit. La fiecare pas, va trebui sa determinam cate siruri incep cu bitul $0$ si cate siruri incep cu bitul $1$. La inceput, vor exista $num[N-1,3]$ siruri care incep cu bitul $0$ si $num[N-1,2]$ siruri care incep cu bitul $1$. Este evident ca, la un anumit pas, toate sirurile care incep cu $0$ se vor afla inaintea tuturor sirurilor care incep cu $1$. De aceea, daca $M$ < numarul sirurilor care incep cu $0$, bitul respectiv va fi $0$; in caz contrar, bitul va fi $1$. Daca bitul este $1$, inainte de a trece la pasul urmator, va trebui sa actualizam valoarea lui $M$, in asa fel incat sa sarim peste toate sirurile care incep cu $0$ ({$M = M - numarul de siruri care incep cu 0$), precum si sa tinem cont de faptul ca am mai consumat inca un bit de $1$. Algoritmul in pseudocod este urmatorul:

Folosind aceste valori, vom determina bitii celui de-al $M$-lea sir, unul cate unul, pornind de la al $N$-lea bit. La fiecare pas, va trebui sa determinam cate siruri incep cu bitul $0$ si cate siruri incep cu bitul $1$. La inceput, vor exista $num[N-1,3]$ siruri care incep cu bitul $0$ si $num[N-1,2]$ siruri care incep cu bitul $1$. Este evident ca, la un anumit pas, toate sirurile care incep cu $0$ se vor afla inaintea tuturor sirurilor care incep cu $1$. De aceea, daca $M$ < numarul sirurilor care incep cu $0$, bitul respectiv va fi $0$; in caz contrar, bitul va fi $1$. Daca bitul este $1$, inainte de a trece la pasul urmator, va trebui sa actualizam valoarea lui $M$, in asa fel incat sa sarim peste toate sirurile care incep cu $0$ ({$M = M - numarul de siruri care incep cu 0$}), precum si sa tinem cont de faptul ca am mai consumat inca un bit de $1$. Algoritmul in pseudocod este urmatorul:

== code(c) | nrbiti = 3
for i = N -> 1

* 'Word Encoding / ACM ICPC NWERC 2004':http://acm.pku.edu.cn/JudgeOnline/problem?id=2058
* 'Coding of Permutations / POJ':http://acm.pku.edu.cn/JudgeOnline/problem?id=1349
* 'Bits of Trinity / ACM ICPC NWERC 1999':http://www.acm.inf.ethz.ch/ProblemSetArchive/B_EU_NWRC/1999/Problems.pdf'

* 'Cuvinte / Stelele Informaticii 2003':problema/cuvinte

* Parantezari / Baraj ONI 2000
h2(#clear). 'Clear':problema/clear

h4. Acoperirea cu numar minim de drumuri

Vom parcurge matricea pe linii, si pentru fiecare linie, pe coloane. Vom mentine o stare $S$ asemanatoare celei din solutia prezentata mai sus, la care se mai adauga un indice $C$ $(1 ≤ C ≤ N)$, avand semnificatia ca valorile de la $C+1$ la $N$ se refera la pozitiile de pe linia de deasupra, iar valorile de pe pozitiile de la $1$ la $C$ (din cadrul starii) se refera la linia curenta. Mentinand starea in acest fel, cand ajungem la elementul de pe linia $L$ si coloana $C$, vom calcula toate starile pentru care indicele este egal cu $C$. Pentru aceasta, vom parcurge toate starile $S'$ corespunzatoare coloanei anterioare ($C-1$ sau $N$, daca $C$ este prima coloana) si vom genera toate starile $S$ cu indicele egal cu $C$, avand de ales dintre urmatoarele optiuni:

Vom parcurge matricea pe linii, si pentru fiecare linie, pe coloane. Vom mentine o stare $S$ asemanatoare celei din solutia prezentata mai sus, la care se mai adauga un indice $C$ $(1 ≤ C ≤ N)$, avand semnificatia ca valorile de la $C+1$ la $N$ se refera la pozitiile de pe linia de deasupra, iar valorile de pe pozitiile de la $1$ la $C$ (din cadrul starii) se refera la linia curenta. Mentinand starea in acest fel, cand ajungem la elementul de pe linia $L$ si coloana $C$, vom calcula toate starile pentru care indicele este egal cu $C$. Pentru aceasta, vom parcurge toate starile $S'$ corespunzatoare coloanei anterioare ({$C-1$} sau $N$, daca $C$ este prima coloana) si vom genera toate starile $S$ cu indicele egal cu $C$, avand de ales dintre urmatoarele optiuni:

* incepe drum nou -> numarul de drumuri creste cu 1
* uneste nodul curent de nodul din stanga -> numarul de drumuri ramane constant

O parte din acesti pointeri pot fi calculati in momentul in care, in faza de constructie a arborelui de intervale 2D, se interclaseaza coordonatele $Y$ corespunzatoare fiului stanga si fiului dreapta. Cealalta parte a pointer-ilor se calculeaza realizand inca $2$ parcurgeri ale coordonatelor $Y$ sortate, una de la stanga la dreapta si alta de la dreapta la stanga (in conditiile in care am memorat pentru fiecare coordonata $Y$ de la care din cei doi fii provine).

Unul dintre concurenti a obtinut $100$ de puncte folosind o structura de date 2D numita 'kd-tree':http://en.wikipedia.org/wiki/Kd-tree, care poate oferi aceleasi operatii ca si un arbore de intervale 2D. Diferenta consta in cantitatea de memorie folosita ($O(N)$, in loc de $O(N*logN)$), dar si in complexitatea cautarii in interiorul unui dreptunghi ($O(sqrt(N))$, in loc de $O(log^2^N)$ sau $O(logN)$ cu optimizarea mentionata).

Unul dintre concurenti a obtinut $100$ de puncte folosind o structura de date 2D numita 'kd-tree':http://en.wikipedia.org/wiki/Kd-tree, care poate oferi aceleasi operatii ca si un arbore de intervale 2D. Diferenta consta in cantitatea de memorie folosita ({$O(N)$}, in loc de $O(N*logN)$), dar si in complexitatea cautarii in interiorul unui dreptunghi ({$O(sqrt(N))$}, in loc de $O(log^2^N)$ sau $O(logN)$ cu optimizarea mentionata).

h3. Link-uri utile

* 'Cautari Ortogonale / infoarena':downloads?cautari_ortogonale.doc , articol scris de Cosmin Negruseri
* 'Arbori de intervale / infoarena':downloads?arbori_de_intervale.zip , articol scris de d-na. prof. Dana Lica

* 'Cautari Ortogonale / infoarena':cautari-ortogonale , articol scris de Cosmin Negruseri
* 'Arbori de intervale / infoarena':arbori-de-intervale , articol scris de d-na. prof. Dana Lica

* 'Range Minimum Query and Lowest Common Ancestor / TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor , articol scris de catre Daniel Pasaila
* 'Orthogonal Range Queries / MIT':http://people.csail.mit.edu/indyk/6.838-old/handouts/lec5.pdf

* 'Game / Bursele Agora 2004':problema/game
* 'Pietre / infoarena':problema/pietre
* 'Otilia / .campion 2005':problema/otilia

* 'Playing with Matches / SGU':http://acm.sgu.ru/problem.php?contest=0&problem=153
* 'A Stone Game / TIMUS':http://acm.timus.ru/problem.aspx?space=1&num=1180
* 'The Game of Squares / TIMUS':http://acm.timus.ru/problem.aspx?space=1&num=1529