Ktree, soluție

[•rgrig]

Am văzut că în firul „feedback” că articolul cu soluțiile oficiale va apărea tîrziu. Între timp putem să spunem noi cum am rezolvat diverse probleme aici pe forum.

La ktree problema cea mai mare pe care am avut-o e că luam „incorect” și nu știam de ce Noroc că cineva întrebase deja pe forum daca pentru graful 1->2->3 poți dinamita ambele muchii.

Pentru fiecare nod n am calculat costul minim necesar pentru a tăia exact m muchii și exact k noduri C[n][m][k]. O muchie e tăiată dacă e tăiată iar un nod e 'tăiat' dacă nu poți ajunge la el de la rădăcină (=nodul 1). Cu alte cuvinte k la mine e n-k în enunț. Ca să calculezi matricea C[n] presupui că ai calculate matricele C[nn] pentru toți copii nn ai lui n. Apoi folosești o altă matrice A[q][m][k] unde A[q] este soluția în cazul în care consideri numai primii q copii ai lui n.

Chestia asta a avut nevoie de o optimizare mică ca să intre în timp: C[n][m][k]=infinit pentru m>k (pentru că o muchie tăiată taie măcar un nod) așa că nu mai trebuie calculat.

[•Pepelea_Flaviu]

daca tot ai facut solutia de 100 .....o poti publica in articolul cu solutii. in felul acesta va fi publicat mai repede

[•andrei-alpha]

Da interesanta idee  Ai avut N^3 ...

[•wefgef]

De fapt este O(N^5) - O(N^3) stari * O(N^2) recurenta. Asta este si solutia oficiala

[•andrei.12]

Exista si o solutie O(N^4), care se foloseste de 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.

Cum parcurgerea Euler a unui arboare are 2 * N - 1 elemte complexitatea finala este O(N ^ 4).

[•wefgef]

  Sa postezi in articol solutia