123 Razboiul lumilor

[ditzone]

Aici puteţi discuta despre problema Razboiul lumilor.

[•junior]

Complexitatea e O(n*t), nu? Poate sa-mi dea cineva vreun hint? Eu nu am reusit decat ceva de genul O(n*n*t) care, evident, nu intra in timp.

[•calinux]

Eu am facut un algoritm O(N*T). Dar nu sunt sigur de corectitudine... Si dat fiind ca nu iau 100... presupun ca nu e corect... or uit ceva. Iata ce fac eu:

1. Leg de frunze un nod virtual care are distanta catre acele noduri 0
2. Pornesc un bfs din acel nod astfel incat sa generez intr-un vector distantele minime din orice nod catre cea mai apropiata frunza.
3. Selectez maximul dintre aceste valori.
4. Afisez toate nodurile care au distanta maxima.

Pe testul dat in exemplu merge. Logic cred ca ar trebui sa fie ok. Daca poate cineva sa-mi zica daca ii se pare incorect. Mersi mult.

[•greco]

Cred ca aceasta modalitate de a aborda o problema nu este foarte productiva. Ar fi mai bine sa pui mana pe foaie, sa vezi exact cum sta treaba, si sa te apuci de implementat numai in momentul in care esti sigur ca algoritmul tau e corect. Daca implementezi ideile care iti vin si lasi evaluatorul infoarena sa-ti spuna daca erau bune sau nu, o sa ai surprize pe la concursuri...

[•junior]

Eu am facut un algoritm O(N*T). Dar nu sunt sigur de corectitudine... Si dat fiind ca nu iau 100... presupun ca nu e corect... or uit ceva. Iata ce fac eu:

1. Leg de frunze un nod virtual care are distanta catre acele noduri 0
2. Pornesc un bfs din acel nod astfel incat sa generez intr-un vector distantele minime din orice nod catre cea mai apropiata frunza.
3. Selectez maximul dintre aceste valori.
4. Afisez toate nodurile care au distanta maxima.

Pe testul dat in exemplu merge. Logic cred ca ar trebui sa fie ok. Daca poate cineva sa-mi zica daca ii se pare incorect. Mersi mult.

Pai din ce inteleg eu tu calculezi distantele minime de la orice nod catre frunze. In enunt se cam cere altceva... (scuze daca am zis vreo prostie, sau am inteles prost explicatia ta)

Totusi, se indura cineva sa-mi dea un hint?

[•filipb]

Pornesti un DFS din nodul 1 si pt fiecare nod calculezi in timpul DFSului distanta maxima a nodului respectiv la fiii sai. Apoi pt. fiecare nod calculezi si distanta maxima "in sus" din arborele DFS... ( nu mai zic cum ). Totul e in O(N) pe test.

[u-92]

nu.. eu tot nu ma prind   adica nu imi dau seama cum sa determin distanta "in sus" in o(n)

[VladS]

Incearca sa rezolvi Color2 ca e cam aceasi idee si ai solutie oficiala din care te poti inspira.

[u-92]

mersi, m-am prins acum rezolvasem si eu color2, dar acolo era oarecum mai simplu..

[•anouk]

sunt destul de nedumerita, am calculat pt fiecare nod subarborele cu radacina in nodul respectiv si suma distantelor maxima, si apoi am ales nodurile cu sume minime... in timp intra, exemplul de pe site merge, merg si cateva cazuri facute de mine, chiar nu reusesc sa-mi dau seama ce am gresit... oare nu e buna ideea de rezolvare?

[•pauldb]

Cod:

2
12
11 10 2
10 3 2
3 4 10
2 9 3
9 3 8
9 12 9
1 12 7
12 6 13
8 7 1
7 12 15
1 5 11
16
1 5 6
1 2 3
1 3 1
1 4 4
5 6 4
5 7 2
7 12 2
7 13 3
2 8 1
4 9 2
9 14 1
4 10 3
10 15 6
4 11 1
11 16 3

Cod:

Testul nr #1
9
12
Testul nr #2
1

[•anouk]

merci  .. la primul test nu-mi afiseaza decat 12, but i'm working on it

[•andunhill]

Nu ar trebui micsorata limita de timp    ? Sursa mea  http://infoarena.ro/job_detail/733433 merge sub 200 ms.

[•VisuianMihai]

La primul test, nu inteleg de ce e orasul 4. Nu ar trebui sa fie primul oras, pentru ca e mai aproape de multe orase decat 4?

[•Schumi]

Problema iti cere sa alegi orasul pentru care drumul maxim intre el si orice alt oras e minim. In cazul testului 1, distanta maxima de la orasul 4 la alt oras este 5 (drumul de la 4 la 3), pe cand distanta maxima de la orasul 1 la alt oras este 7 (drumul de la 1 la 5).

[•SebiSebi]

Folosesc multiset din STL si vreau ca functia heap.erase(x) sa stearga un singur element cu valoarea x chiar daca sunt mai multe cu aceeasi valoare. Cum fac asta? Multumesc!

[•vendetta]

stergi iteratorul pe care se afla elementul X
faci ceva de genul :

Cod:

multiset<int>::iterator it;
it = my_set.find(X);
my_set.erase(it);

[•SebiSebi]

Multumesc! A mers pana la urma.