514 Capitala

[•DITzoneC]

Aici puteţi discuta despre problema Capitala.

[•marin]

Problema asta cred ca este similara cu cezar(515 in arhiva, data la oji). Trimit aceeasi sursa cu dimensiunile modificate (cu k=0) si primesc Killed by signal 11(SIGSEGV). pe 9 teste iatr pe ultimul incorect. Ce gresesc ?

[•Florian]

Ai modificat fisierul de intrare/iesire?

[•marin]

am modificat.
Pe exemplu merge. Nu stiu de unde sa dea killed ...

[•Florian]

am modificat.
Pe exemplu merge. Nu stiu de unde sa dea killed ...

Mai uita-te odata la dimensiuni. Aproape sigur de la asta e. Si incorectul la fel. Mai arunca o privire pe sursa.

[•devilkind]

intradevar seamana cu problema cezar, la care din cate tin eu minte solutia e o(nlogn). Pentru problema asta in schimb exista o soluti cu complexitatea O(N+M).

[•marin]

Am mai incercat sa fac problema modificand solutia de la cezar. Am scris chiar si de la 0 codul. Obtin Killed by ...

devilkind : da-mi si mie o idee de o(n+m)

[•devilkind]

gandeste-te cum ca ai putea sa consideri ca arborele o anumita radacina (oricare) si cum ai putea sa calculezi ptr un nod suma pana la orasele din subarborele acestuia. Akuma ce iti mai trebuie e sa stii suma pana la nodurile care nu sunt in subarbore, valoare care o poti calcula "on the fly" daca te plimbi cum trebuie prin arbore.
(am incercat sa dau niste hinturi care sa nu dezvaluie chiar toata rezolvarea)

[•amadaeus]

La ce te referi cand spui ca poti calcula suma distantelor pana la nodurile care nu sunt in subarbore "on the fly"?
Eu am rezolvat problema cu doua parcurgeri DF, una ca sa determin suma distantelor pana la nodurile din subarbore, iar a doua pentru a determina (pe baza informatiilor de la primul DF) cealalta suma; problema e ca imi iese din timp pe un test.
Se poate face cu o singura parcurgere a arborelui? 

[•cotofana]

deci pana la urma cum se rezolva?
ideea mea de rezolvare i aceeasi ca si cea al lui amadeus
numa ca si io iau tot numai un tle 

[•Mishu91]

Eu am rezolvat TLE-ul ala parsand citirea

[•Bit_Master]

70 cu cstdio
100 cu streamuri

[•Andrei_Pavel]

Buna seara,
Ce e gresit daca gasesc elementul care se repeta cel mai repede in drumurile initiale si dupa aceea fac un DFS din el ?
Nu inseamna ca avem cel mai multe drumuri cu distanta de 1 ?
Multumesc anticipat!  

[•vendetta]

Nu e corect ce zici; e gresit pentru ca, pur si simplu e gresit...! Si la ce te ajuta ca stii ca ai cele mai multe drumuri cu distanta 1 ? Uite un exemplu pe care pica :

Cod:

.in : 
8
2 4 
2 5
2 1
1 3
3 6
6 7
7 8

.out : dat de tine nodul 2 cu ceva distanta
si corect nodul 1 si distanta 15

[•ctlin04]

Nu e chiar asa de simpla problema, este o problema de dinamica pe arbore bazata pe doua parcurgeri in adincime. Nu este corect a consideri nodul radacina cel care are cel mai multi vecini din simplu motiv ca pot exista mai multe astfel de noduri. Cel mai simplu si evident exemplu ar fi un lant de noduri de la 1 la 5, tu ai sa iai nodul 2 ca radacina si vei obtine suma distantelor 7, iar daca ei nodul 3, care la fel are doi vecini, obtii suma dist 6, deci mai mica.  
SPOR  

[•scipianus]

Nu e chiar asa de simpla problema, este o problema de dinamica pe arbore bazata pe doua parcurgeri in adincime.

Sa stii ca merge si solutia de la problema Cezar, care dupa parerea mea e mai usoara si intuitiva

[•Andrei_Pavel]

Mersi de sfaturi o sa o incerc pe aia mai intai

[•Andrei_Pavel]

