infoarena

Aici puteţi discuta despre problema CT (http://infoarena.ro/problema/ct).

Imi spune si mie cineva o idee ?

Daca ai distruge toate LCA-urile, atunci ai fi sigur ca nu exista drum intre cele 2 noduri din oricare pereche.

Nu iti ramane decat sa vezi cum minimizezi numarul de LCA-uri pe care le distrugi (adica daca ptr 2 noduri ai distrus deja un nod de pe drumul ce le unesete, nu mai are rost sa distrugi LCA-ul lor).

Cum pot sa gasesc in mod optim LCA-urile care sunt in plus?

Faci o parcurgere din radacina arborelui, intai rezolvi subarborii radacinii si apoi vezi daca mai are sens sau nu sa elimini radacina.

Are cineva idee ce au testele 5,6 si 9 ? Am deja ore de debug si nu gasesc niciun test pe care sa nu-mi mearga. Programul pare perfect. Folosesc ideea din articolul cu solutii (varianta a 2-a). Exista vreun caz particular mai ascuns?  :annoyed:

Tin minte ca am avut si eu probleme cu testele astea. Din pacate sursa nu o mai am (era pe infoarena 1), dar parca buseam ceva foarte stupid - nu declaram vectorul pentru aint destul de mare.

Multumesc mult! Am reusit sa iau 100. Intr-adevar, greseam ceva stupid. Am declarat peste tot dublu decat declarasem initial si am luat 100. Dar mi se pare ciudat. Tind sa cred ca testele nu respecta restrictiile  :-k

Poti sa bagi assert-uri in sursa ta si daca ceva nu e in regula, contacteaza-ma.

Am verificat si testele sunt ok. Totusi, parcurgerea Euler nu are 2*N - 1 elemente? [N - nr de noduri]. Chiar nu stiu ce are sursa asta (http://infoarena.ro/job_detail/325754?action=view-source). Cam dubioasa intamplarea...  :-k

Pai parcurgerea euler are 2*n elemente => aint-ul trebuie sa aiba 8*n elemente (4*n nu este de ajuns - vezi cazul cand n = 9, aint-ul = 64).

Edit: Acum vad ca tu ai facut cu RMQ. Eh, o fi ceva aseamantor.

Ma ajuta cineva sa mai optimizez inca cu vreo 50 ms, ca eu nu mai am nici o idee, am facut LCA cu RMQ, si am aflat toate LCA-urile la gruparile de orase teroriste, am sortat descrescator cele k LCA-uri dupa nuvelul LCA-ului in arbore cu quicksort, apoi am eliminat nodurile in O ( n+k ), plus am parsat si citirea  ](*,)
Mai este vreo optimizare care sa micsoreze complexitatea sau e da la PASCAL  :?

Cred ca e prea stransa limita.

imi explica si mie cineva care ar fi problema in solutia mea ](*,)
http://www.infoarena.ro/job_detail/1043463?action=view-source

eu am facut lca pentru fiecare a si b din cele K si dupa aia le-am sortat dupa nivelul lor in arbore
am parcurs lca-urile si verificam daca nodurile din care este format lca-ul dat sunt nemarcate ambele faceam df pentru subarborele lc-aului

   Dupa ce fac fiecare LCA si le ordonez dupa nivel , ce fac??

Merge sa fac o liniarizare si apoi sa rezolv problema cuielor, intervalele fiind "formate" din first[ x ] si first[ y ] unde x si y sunt bazele unei organizatii sau metoda asta e total pe langa?

Poate sa ma ajute cineva? Pe testele 4,5,6 si 9 imi da incorect desi mie imi merge pe toate exemplele. Am incercat sa maresc si dimensiunile vectorilor dar tot acelasi rezultat. Sursa este http://www.infoarena.ro/job_detail/1419337?action=view-source (http://www.infoarena.ro/job_detail/1419337?action=view-source)