infoarena

Aici puteţi discuta despre problema Petrica (http://infoarena.ro/problema/petrica).

Problema cere: "Dandu-se un arbore cu N noduri, sa se elimine 3 muchii astfel incat diferenta dintre cea mai mare si cea mai mica suma a costurilor nodurilor din fiecare arbore ramas sa fie minima?" NU? Am testat o gramada... pur si simplu nu vrea sa ia mai mult de 10 pct.... #-o

Hm... daca rezolvarea ta implica la un moment dat sa faci niste diferente, te-ai uitat si tu sa nu scazi aceeasi porcarie de doua ori ?  :wink:

Da... Eu ciclam trei noduri i1, i2, i3, diferite intre ele si diferite de radacina si eliminam muchiile i1-parinte[i1], i2-parinte[i2], i3-parinte[i3]. Fiecare arbore care ramanea in padurea formata era considerat un nod comprimat si facem un nou arbore cu 4 noduri in care prelucram separat fiecare nod... obtineam O(N^3). sper sa imi dau seama ce e...

Pai in primul rand.. solutia ta nu cred ca este O(N^3) din moment ce tai 3 noduri si apoi prelucrezi padurea de arbori rezultata.

Hint: Taie doar doua noduri si incearca sa-l tai pe al treilea inteligent (ai sa iasa O(N^3))

Iesea O(N^3) pentru k eu retineam S = suma costurilor nodurilor din subarborele cu radacina in nodul i. Si nu aveam decat de prelucrat (scazut, adunat, etc. ) niste valori S[i1], S[i2], S[i3], S[radacina].
   Oricum, o sa ma gandesc si la chestia cu alegerea doar a doua noduri... (nu prea m-am gandit la asta). ms de sfat.

    O sa postez dupa 27... dak acum evaluatorul e oprit... :)

Hmm.. cred ca e buna si ideea ta. O fi de la implementare.

Si eu ma gandisem la aceeasi solutie. Am implementat-o acum si am luat 100 puncte. Probabil ai gresit undeva la implementare.

Sigur e de la implementare... O sa o rescriu de la inceput, alta varianta nu am...  :mrgreen:

La problema asta m-am prins partial ce avea (acum iau 40, nu 10.. se vede diferenta... :)) )... Era de la faptul ca unele muchii se puteau repeta... Eu citeam doar primele n-1 muchii (credeam ca nu se repeta...), si nu pana la sfarsitul fisierului.... Daca mai vad inca o greseala, iau 100 :)

Nu are cum sa fie de la asta , fiindca eu am luat 100 cu aceasta citire:

Eu cred ca am o singura problema la rezolvare. Din problema nu-mi dau exact seama cum sa determin radacina.

Are cineva vreo idee.

Agata pur si simplu arborele in nodul 1 ( considera radacina = 1 ) si porneste algoritmul tau ( nu conteaza ce radacina alegi, rezultatul e acelasi... ).

are ceva special testul 3? iau WA pe el
am obtinut un algoritm O(n^2*log(n)+n^3).. intai fac lca iar apoi iau 3 noduri si elimin muchiile [i-tata] si calculez cele 4 sume in functie de cazurile care apar

testul 10 e smecher?

l-am facut...intre timp

un O(n^3) intra in timp aici ? daca da problama e simpla nu ?

Da.. O(n^3) intra in timp...

Cat va da pe:


?  :-k multumesc anticipat

2

da....mersi....am luat 100 intre timp  :)

ce au in comun testele 2 4 5 7 8 de iau WA pe ele  :?, nu inteleg, pur si simplu citesc muchiile, imi creez vectoru de tati cu ajutoru unui DF, apoi parcurg toate nodurile de la 2 la n (agat arborele in nodul 1), si elemin muchia i - arb ( arb - vectoru de tati), si apoi calculez suma ptr fiecare subarbore creeat (cel cu radacina in 1, i,j,k respectiv), si vad diferenta dintre maxim si minim.

[Later edit] am incercat sa citesc si pana la eof dar tot aia

La problema asta sunteti siguri ca structura e un arbore?Eu as crede ca e un graf.

Din asta eu inteleg ca e graf neorientat, conex si fara cicluri => arbore.

Da ,ai dreptate,nu am fost atent la precizarea cum ca ar exista un drum unic intre 2 orase. :peacefingers:
[EDIT]:Am facut problema si nu am luat decat 10p.Vrand sa observ unde cade programul meu,am zis sa introduc testul lui Toma Radu,dar din cate observ ala nu ii un arbore,deoarece nodul 6 are doi tati.Gresesc eu cu ceva?

