Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-11-19 12:27:10.
Revizia anterioară   Revizia următoare  

Solutii Happy Coding 2007 

Abc2

O prima abordare care ar parea sa aiba sanse de a obtine punctaj maxim este de a construi un trie al cuvintelor. Cu ajutorul acestui trie putem verifica in complexitate O(L) daca exista vreun cuvant care sa se termine la fiecare pozitie i din sir. Totusi, aceasta solutie are complexitate O(L*lungime text mare) si nu se incadreaza in timp.

Optimizarea consta in construirea automatului finit determinist asociat celor N cuvinte. Acest automat poate fi construit in complexitate O(N*L), conform algoritmului Aho-Corasick. Modul de constructie este asemanator calculului functiei prefix din algoritmul KMP. Construim trie-ul cuvintelor, apoi, pentru un nod X al trie-ului, determinam nodul din trie care corespunde celui mai lung sir de caractere care este sufix al sirului asociat nodului X. Putem calcula aceste valori pe nivele, intrucat un nod Y de tipul celui mentionat mai sus se va afla intotdeauna pe un nivel superior nodului X (dar nu neaparat pe calea de la radacina trie-ului pana la nodul X). Acest automat se poate folosi apoi in cadrul parcurgerii textului dat. Incepem din starea corespunzatoare sirului vid (radacina trie-ului). De fiecare data cand trecem la urmatorul caracter, incercam sa trecem in nodul din trie ce corespunde caracterului respectiv si este fiu al starii curente. Daca acest nod nu exista, la fel ca la KMP, trecem in starea corespunzatoare "prefixului-sufix" al starii curente si repetam acest lucru pana cand ajungem in radacina trie-ului sau intr-un nod care are un fiu ce corespunde caracterului urmator din sir. Daca ajungem intr-un nod ce corespunde unei stari finale, atunci am gasit o aparitie a unui cuvant.

Solutia oficiala foloseste un algoritm de constructie a unui automat finit determinist avand complexitate O(N*L2). Se va construi trie-ul cuvintelor, apoi, pe baza acestui trie, se va calcula un automat care are un numar de stari egal cu numarul de noduri ale trie-ului. Pentru fiecare stare X si fiecare caracter c, se va calcula functia nextState[X,c], reprezentand starea ce corespunde celui mai lung sir care este un subsir al sirului corespunzator starii X concatenat cu caracterul c. Pentru starile X ce au fiu in trie corespunzator unui caracter c, nextState[X,c] va fi egal cu acest fiu. Pentru celelalte caractere si o stare X, vom avea O(L) stari candidate. Mai exact, sa consideram ca TX este tatal nodului X in trie (presupunand ca X nu este radacina trie-ului) si ca avem starile Q0, Q1, .., QP stari ce corespund sufixelor de lungime 0, 1, .., P ale sirului corespunzator nodului TX (acest sir are P+1 caractere). Atunci multimea de stari R1, .., RP+1 avand aceeasi semnificatie pentru nodul X se calculeaza ca fiind R1=fiu[Q0,u], R2=fiu[Q1,u], .., RP+1=fiu[QP,u], unde X=fiu[TX,u], adica fiul nodului TX, ce corespunde caracterului u. La aceasta multime vom adauga pe R0=radacina trie-ului (ce corespunde sirului vid). nextState[X,c] va fi egal cu sirul de lungime maxima dintre sirurile corespunzatoare nodurilor fiu[Ri,c], cu 0 ≤ i ≤ P+1. Se observa usor ca pentru orice nod X pot exista cel mult O(L) stari candidate, deoarece sirul corespunzator unui nod X are O(L) caractere.

O solutie mai simpla si care ar obtine punctajul maxim consta in folosirea unor functii de hash, ca in algoritmului Rabin-Karp. Aceste functii trebuie sa fie calculabile usor (in O(1)) atunci cand avem valoarea hash-ului pentru un sir S si dorim sa calculam valoarea pentru sirul S' obtinut prin adaugarea unui caracter la dreapta lui S si inlaturarea unui caracter din stanga lui S. Cateva variante de functii de hash ar putea fi urmatoarele:

  • functii polinomiale, cu puteri de numere prime: (cN*PN + cN-1*PN-1 + c1*P + c0) mod Q (P si Q numere prime)
  • scrierea sirurilor ca numere in baza 3 (intrucat alfabetul consta doar din 3 litere) => este ideea de mai sus, dar cu P=3.