ok..am citit solutia de la cezar si aia e greedy..as fi curios cum arata dinamica aici ? 

[•scipianus]

Si daca e greedy inseamna ca e ceva rau si josnic? Cam asa a sunat afirmatia ta,fara suparare

[•Andrei_Pavel]

a..nu ..doar ca sunt curios sa lucrez cat mai multe dinamici, doearece cum ai zis si tu greedy e mult mai intuitiv decat o dinamica

[•CosminRusu]

ok..am citit solutia de la cezar si aia e greedy..as fi curios cum arata dinamica aici ? 

Eu nu am rezolvat inca Cezar, nu stiu cum e acolo. Am facut insa o dinamica cam asa:
Pentru inceput pornesc un dfs din nodul 1 si calculez pentru fiecare nod suma distantelor de la nodul respectiv la toate nodurile din subarborele sau (fie acesta vectorul sum ). El se afla usor folosindu-te si de un vector nrNod[i ] = numarul de noduri din subarborele lui i.

Avand calculat acest vector, pornesti o alta parcurgere df ca sa adaugi pentru fiecare nod suma distantelor "in sus" . Incearca sa te gandesti care va fi urmatoarea formula, iar daca nu iti iese trimite-mi un PM si iti explic, nu vreau sa stric farmecul acestei probleme  .

[•AlexandruValeanu]

Am si eu o intrebare: am calculat cei doi vectori nr[ i ] = numarul de noduri din subarborele nodului i si sum[ i ] = distanta pana la toate nodurile din subarborele nodului i dar nu imi pot da seama cum pot afla suma distantelor de la un nod de la cele care nu sunt in subarborele sat. Imi poate explica cineva va rog frumos cum s-ar calcula ?

[•CosminRusu]

Sa zicem ca te aflii in nodul X, iar Y este un fiu al lui X.

Cand te muti din X in Y te apropii de nr[Y ] (+1 , in functie de cum iti este construit vectorul nr ) noduri (distantele pana la aceste noduri scad cu o unitate). Pe de alta parte te departezi de N- nr[Y ] ,  adica distantele pana in aceste noduri cresc cu o unitate. Stiind sum [x ] (fiindca pentru nodul 1 cunosti suma ceruta de problema ), ceea ce ramane de calculat e sum [y] pe baza a ceea ce ti-am zis mai sus.

Daca nu intelegi trimite-mi un PM si te ajut mai departe. Spor  !

[•ctlin04]

O sa incerc sa explic mai detaliat, ca sa fie pe inteles.
 Fie vectorii sum[ i ] -suma lungimilor drumurilor pentru nodurile din subarborele nodului i, nr[ i ]-numarul de noduri din subarborele nodului i si sus[ i ]-suma lungimilor drumurilor in sus, adica ceea ce ai intrebat tu.
 Fie nodul x si tatal lui y;
  sus[ x ]=sum[fratii lui x]+ 2*(nr[ y ]-nr[ x ] -1)+sus[ y ]+n-nr[ y ].
 Cum se explica formula?
  La fiecare drum care porneste de la un frate in jos trebuie sa adaugam 2 strazi ca sa-l unim cu nodul x, respectiv adunam suma distantelor in jos din fiecare frate+ 2*numarul de drumuri, adica numarul de frati si de noduri din subarbori lor. Acum au ramas drumurile in sus care pornesc din tata. Avem deja calculata sus[tata], adica suma distantelor in sus pentru tata, iar pentru a uni nodul x cu y trebuie sa mai adaugam o muchie la fiecare drum in sus ce porneste din tata, adica numarul de noduri care nu fac parte din subarborele lui y, acest numar este evident n-nr[ tata ].
 Sper ca am fost cit de cit explicit.  

[•CosminRusu]

Mi se pare destul de complicata formula ta.

Formula mea e aceasta si se bazeaza pe explicatia pe care am dat-o anterior. Si mi se pare mult mai simpla si intuitiva.

sum[nod] = sum[tata] + n - 2*(nodes[nod]+1);

Practic in primul dfs trebuia sa calculez doar nodes[i ] 1 <= i <= n si sum[1] ;
Iar in al doilea dfs ma foloseam de formula.