Solutia de complexitate $O(N^3^)$ este evidenta. Se calculeaza $HMIN[i, j]$, reprezentand inaltimea minima a unui arbore ce contine frunzele din intervalul $i, .., j$. $HMIN[i, i] = L{~i~}$, iar $HMIN[i, j] = 1 + min { max {HMIN[i,k], HMIN[k+1,j]} }$ (pentru $i < j$ si $i ≤ k < j$ ). Raspunsul il avem in $HMIN[1, N]$. In mod evident, pentru limitele date, algoritmul nu are nici o sansa sa se incadreze in limita de timp (sau de memorie).

Pentru rezolvarea acestei probleme vom folosi un algoritm greedy, avand complexitatea $O(N)$. Vom parcurge sirul frunzelor de la stanga la dreapta si vom mentine o stiva ce corespunde drumului cel mai din dreapta a arborelui de inaltime minima de pana atunci. Sa presupunem ca am calculat arborele de inaltime minima ce corespunde primelor $i$ frunze si acest arbore are pe drumul cel mai din dreapta niste noduri aflate la nivelele $0, 1, 2, .., K$ (deci $K+1$ noduri in total). Pentru fiecare nod de pe acest drum, cunoastem nivelul acestuia, precum si inaltimea subarborelui ce are radacina in nodul respectiv ({$H[i]$}). Vom avea $H[ 0 ] ≥ 1 + H[ 1 ] ≥ 2 + H[ 2 ] ≥ .. ≥ K + H[K]$. Cand introducem a $i+1$-a frunza, ea va fi ultimul nod de pe drumul cel mai din dreapta al arborelui. Pentru a o introduce pe acest drum, va trebui sa introducem un nod suplimentar deasupra unui nivel $x$, care sa aiba ca fiu dreapta frunza $i+1$ si ca fiu stanga subarborele ce corespundea nivelului $x$ dinainte (si care avea inaltimea {$H[x]$}) - vom numi aceasta operatie *split* deasupra nivelului $x$. In urma acestei operatii, inaltimea subarborelui de pe nivelul $x$ si de pe drumul cel mai din dreapta va deveni egala cu $Hnou[x]=1+max{L[i+1], H[x]}$. Vom dori sa aplicam operatia de split unui nivel cat mai de jos, dar care sa nu determine cresterea inaltimii arborelui nostru (daca se poate). Mai exact, vom incerca sa aplicam operatia split deasupra unui nivel $x$, pentru care are loc proprietatea $1+Hnou[x] ≤ H[x-1]$ (adica nu se mareste inaltimea subarborelui de pe nivelul {$x-1$}). In mod clar, daca un astfel de nivel $x ≥ 1$ nu exista, va trebui creata o radacina noua, iar inaltimea arborelui va creste (fiind egala cu {$1+max{H[ 0 ],L[i+1]}$}). Vom observa ca acest cel mai din dreapta drum al arborelui se comporta ca o stiva, deoarece, daca la un moment dat nu putem realiza operatia de split deasupra celui mai de jos nivel de pe drum, atunci va trebui neaparat sa o realizam mai sus si subarborele respectiv nu se va mai afla, dupa aceea, pe cel mai din dreapta drum al arborelui.