Probleme asemanatoare

Tritzi

Algoritm de complexitate O(N)

Vom calcula valorile T[i,j], reprezentand numarul de siruri de i tritzi, pentru care ultimul trit are valoarea j. T[1,j] = (1 mod P). Pentru i > 1, avem:

  • T[i, 0] = (T[i-1, 0] + T[i-1, 2]) mod P
  • T[i, 1] = (T[i-1, 1] + T[i-1, 2]) mod P
  • T[i, 2] = (T[i-1, 0] + T[i-1, 1] + T[i-1, 2]) mod P

Aplicarea directa a acestor relatii de recurenta conduce la un algoritm liniar, care, insa, nu se incadreaza in limita de timp.

Algoritm de complexitate O(log N) - varianta 1

Folosind relatiile de recurenta de mai sus, putem construi o matrice A de iteratie si vom privi T[i] ca pe un vector coloana. Avem relatia: T[i] = A * T[i-1]. T[N] = AN-1 * T[ 1 ]. T[ 1 ] este cunoscut direct, iar AN-1 se poate calcula in complexitate O(log N), folosind exponentiere logaritmica.

Algoritm de complexitate O(log N) - varianta 2

Vom calcula o matrice T[x][i][y] = numarul de siruri de tritzi (mod P), de lungime 2i si pentru care primul trit are valoarea x, iar ultimul trit are valoarea y. T[x][ 0 ][y] se determina direct, iar pentru i > 0, T[x][i][y] va fi egal cu o suma din T[x][i-1][a] * T[b][i-1][y], unde a si b sunt doua valori (0, 1 sau 2) care pot fi plasate una dupa alta.

Apoi vom scrie numarul N ca o suma de puteri ale lui 2: N = 2p1 + 2p2 + .. 2pK. Vom calcula o matrice U[x][i][y] = numarul de siruri de tritzi (mod P) de lungime 2p1 + 2p2 + .. + 2pi, pentru care primul trit are valoarea x si ultimul trit are valoarea y. Avem U[x][ 0 ][y] = T[x][p0][y]. Pentru i > 0, U[x][i][y] este egal cu o suma din U[x][i-1][a] * T[b][pi][y], unde a si b sunt doua valori de tritzi care pot fi plasate una dupa alta. Rezultatul final il vom obtine adunand toate valorile U[x][K][y], unde K este numarul de biti de 1 din reprezentarea binara a lui N.

h3.Probleme asemanatoare

Regine2

Problema se rezolva prin backtracking. Pentru fiecare pozitie (in ordinea liniilor si, pentru fiecare linie, in ordinea coloanelor), se incearca amplasarea sau neamplasarea unei regine in pozitia respectiva, iar apoi se marcheaza toate pozitiile atacate de regina respectiva, pentru a nu se mai incerca amplasarea unei regine viitoare pe o pozitie deja atacata. La intoarcerea din backtracking, pozitiile marcate se demarcheaza (vom folosi, de fapt, un contor pentru fiecare pozitie, in care vom retine de cate regine deja amplasate este atacata pozitia respectiva). Singura optimizare necesara este ca, atunci cand marcam pozitiile atacate de o regina nou-amplasata, vom marca doar pozitiile pe care vom incerca sa amplasam o regina in viitor (adica doar inspre directiile: est, sud-est, sud, sud-vest, si nu in toate cele 8 directii).

Probleme asemanatoare

Rfinv

Solutie de complexitate O(N4)

