infoarena

Aici puteţi discuta despre problema Radiatie (http://infoarena.ro/problema/radiatie).

Imi poate explica si mie cineva mai pe indelete sol. a doua din articol de la Radiatie? Din cate stiu eu, chiar daca nu folosesti comprimare de drumuri, arborele partial de cost minim tot va fi un arbore degenerat. Daca ai face o simpla parcurgere pe acest arbore ar putea sa te duca la un raspuns gresit pt. ca ai putea avea nevoie de o muchie X - Y pe care nu o ai in arborele respectiv , dar caruia i-ai introdus capetele unindu-le cu un reprezentant Z ...si o sa ai muchie de la X la Z si de la Y la Z, muchii carora poate nici macar nu le sti costul.  :-k

Multumesc!   :peacefingers:

Sa presupunem ca unesti reprezentatul lui X(sa-i zicem A) cu reprezentantul lui Y(B). Vei adauga muchia A-B cu costul muchiei X-Y. Ideea este ca pe drumul de la X la A vei gasi muchii de cost mai mic decat cea de cost X-Y din felul in care parcurgi muchiile pentru APM. Analog pentru drumul de la Y la B. Deci oricum cand vei interoga un element care se afla initial in multimea cu A si unul din multimea lui B raspunsul va fi dat de costul muchiei X-Y ( muchia A-B din APM ) , iar cand se fac query-uri in aceeasi multime muchia X-Y nu afecteaza costul dupa cum era normal.

Eu tot nu inteleg ceva... Fac cam in felul urmator:
1. determin APM in NlogN
2. raspund la intrebari astfel: fie x=LCA (nod1, nod2); solutie=max(max_de_pe_drum(nod1,x),max_de_pe_drum(nod2,x));

Iau Signal 11 intr-o veselie, desi mie imi merge acasa.

E cumva posibil ca graful din fisierul de intrare sa nu fie conex? Pentru ca daca nu e conex, arunc la gunoi toata sursa, ca in loc de 1 APM, am o padure de APM  :?

Nu e precizat in enunt ca graful e conex

graful e conex cred, ptr ca eu am luat 100 cu o rezolvare asemanatoare cu a ta. Banuiesc ca folosesti un arbore de intervale ptr lca, vezi ca parcurgerea euler are 2*n-1 elemente, vezi dak arborele de intervale are o dimensiune buna ptr atatea elemente.

Doar atat. Nu se zice ca graful ar fi conex. :)

Am o solutie care iese din timp pe jumatate din teste. Fac asa:
- construiesc APM-ul, cu algoritmul lui Prim, folosind si un min-heap. [ deci O(M*logN) ]
- execut un DF, pentru a construi parcurgerea euleriana si adancimile pt fiecare nod. [ deci O(N+M) ]
- calculez rmq[ j ] [ i ] - pozitia elementului minim a secventei de lungime 2^j care incepe pe pozitia i. [secventa considerand vectorul cu adancimi] [ deci O(Nr*logNr), unde Nr - nr de elemente ale parcurgerii euleriene]
- Pt o pereche (i,j) data
   --- calculez LCA(i,j) in O(1) ( folosind rmq-ul ). ( sa zicem ca LCA(i,j) = nod)
   --- calculez muchia de cost maxim deplasandu-ma in arbore de la i la nod, respectiv muchia de cost maxim deplasandu-ma in arbore de la j la nod. Afisez muchia de cost maxim din cele doua muchii. Aici cred ca e problema algoritmului meu, pentru ca pot ajunge chiar la O(N) pt fiecare operatie.

In sfarsit, cum as putea sa rezolv optim o problema de genul urmator: "Se considera un arbore. Se dau doua noduri x si y, precum si predecesorul lor comun minim z. Aflati muchia de cost maxim de pe drumul x -> z -> y. " Se poate mai mult de O(N) sau trebuie sa ma gandesc la alta rezolvare [respectiv, cea care e descrisa in articolul cu solutii] ?

Va multumesc!

Ai putea sa mai tii o matrice Max[ i ][ j ] - muchia de cost maxim dintre nodul i si stramosul lui, 2 ^ j. Astfel poti raspunde in O(1) si la aceasta interogare. :D Iar construirea o poti face odata cu calcularea matricii RMQ[ i ][ j ].

 :ok: Multumesc pentru idee. Mi-a iesit in cele din urma.


LE: max[ i ][ j ] nu poate fi calculata odata cu rmq[ i ][ j ], pentru ca rmq[ i ][ j ] se face pe toata parcurgerea euler ( care poate avea chiar 2*n-1 elemente ), pe cand max[ i ][ j ] se face doar pe intervalul [1,n].

Cand am spus ca poti construi matricea RMQ[ i ][ j ] ma refeream la matricea stramosilor. Adica in RMQ[ i ][ j ] credeam ca retii al
2 ^ j - lea stramos al nodului i, de aceea am spus ca merge construita deodata cu matricea Max[ i ][ j ]. Daca te uiti putin mai atent peste sursa mea ai sa vezi ca este posibil :D.

Nu inteleg.

de la 1 la 3 n-ar trebui sa fie 9?  :fighting:

Poti sa adaugi in problema ca in fiecare camera exista cate un aparat care-l vindeca de efectele radiatiilor, deci conteaza doar cat se expune intr-un singur tunel (sa nu i se faca rau), dar nu conteaza suma expunerilor pe tot drumul. :D

Imi poate da cineva un test mai complex, pentru ca iau 0p si imi ies toate exemplele pe care le dau.

Construiesc APM-ul cu Kruskal si apoi determin maximul de pe drum pana la LCA cu al 2^j - lea stramos.

Sursa : http://infoarena.ro/job_detail/696015?action=view-source