013 Petrica

[•k_ounu_eddy]

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.

[•c_e_manu]

numarul de locuitori din distructul cu cea mai mare populatie

Cred ca trebuia districtul. 

[•Sorin_Ionut]

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 ....

[•klamathix]

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 ?

[•adysnook]

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?

[•devilkind]

Petrica este presedintele unei tari cu N orase conectate prin strazi bidirectionale astfel incat exista un drum unic intre oricare doua dintre ele

[•adysnook]

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

[•pauldb]

Da, orasele si drumurile dintre orase reprezinta un arbore.

[•alexa_myparadise]

 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.

[•darkseeker]

populatiile oraselor sunt date in ordine nu ?

[•SpiderMan]

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 .

[•darkseeker]

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 ...

[•vendetta]

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

Cod:

(First[j] < First[i] && Last[j] > Last[i]) atunci scad din S[j] S[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.

[•stardust]

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).

[•dutzul]

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

[•stardust]

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

Cod:

for(int i=1;i<=n-2;i++)
   for(int j=i+1;j<=n-1;j++)
     for(int k=j+1;k<=n;k++)

[•dutzul]

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 )

[•ctlin04]

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 

[•stardust]

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.

[•Patrik]

De ce nu se mai pot trimite solutii?

[•SebiSebi]

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

[•ionut98]

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?

[•mihai.alpha]

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 .

[•AlexTudor]