Vom sorta toate cele O(N2) distante din matrice in ordine crescatoare si vom initializa o matrice D[i][j]=infinit, pentru i <> j, respectiv 0, pentru i=j. Pe masura ce parcurgem sirul sortat al distantelor, vom actualiza valorile din matricea D. Sa presupunem ca am ajuns la o distanta avand valoarea x, ce reprezinta distanta minima dintre 2 noduri i si j. Daca D[i][j] < x sau D[i][j] > x si nu exista muchie in graf intre i si j, atunci nu avem solutie si ne oprim. Daca D[i][j] > x si exista muchie intre i si j, atunci vom pune pe aceasta muchie costul x. In continuare, va trebui sa actualizam valorile D[a][b] afectate de setarea valorii x pe muchia (i,j). Mai exact, pentru fiecare pereche de noduri (a,b), D[a][b] va fi egal cu minimul dintre valoarea actuala D[a][b] si min { D[a][i] + x + D[j][b], D[a][j] + x + D[i][b] }.

Daca nu am intalnit nici o contradictie pe masura ce am parcurs muchiile, atunci raspunsul este "DA" ; in caz contrar, raspunsul este "NU".

Solutie de complexitate O(N3)

Pe fiecare muchie a grafului (i,j) se pune o distanta egala cu valoarea A[i][j] ($A$ fiind matricea data). Se aplica apoi algoritmul Roy-Floyd pe acest graf, iar matricea distantelor obtinuta trebuie sa fie identica cu matricea distantelor data (in caz contrar neexistand solutie).

Probleme asemanatoare

Pali

Se va calcula pmin[i] = numarul minim de palindroame in care poate fi impartit sirul format din primele i caractere ale sirului dat.

Solutia 1

Vom avea pmin[ 0 ] = 0 si pmin[i] = 1 + min { pmin[j] | subsirul j+1,..,i este un palindrom }, cu 0 ≤ j ≤ i-1. Pentru a determina rapid daca subsirul dintre 2 pozitii k si l este un palindrom, vom calcula o matrice Pali[k][l], avand valorile 1 si 0, daca subsirul dintre pozitiile k si l este palindrom sau nu. Vom avea Pali[k][l] = 1, daca sir[k] = sir[l] si Pali[k+1][l-1]=1 (pentru cazul in care l-k ≥ 2). Pentru ca aceasta solutie sa se incadreze in timp, va trebui ca matricea sa o calculam coloana cu coloana, pe masura ce avem nevoie de valorile din ea.

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).

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

Furnica

  • daca pozitia de start este 'C', atunci raspunsul este (t+1)2
  • daca pozitia de start este 'S', atunci:
    • daca t este par, atunci raspunsul este ((t/2)+1)2
    • daca t este impar, atunci raspunsul este ((t+1)*(t+2)/2)-((t+1)/2)2

Aceste formule (sau altele echivalente) pot fi obtinute folosind urmatorul rationament: furnica se poate afla in orice pozitie aflata la o distanta care are aceeasi paritate ca si t, fata de pozitia initiala. Pentru pozitia de start 'C', aceste pozitii formeaza niste "romburi", iar pentru pozitia de start 'S', aceste pozitii formeaza niste diagonale "secundare".

Flori2

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 MAXi. Raspunsul cautat este maxim{MAXi + 1} si se obtine in complexitate O(N2*logN).

Solutia de complexitate O(N3), 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.

Probleme asemanatoare

Bitmap

O prima solutie ar consta in a incerca toate cele 4 posibilitati de a codifica un bitmap care nu are toate celulele de aceeasi culoare. Aceasta abordare de tip backtracking nu s-ar incadra in timp. Optimizarea necesara consta in memoizarea starilor prin care trecem in cadrul backtracking-ului (algoritmul nu se mai numeste backtracking acum, ci devine un fel de programare dinamica). O stare este data de 2 numere pe cel mult 11 biti, S1 si S2. Bitii de 1 din S1 definesc liniile selectate din cadrul bitmap-ului initial, iar bitii de 1 din S2 definesc coloanele selectate din cadrul bitmap-ului initial. Bitmap-ul definit de starea (S1,S2) este reprezentat de celulele aflate la intersectia dintre liniile selectate de S1 si coloanele selectate de S2. Prin urmare, vom calcula lmin[S1,S2] = lungimea minima a bitmap-ului ce corespunde starilor S1 si S2. lmin[2M 1,2N-1] va contine rezultatul cautat. Pentru ca solutia sa se incadreze in timp, matricea cu valorile asociate fiecarei stari nu trebuie reinitializata la fiecare test. Se va folosi o matrice suplimentara last_test, in care vom memora numarul ultimului test in care am ajuns sa calculam valoarea pentru starea (S1,S2). Daca ajungem la starea (S1,S2) in testul curent, vom verifica valoarea lui last_test[S1,S2]. Daca aceasta este egala cu numarul testului curent, inseamna ca am calculat deja valoarea respectiva; in caz contrar, o vom calcula acum si vom seta last_test[S1,S2] la numarul testului curent.

Cascaval

Cercuri3

O metoda simpla este sa translatam primul cerc in originea sistemului de axe de coordonate si sa il rotim pe cel de-al doilea pana cand centrul acestuia se afla pe axa OX (la coordonata X egala cu distanta dintre cele 2 centre). Trebuie analizate cateva cazuri, pe baza valorilor razelor celor 2 cercuri si a distantei dintre centrele lor (cazurile simple sunt cand unul din cercuri se afla complet in interiorul, respectiv complet in exteriorul celuilalt cerc). In cazul in care se decide ca cele 2 cercuri se intersecteaza in 2 puncte, vom observa ca, in urma translatiei si rotatiei efectuate, cele 2 puncte de intersectie se vor afla la aceeasi coordonata x, dar la coordonate y opuse (egale in modul, dar opuse ca semn). Vom determina cele 2 coordonate folosind Teorema lui Pitagora generalizata in triunghiul format din centrele celor 2 cercuri si fiecare din cele 2 puncte de intersectie (deoarece cunoastem lungimile tuturor laturilor). Aria comuna a celor 2 cercuri este acum formata din 2 bucati de cerc, de o parte si de alta a segmentului ce uneste cele 2 puncte de intersectie. Aria fiecareia din cele 2 bucati de cerc se poate scrie ca diferenta dintre aria unui sector de cerc (corespunzator segmentului ce uneste punctele de intersectie) si aria unui triunghi (format din centrul unui cerc si cele 2 puncte de intersectie). O formulare suficient de generala a expresiilor ce calculeaza aria comuna permite tratarea unitara a cazurilor in care cel de-al doilea cerc are centrul in exteriorul, respectiv in interiorul primului cerc.

Link-uri utile

Probleme asemanatoare

Antitero

  • cat timp (exista un soldat care se poate deplasa in siguranta intr-o pozitie de unde poate omori un terorist)
    • deplaseaza soldatul in pozitia respectiva si elimina teroristul
  • daca toti soldatii pot ajunge in siguranta la destinatie, atunci deplaseaza-i acolo si incheie misiunea cu succes
  • altfel: "Mission aborted!"

Aceasta este schita unui algoritm usor de implementat care rezolva problema. Practic, se incearca eliminarea repetata a cat mai multor teroristi, dupa care se incearca deplasarea la destinatie. Rezolvarea problemei implica, asadar, doar parcurgeri repetate ale grafului (de exemplu, DF sau BF), in care unele noduri sunt "blocate" (cele in care se afla teroristi in viata si cele amenintate de teroristi in viata).

Sistem2

Problema se rezolva generand permutari ale celor N variabile si verificand daca ele verifica constrangerile. Ideea importanta este ca verificarea satisfacerii constrangerilor sa nu se realizeze abia dupa ce s-a generat cate o permutarea intreaga, deoarece o astfel de abordare nu s-ar incadra in limita de timp. Pe masura ce selectam o valoare pentru un element i al permutarii, vom verifica toate constrangerile care contin acel element si elemente dinaintea lui i (ale caror valori au fost, de asemenea, deja selectate). Daca cel putin o constrangere nu este satisfacuta, nu vom mai continua generarea permutarii in continuare, ci vom trece la valoarea urmatoare a elementului i (scapand, astfel, de un numar posibil foarte mare de permutari pe care le-am fi generat degeaba). Aceasta optimizarea nu ne-ar fi prea folositoare daca, de exemplu, toate constrangerile contin ultimul element (si verificarea lor se poate face abia la sfarsit), insa, putem schimba ordinea in care selectam valorile elementelor. De exemplu, daca luam elementele in ordinea in care apar acestea in constrangeri (intai cele din prima constrangere, apoi cele din a doua care nu apar si in prima, apoi cele din a treia care nu apar in primele doua s.a.m.d.), putem garanta ca dupa selectarea valorilor a cel mult 4 elemente vom putea verifica prima constrangere si ca dupa cel mult 8 elemente putem verifica a doua constrangere. Daca schimbam si ordinea constrangerilor, in asa fel incat constrangerile cu numar mai mic de variabile sa fie primele, obtinem niste optimizari si mai bune. Alta optimizare utila ar fi aceea ca, daca o constrangere contine P variabile, dupa setarea valorilor a P-1 dintre ele se poate calcula valoarea celeialalte variabile. De asemenea, pentru fiecare element a carui valoare nu a fost setata inca s-ar putea memora multimea valorilor posibile pe care le mai poate lua in continuare (pe baza variabilelor avand valori setate si a multimilor de valori posibile ale variabilelor cu valori nesetate inca, dar impreuna cu care se afla in cel putin o constrangere),

