Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Ktree, soluție  (Citit de 2738 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
rgrig
De-al casei
***

Karma: 46
Deconectat Deconectat

Mesaje: 144



Vezi Profilul WWW
« : 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 Smile 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ă Smile 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.
Memorat
Pepelea_Flaviu
Client obisnuit
**

Karma: 30
Deconectat Deconectat

Mesaje: 98



Vezi Profilul
« Răspunde #1 : 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
Memorat
andrei-alpha
Client obisnuit
**

Karma: 103
Deconectat Deconectat

Mesaje: 91



Vezi Profilul
« Răspunde #2 : Decembrie 01, 2008, 13:56:31 »

Da interesanta idee  Smile Ai avut N^3 ...
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #3 : 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 Very Happy
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
andrei.12
Echipa infoarena
Nu mai tace
*****

Karma: 107
Deconectat Deconectat

Mesaje: 381



Vezi Profilul
« Răspunde #4 : 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).
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #5 : Decembrie 01, 2008, 20:01:16 »

 Applause Sa postezi in articol solutia Smile
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines