|
•Cosmin
|
|
« Răspunde #1 : Octombrie 14, 2008, 07:17:22 » |
|
Cred ca poti sa gandesti invers problema. Ce nod il colorezi ultimul? Probabil o frunza. Care frunza? Daca ai de ales intre 2, minimizezi suma colorand-o pe cea de pondere mai mica ultima. Deci practic tai frunze din arbore si ai o coada de prioritati in care tii frunzele curente ordonate dupa ponderea lor.
|
|
|
Memorat
|
|
|
|
•domino
|
|
« Răspunde #2 : Octombrie 14, 2008, 16:04:29 » |
|
Solutia pe care am facut-o eu era ceva de genul asta: pentru fiecare subarbore tineam ordinea in care se coloreaza nodurile si faceam un DF. Cand eram intr-un nod apelam recursiv pentru fiecare subarbore si apoi interclasam listele ca sa obtin lista pentru nodul respectiv. Ca sa interclasez doua liste foloseam o dinamica simpla. Complexitate e cam mare, dar intra in timp.
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #3 : Octombrie 14, 2008, 19:52:49 » |
|
si nu merge mai simplu ce am zis eu? pare corect.
|
|
|
Memorat
|
|
|
|
•sima_cotizo
|
|
« Răspunde #4 : Octombrie 15, 2008, 08:56:31 » |
|
Si mie mi se pare corect, dar iau WA.
|
|
|
Memorat
|
|
|
|
•mariusdrg
Client obisnuit
Karma: 70
Deconectat
Mesaje: 59
|
|
« Răspunde #5 : Ianuarie 05, 2009, 19:00:23 » |
|
Pai nu prea e buna solutia lui cosmin, ca defapt solutia inverseaza problema... nu sti exact ce ti se deblocheaza cand elimini o frunza... ca sa exemplific consider urmatorul test: 4 1 (4 noduri si 1 este radacina) 10 2 5 4(valorile) 1 2 2 3 1 4 Algoritmul lui Cosmin va face urmatoarele: elimina nodul 4,elimina nodul 3, elimina nodul 2 , elimina radacina, astea in ordine invers cronologica, insumand 4 * 4 + 5 * 3 + 2 * 2 + 10 = 45.(Eu ma refer in ordine inversa fiindca asa merge si algoritmul, defapt logic se coloreaza radacina, dupa aia nodul 2 , dupa nodul 5 si dupa nodul 4.) solutia optima e sa se elimine nodul 3, elimina nodul 2, elimina nodul 4 si elimina radacina, insumand la 5 * 4 + 2 * 3 + 4 * 2 + 10 = 44.
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #6 : Ianuarie 05, 2009, 21:27:48 » |
|
marius, cred ca cosmin se referea la faptul ca la fiecare pas tai o frunza din arbore. E clar ca la pasul urmator ti se deblocheaza parintele lui. Singura problema care eu nu am inteles-o este cum alege la un pas frunza care o taie.
|
|
|
Memorat
|
|
|
|
•mariusdrg
Client obisnuit
Karma: 70
Deconectat
Mesaje: 59
|
|
« Răspunde #7 : Ianuarie 05, 2009, 21:46:32 » |
|
Pai nu e neaparat sa se deblocheze parintele ca un parinte poate avea mai multi fi si unul din fi poate sa fie chiar celalalta frunza, cum este cazul dat de mine... in acest caz nu se deblocheaza nimic cand elimini 4-le.
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #8 : Ianuarie 05, 2009, 21:51:14 » |
|
da corect, deblochezi un nod de abia dupa ce ai taiat toti fii lui.
|
|
|
Memorat
|
|
|
|
|