In concluzie, problema nu se rezolva in timp polinomial (lucru care se putea ghici dupa numarul mic de variabile), fiind necesare unele optimizari. Ea poate fi privita ca un caz particular al problemei satisfacerii constrangerilor, care este o problema generala, pentru care au fost studiati multi algoritmi si au fost gasite multe optimizari.

Optic

Zvon

Solutia "oficiala" are complexitatea O(N*logN) si presupune calculul urmatoarelor valori:

  • TMIN[i] = timpul minim necesar pentru a propaga zvonul in subarborele lui i, din momentul in care i afla zvonul. In mod clar, TMIN1 reprezinta rezultatul cautat.

Pentru a calcula TMIN[i], vom calcula intai valorile TMIN ale fiiilor lui i, pe care le vom sorta apoi descrescator: TMIN[f1] ≥ TMIN[f2] ≥ .. ≥ TMIN[fK]. Ordinea in care i va transmite zvonul fiilor sai este chiar ordinea descrescatoare a valorilor TMIN a acestora. In aceste conditii, TMIN[i] = maxim { 1 + TMIN[f1], 2 + TMIN[f2], .., K + TMIN[fK] }.

Probleme asemanatoare

Cerc2

Observam ca distanta dintre oricare 2 puncte in care fotonul atinge cercul este aceeasi ca cea dintre punctul initial si punctul (R*cos(alfa), R*sin(alfa)). Fie aceasta distanta D. Dupa S secunde, fotonul se afla la o distanta S mod D de ultimul punct in care a atins cercul. Operatia modulo se poate defini si pentru numere reale, scriind S ca fiind k*D + r, unde k este un numar intreg (si r este restul impartirii). Putem folosi acum Teorema lui Pitagora generalizata, pentru a determina distanta de la foton la centrul cercului, in triunghiul format din punctul curent, ultimul punct de atingere a cercului si centrul cercului. O metoda mai simpla de a calcula aceasta distanta este de a calcula distanta de la centrul cercului la segmentul dintre 2 puncte consecutive in care fotonul atinge cercul (aceasta distanta este R*sin(beta)). Cum perpendiculara din centrul cercului pe acest segment il intersecteaza exact in mijloc, putem folosi distanta fotonului fata de mijlocul segmentului si apoi Teorema lui Pitagora intr-un triunghi dreptunghic, pentru a calcula distanta de la foton la centrul cercului (in triunghiul format de centrul cercului, mijlocul segmentului si pozitia fotonului, distanta respectiva este lungimea ipotenuzei).

Probleme asemanatoare

Puteri2

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 10x si 10x+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 {104}), 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)

Aimin

Solutia de complexitate O(N3) este evidenta. Se calculeaza HMIN[i, j], reprezentand inaltimea minima a unui arbore ce contine frunzele din intervalul i, .., j. HMIN[i, i] = Li, 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 H0 ≥ 1 + H1 ≥ 2 + H2 ≥ .. ≥ 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{H0,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 H0=1+H1=2+H2=...=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.

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 sau arbori de intervale ; de exemplu, o solutie asemanatoare constructiei unui arbore Huffman, bazata pe unirea repetata a cate doi subarbori alaturati pentru care maximul inaltimilor este minim.

Multimi

Nrbanda

Tramvai

Biti3

Clear

H

Permavg

Kboard