Da, gresesti undeva :) Testul respectiv e corect, si muchiile alea formeaza un arbore.
In fisierul de intrare poti sa gasesti muchia 1 - 2 sau 2 - 1 avand aceeasi semnificatie. Daca observi, sunt 4 muchii legate de nodul 6:(2,6) (4,6) (6,8) si (6,13), dar asta nu inseamna ca 6 are 2 tati si 2 fii ci doar faptul ca 6 e legat prin muchie de nodurile 2, 4, 8, 13.
Arbore = graf neorientat conex si aciclic. (Nu trebuie neaparat sa aiba o radacina si o ierarhie "X este tatal lui Y").

Da ,ai dreptate.Nu am mai lucrat de mult cu arbori si am cam uitat.Ms  :)

Am optimizat cat am putut,am folosit si 2 surse(una in care am memorat arborele cu liste de adiacenta,si alta in care am folosit o idee din articolul "Multe 'smenuri' de programare in C/C++"  :)),si tot nu trec de 50p.Ce as putea sa fac?Precizez ca dupa ce calculez vectorul tati, am 3 foruri imbricate, cu I:2->n-2, J:I+1->n-1,K:J+1->n
PS:I:2->n-2  inseamna I ia valori de la 2 la n-2.

[Editat de moderator] Nu mai posta de 2 ori consecutiv, exista butonul "Edit"...
EDIT:M-am tot gandit la ce as putea sa fac,dar nu mi-a venit nici o idee.La ce mi-ar ajuta LCA,sau cum as putea sa tai al treilea nod "inteligent" ?.As putea sa folosesc niste algoritmi pt determinarea unui arbore de cost minim(Kruskal sau Prim).Va rog ,daca se poate,dati niste indicii.

Cred ca trebuia districtul.  :)

Un algoritm randomizat poate lua 70-80 p daca il optimizati chiar si 90 la 100 nu am reusit sa ajung
Algoritmul randomizat alege 3 muchii si calculeaza diferentele (o solutie nu prea inteligenta dar care scoate niste pct pe testele care nu au solutie unica sau care au nr mic de noduri) (daca vreti sa va distrati recomand sa incercati)
Intrebarea era cum alegi aceea muchie dintre 2 noduri "inteligent" ?? ca sa ai N^3 ....

Eu fac un DF pentru Sum[ i ] = populatia subarborelui cu radacina in nodul i si apoi incerc toate variantele de taiere . Am 10 puncte cu wa pe restul si nu prea imi dau seama de ce. Practic am aceeasi problema cu Filip Buruiana ( pagina 1 )  . Ma poate ajuta cineva , va rog ? :D

nu cumva problema ar trebui sa contina si un test cu maximul valorilor, asta insemnand 200 orase;
graf complet de 197 de noduri + 3 noduri conectate cu cate o muchie la 3 noduri distincte din graful complet
asta inseamna 197*196/2+3 muchii adica 19309 muchii, adica 19311 randuri in fisierul de intrare.
oare a fost facut un program performant si pentru asta?

adica vrea sa spuna ca daca orasul 1 se conecteaza cu orasul 3 trecand prin orasul 2 asta inseamna ca nu poate exista un drum de la orasul 1 direct la orasul 3? asta inseamna ca tine strict de arbori. Multumesc

Da, orasele si drumurile dintre orase reprezinta un arbore.

 Nu am nicio idee pentru a rezolva aceasta problema.M-ati putea indruma la vreun tutorial pe topcoder sau asa ceva pentru problema asta...sau sa spuneti macar un pic din ideile voastre multumesc mult.Programarea aia dinamica nu stiu cum as putea sa o implementez. ](*,) ](*,) plz help.

Later edit : Sau daca e alta problema asemanatoare cu "Petrica"  Very Happy

Editat de moderator : Modifica'ti posturile anterioare, nu posta consecutiv pe aceeasi tema.

populatiile oraselor sunt date in ordine nu ?

Cum adica ? Daca te referi la faptul ca a i-a valoarea de pe linia a doua inseamna populatia orasului i, atunci da, ai dreptate ;).

