h2. 'Puteri2':problema/puteri2

h2. Aimin

Problema cere determinarea radicalului de ordin $P$ dintr-un numar mare. Exista mai multe metode de realiza acest lucru, dintre care voi mentiona doua:
 
* Determinarea radicalului de ordin $P$ cifra cu cifra: Se determina intai numarul de cifre ale numarului (se incadreaza radicalul intre un $10^x^$ si $10^x+1^), apoi se determina, pe rand, fiecare cifra a rezultatului; pentru fiecare pozitie, se incearca, pe rand, toate cifrele de la $0$ la $9$ si ne oprim la ultima cifra pentru care numarul ridicat la puterea $P$ (considerand ca cifrele de dupa cifra curenta sunt egale cu {$0$}), nu depaseste $N$-ul dat. Eventual, cifra curenta se poate cauta binar (poate fi util daca rezultatul este tinut intr-o baza mai mare decat {$10$}).
* Cautarea binara a rezultatului, intre o limita inferioara si o limita superioara. Numarul fixat in cadrul cautarii binare se ridica la puterea $P$ si daca depaseste $N$-ul dat, se pastreaza jumatatea inferioara a intervalului de cautare; in caz contrar, se pastreaza jumatatea superioara a intervalului.
 
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.
* 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. 'Aimin':problema/aimin
 
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.
 
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.
 
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