Pentru rezolvarea acestei probleme vom folosi un algoritm greedy, avand complexitatea $O(N)$. Vom parcurge sirul frunzelor de la stanga la dreapta si vom mentine o stiva ce corespunde drumului cel mai din dreapta a arborelui de inaltime minima de pana atunci. Sa presupunem ca am calculat arborele de inaltime minima ce corespunde primelor $i$ frunze si acest arbore are pe drumul cel mai din dreapta niste noduri aflate la nivelele $0, 1, 2, .., K$ (deci $K+1$ noduri in total). Pentru fiecare nod de pe acest drum, cunoastem nivelul acestuia, precum si inaltimea subarborelui ce are radacina in nodul respectiv ({$H[i]$}). Vom avea $H[0] ≥ 1 + H[1] ≥ 2 + H[2] ≥ .. ≥ K + H[K]$. Cand introducem a $i+1$-a frunza, ea va fi ultimul nod de pe drumul cel mai din dreapta al arborelui. Pentru a o introduce pe acest drum, va trebui sa introducem un nod suplimentar deasupra unui nivel $x$, care sa aiba ca fiu dreapta frunza $i+1$ si ca fiu stanga subarborele ce corespundea nivelului $x$ dinainte (si care avea inaltimea {$H[x]$}) - vom numi aceasta operatie *split* deasupra nivelului $x$. In urma acestei operatii, inaltimea subarborelui de pe nivelul $x$ si de pe drumul cel mai din dreapta va deveni egala cu $Hnou[x]=1+max{L[i+1], H[x]}$. Vom dori sa aplicam operatia de split unui nivel cat mai de jos, dar care sa nu determine cresterea inaltimii arborelui nostru (daca se poate). Mai exact, vom incerca sa aplicam operatia split deasupra unui nivel $x$, pentru care are loc proprietatea $1+Hnou[x] ≤ H[x-1]$ (adica nu se mareste inaltimea subarborelui de pe nivelul {$x-1$}). In mod clar, daca un astfel de nivel $x ≥ 1$ nu exista, va trebui creata o radacina noua, iar inaltimea arborelui va creste (fiind egala cu {$1+max{H[0],L[i+1]}$}). Vom observa ca acest cel mai din dreapta drum al arborelui se comporta ca o stiva, deoarece, daca la un moment dat nu putem realiza operatia de split deasupra celui mai de jos nivel de pe drum, atunci va trebui neaparat sa o realizam mai sus si subarborele respectiv nu se va mai afla, dupa aceea, pe cel mai din dreapta drum al arborelui.

Corectitudinea algoritmului prezentat poate fi demonstrata folosind urmatoarele elemente:
* Presupunem ca avem un arbore de inaltime minima pana la pasul $i$. Daca la pasul $i+1$ nu aplicam operatia split deasupra nivelului $0$, atunci inaltimea arborelui nu creste si cum inaltimea minima pentru $i+1$ frunze nu poate fi mai mica decat cea pentru $i$ frunze, raspunsul este corect.
* Daca pana la pasul $i$ avem un arbore de inaltime minima $HMIN[i]$ si la pasul $i+1$ ajungem sa aplicam operatia split deasupra radacinii, atunci avem $2$ cazuri:
** Daca $L[i+1] ≥ HMIN[i]$, atunci noua inaltime $HMIN[i+1]$ va fi $1+L[i+1]$ si este optima (deoarece inaltimea minima este mai mare sau egala cu {$1+max{L[orice frunza]}$})

** Daca $L[i+1]<HMIN[i]$, atunci avem ca $H[ 0 ]=1+H[ 1 ]=2+H[ 2 ]=...=K+H[K]$ (in caz contrar nu am ajunge sa aplicam operatia de split deasupra radacinii). Vom presupune prin absurd ca ar exista un alt arbore de inaltime minima pana la pasul $i$, care sa aiba un drum cel mai din dreapta diferit de cel la care am ajuns, care ar fi permis introducerea frunzei $i+1$ fara a creste inaltimea arborelui. Aceasta este etapa cea mai importanta a demonstratiei si, in urma analizei catorva cazuri, se va ajunge la o contradictie; contradictia va consta in faptul ca acest presupus arbore ar urma sa aiba o inaltime mai mica decat $HMIN[i]$, ceea ce este absurd.

** Daca $L[i+1]<HMIN[i]$, atunci avem ca $H[0]=1+H[1]=2+H[2]=...=K+H[K]$ (in caz contrar nu am ajunge sa aplicam operatia de split deasupra radacinii). Vom presupune prin absurd ca ar exista un alt arbore de inaltime minima pana la pasul $i$, care sa aiba un drum cel mai din dreapta diferit de cel la care am ajuns, care ar fi permis introducerea frunzei $i+1$ fara a creste inaltimea arborelui. Aceasta este etapa cea mai importanta a demonstratiei si, in urma analizei catorva cazuri, se va ajunge la o contradictie; contradictia va consta in faptul ca acest presupus arbore ar urma sa aiba o inaltime mai mica decat $HMIN[i]$, ceea ce este absurd.

