Solutii All you can code 2008

... Rezumat concurs ...

Secventa 6

Problema cere determinarea numarului perechilor de indici i, j (i < j) pentru care a_k < a_i si a_k < a_j, unde i < k < j. Sa consideram multimea T a indicilor care verifica relatia de mai sus pentru pozitia p a sirului dat. Daca avem t₁ si t₂ apartinand lui T, t₁ < t₂, cum a_t1 < a_k cu t₁ < k < p, rezulta ca a_t2 < a_t1; asadar multimii ordonate (crescator) T ii corespune o multime ordonate (descrescator) A'. Multimea A' poate fi construita cu ajutorul unei stive sortate, la pasul p sunt scoase din stiva elemente mai mici sau egale decat a_p si este introdus elemntul a_p. Stiva construita astfel contine elementele corespunzatoare indicilor multimii T prezentate mai sus, dar contine si elemente in plus (este respectata numai una din conditiile problemei). Observam ca ultimul element care respecta si a doua conditie este, in ordinea stivei sortate, primul element mai mare sau egal decat a_p. In concluzie numarul de indici care respecta conditia pentru pozitia p este egala cu numarul de elemente scoase din stiva sortata la introducerea elementului a_p +1 daca ultimul element scos din stiva este diferit de a_p.

Control

...

Grau

...

Take 5

...

Drept

...

Ktree

Prima solutie - Complexitate O(N⁵)

Se calculeaza o dinamica D[ i ][ j ][ k ] = costul minim daca in subarborele i tai k muchii si ai j noduri inaccesibile din nodul 1.

Pentru a calcula matricea D pentru un nod T, presupui ca ai calculate valorile lui D pentru toti fii lui T.
Apoi se mai construieste o dinamica A[ i ][ j ][ k ] = solutia daca consideri numai primii i fii ai lui T.

Solutia finala se afla in D[ 1 ][ N-K ][ M ].

A doua solutie - Complexitate O(N⁴)

Aceasta solutie se bazeaza pe parcurgerea Euler a arborelui dat.

La inceput se calculeaza o dinamica A[ i ][ j ] = costul minim pentru ca in subarborele i sa se taie j muchii.

Apoi se mai calculeaza o dinamica D[ i ][ j ][ k ] = costul minim pentru a ajunge in pozitia i a parcurgerii Euler a arborelui, cu j noduri inaccesibile din nodul 1 si k muchii taiate.
Daca suntem pe pozitia i in parcurgere(fie T nodul de pe acea pozitie), avem 2 optiuni: nu taiem nodul: din D[ i ][ j ][ k ] -> D[ i+1 ][ j ][ k ], sau daca nodul T apare pentru prima data in parcurgere putem sa il taiem: D[ i ][ j ][ k ] -> D[pozitia finala a lui T in parcurgere + 1][j + nr de noduri din subarborele T][k + nrs], unde nrs ia valori de la 1 la M.

Solutia finala se afla D[ 2 * N ][ N-K ][ M ], deoarece parcurgere Euler a arborelui are 2 * N - 1 elemente.

Seg

...

Transport rutier

...

Tree Search

Problema se rezolva prin programare dinamica. Presupunem ca agatam arborele intr-un nod oarecare. Folosind DFS, calculam P[ i ] = costul maxim al unui drum care contine drept capat nodul i, si contine doar noduri din subarborele lui i. Relatia de recurenta se determina relativ simplu: P[ i ] = C[ i ], daca i este nod terminal, iar P[ i ] = max ( C[ i ], C[ i ] + P[ k ] ), pentru k - adiacent a lui i ( diferit de tatal lui i ). De asemenea, mai trebuie calculat si un vector de tati: tata[ x ] = tatal nodului x. Avand acesti vectori calculati, mai trebuie sa determinam drumul de cost maxim care are drept extremitate nodul i, si pleaca "in sus". Astfel, notam cu T[ i ] - costul maxim al unui drum care pleaca din i, "in sus". Pentru a calcula acest vector, ne trebuie cate o parcurgere DF pt fiecare fiu al radacinii. Presupunem ca dorim sa calculam T[] pentru subarborele k al radacinii (asadar, k este fiu al radacinii). Trebuie sa procedam astfel:

T[ radacina ] se initializeaza cu max ( C[ radacina ], P[ j ] ), unde j este un fiu al radacinii, diferit de k.
Aplicam un algoritm de tip DF, avand ca punct de plecare k. Pentru fiecare nod x pe care il parcurgem (avand tatal t) calculam T[ x ] = max ( C[ x ], C[ x ] + T[ t ], C[ x ] + C[ t ] + P[ j ]), unde j este un fiu al lui t, diferit de i si diferit de tata[t]. Continuam parcurgerea cu fiecare subarbore a lui x (considerand radacina tot nodul radacina)

Asadar, putem acum calcula bst[ x ] = costul maxim al unui drum care contine nodul x, pe baza lui P si a lui T. Relatia de recurenta se determina usor. Avand acest vector calculat, putem raspunde in O(1) pe query. Asadar complexitatea programului va fi O( N + M ).

Observatie: Pentru a calcula cel mai mare fiu al radacinii, diferit de fiul k, se va folosi un deque, altfel algoritmul putand deveni O( N ^ 2).