Da , la asta ma refeream ... off :| speram sa fie de la asta . Iau wa pe 4 teste x( . Daca poate cineva sa-mi sugereze un test mai .. "special" as fi recunoscator ... Deci am tot incercat sa vad ce ar fi gresit in algoritmul meu si nu inteleg . Fac o parcurgere df si numerotez nodurile in ordinea in care au fost atinse in parcurgere . Sortez nodurile dupa aceasta valoare si elimin orikre pereche de 3 muchii de tip i - tata[ i ] , j-tata[j] , k-tata[k] astfel inkt dfn[ i ] < dfn[j] < dfn[k] . Am pus aceasta conditie pentru a calcula mai usor suma costurilor nodurilor din fiecare district , deoarece daca aveam 2 noduri pe acelasi lant si eliminam prima data nodul de pe un nivel mai jos atunci cand eliminam un nod de deasupra lui ar fi trebuit sa scad si valoarea nodului eliminat anterior . Oricum am facut calculul si metoda mea elimina oricare pereche de 3 muchii din arbore . Astept orice idee ...

Iau doar 10 puncte. Am facut asa : retin in S[nod] numarul de oameni din subarborele cu radacina in nod ; apoi iau fiecare triplet de forma(i,j,k) cu 1<i<n-1, i<j<n, k<j<=n. Mai am doi vectori in care am First[nod], Last[nod]; Prima aparite a nodului respectiv ultima din parcurgerea DFS; verific daca exista subarbori inclusi in alti subarbori din cele 4 valori(1, i, j, k); asta o fac astfel : subarborele i e inclus in subarborele j daca prima aparatie a lui j e mai mica ca a lui i si ultima a lui j e mai mare ca alui i
Si retin minimul(Max-Min) de la toate tripletele. Ma poate ajuta cineva?
L.E. : Am uitat sa folosesc tag-ul code si parantezele drepte le-a interpretat gresit.
L.E. : Mi-a iesit de 100. Am uitat sa tratez cazul cand am de ex. : tripletul(i,j,k) iar j si k sunt subarbori ai lui i iar j e subarbore a lui k sau k e subarbore a lui j; netratand acest caz scadeam o valoare de 2 ori.

Ideea e buna. Nu inteleg insa cum verifici daca un subarbore nu apartine altuia. Ai scris execrabil, nu se intelege mai nimic. Explica putin mai detaliat partea asta cu verificarea. Si vezi ca se scrie "iau", fara cratima.


LE : Imi pare rau. Nu pot sa te ajut pentru ca nu imi dau seama daca e bine cum faci tu. Dar pot sa iti spun cum am facut eu. Am facut o parcurgere bfs iar apoi mi-am calculat o matrice a[ i ][ j ] care imi spunea daca nodul j se afla in subarborele cu radacina i. Am calculat-o in O(n logn).

pf si eu fac la fel ca salajan razvan si primesc la fel WA si tle pe ultimele teste doar testul 1 il iau nustiu ce are miar putea da cineva un test mai solid dar care sal pot verifica
mersi

Vezi sa nu scazi aceasi chestie de doua ori sau ceva de genu si fa forurile alea asa

hmm am pus conditie sa fie i!=j&&j!=k si am mai pus conditia sa fie pe nivele crescatoare (asa reduc numarul de cazuri care le am cand fac diferentele )

Cei care au avut wa pe testul 3 si l-au trecut pina la urma, va rog un hint ca nu ma prind nicidecum ce caz poate sa fie asa special  ](*,)

Eu tin minte ca il picam deoarece cand scadeam din suma totala pe s[k] nu verificam daca nodul k se afla in subarborele lui j(adica deja il scazusem) sau ceva de genul. La o conditie din asta cred ca gresesti. Vezi sa nu scazi de doua ori aceasi chestie alt caz particular nu e.

De ce nu se mai pot trimite solutii?

S-a intamplat ceva cu arhiva de probleme. O sa se remedieze in curand.

Iau WA pe 7 teste imi poate da cineva un test mai special nu-mi dau seama ce gresesc

1)calculez un vector de tati si folosesc vector din stl pentru fii pe care ii retin ca o lista de adiacenta si mai am un vector in care retin pe pozitia i suma numarului locuitorilor din fiecare oras plecand din orasul i in fii pana ce ajung in toare frunzele
2)calculez o valoare mediana pentru un subarbore(suma tuturor nodurilor/4)
3)caut cea mai apropiata valoare de ceea ce caut eu(retin nodul care indeplineste acest lucru), dupa care golesc nodul respectiv si toti fii la care pot ajunge pornind din acesta si fac update pe tati pana ce ajung la nodul fara alt tata(repet acest lucru de 3 ori
4)la final caut valoare maxima ramasa in arbore
5)am 4 valori nr1,nr2,nr3,nr4 care reprezinta populatia totala a fiecarui subarbore
6)fac fiecare diferenta posibila cu modul si afisez maximul

Sau daca e gresita abordarea mea imi puteti spune unde gresesc?

Tot iau 60p cu 4 WA. Am facut cu LCA, in rest aceeasi idee ca cea a lui filipb. Aveti vreo sugestie?
LE:
Am luat 100p. Am pus unsigned int peste tot si a mers :shock:.

 :-' :-' :-' :-' :evil: :evil: :evil: :weightlift: :weightlift: :weightlift: =D&gt; =D&gt; 8) :peacefingers: :readthis: :rotfl: :rotfl: :winner1: :winner1: :winner2: :roll: #-o :harhar: :winner1: :aha: =D&gt; :?