Pentru o abordare matematica formala a problemei, care foloseste notiuni de calcul algebric pentru obtinerea unui algoritm liniar, puteti citi urmatorul 'articol':http://citeseer.ist.psu.edu/679514.html.
Pentru a obtine punctaj maxim, datorita limitei de timp nu foarte stricte, se putea implementa si un algoritm cu complexitatea $O(N*logN)$, folosind structuri de date precum 'arbori indexati binar':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees sau 'arbori de intervale':arbori-de-intervale ; de exemplu, o solutie asemanatoare constructiei unui arbore 'Huffman':http://en.wikipedia.org/wiki/Huffman_coding, bazata pe unirea repetata a cate doi subarbori alaturati pentru care maximul inaltimilor este minim.

h2. 'Multimi':problema/multimi
Se considera matricea $M$ cu $n$ linii si $m$ coloane, unde $M[i][j]=1$, daca $i$ este in $A{~j~}$ si $0$, altfel. Deoarece $A{~1~},...,A{~m~}$ separa multimea $[n]$, rezulta ca oricare $2$ linii ale matricei sunt diferite (daca liniile $k$ si $l$ ar fi egale, atunci $k$ si $l$ nu pot fi separate). De aici rezulta ca $n ≤ 2^m^$ (numarul de linii posibile, astfel incat oricare $2$ sa fie diferite). Asadar, $m ≥ log{~2~}n$. Vom arata ca $m=(log{~2~}n) + 1$. Presupunem prin absurd ca $m=log{~2~}n$. Din principiul lui Dirichlet se obtine cu usurinta faptul ca fie apare in matrice linia $00..0$ (contradictie cu conditia de acoperire), fie matricea contine 2 linii identice, ceea ce este absurd.

h2. Multimi

Pentru $m=(log{~2~}n)+1$ se poate da exemplul urmator: $A{~j~}$ este multimea numerelor mai mici sau egale cu $n$ care au $1$ pe bitul $(j-1)$ din reprezentarea lor binara pe $m$ biti (am numarat bitii de la stanga catre dreapta, incepand cu bitul {$0$})

h2. Nrbanda

h2. 'Nrbanda':problema/nrbanda
 
Se roteste intreg sirul la stanga, pana cand pe prima pozitie se afla numarul $1$. Apoi problema se rezolva incremental, pas cu pas. La pasul $i$ ({$2 ≤ i ≤ N$}), avem numerele de la $1$ la $i-1$ pe primele $i-1$ pozitii si vom dori sa aducem numarul $i$ pe pozitia $i$ (daca nu se afla deja acolo). Pentru aceasta, rotim sirul spre dreapta pana cand numarul $i$ ajunge pe ultima pozitie. Apoi separam sirul intre pozitiile $N-1$ si $N$ pana cand pe pozitiile $N-i+1, N-i+2, .., N-1$ se afla numerele $1, 2, .., i-1$ (la fiecare separare, numarul $i$ ramane pe ultima pozitie, iar numerele de pe pozitiile $1,..,N-1$ se rotesc spre stanga). Apoi se roteste intregul sir spre stanga, pana cand numerele $1, .., i$ ajung pe pozitiile $1, .., i$.
 
Probleme asemanatoare
 
* 'Order2 / Lista lui Francu':problema/order2
 
h2. '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").
 
h2. '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$.
 
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:
 
* $nrbiti = 3$
* $for i = N -> 1$
** daca num[i-1, nrbiti] >= M atunci$
*** $bitul i este 0$$
** altfel
*** bitul i este 1
*** M = M - num[i-1, nrbiti]
*** nrbiti = nrbiti - 1
 
h3. Probleme asemanatoare
 
* 'Stringsobits / USACO 1998':http://oldweb.uwp.edu/academic/mathematics/usaco/1998/Spring/prob.htm#p5
* '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'
* Parantezari / Baraj ONI 2000

h2. Tramvai
h2. Biti3

h2. Clear