|
Titlul: Ktree, soluție Scris de: Radu Grigore din Decembrie 01, 2008, 13:15:36 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. Titlul: Răspuns: Ktree, soluție Scris de: Flaviu Pepelea din Decembrie 01, 2008, 13:52:48 daca tot ai facut solutia de 100 .....o poti publica in articolul cu solutii. in felul acesta va fi publicat mai repede
Titlul: Răspuns: Ktree, soluție Scris de: Andrei-Bogdan Antonescu din Decembrie 01, 2008, 13:56:31 Da interesanta idee :) Ai avut N^3 ...
Titlul: Răspuns: Ktree, soluție Scris de: Andrei Grigorean din Decembrie 01, 2008, 14:12:12 De fapt este O(N^5) - O(N^3) stari * O(N^2) recurenta. Asta este si solutia oficiala :D
Titlul: Răspuns: Ktree, soluție Scris de: Andrei Parvu din Decembrie 01, 2008, 17:21:17 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). Titlul: Răspuns: Ktree, soluție Scris de: Andrei Grigorean din Decembrie 01, 2008, 20:01:16 =D> Sa postezi in articol solutia :)
|