277 CT

[ditzone]

Aici puteţi discuta despre problema CT.

[•Marius]

Imi spune si mie cineva o idee ?

[•wefgef]

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

[•StTwister]

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

[•astronomy]

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

[•Florian]

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? 

[•wefgef]

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.

[•Florian]

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 

[•pauldb]

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

[•Florian]

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. Cam dubioasa intamplarea... 

[•wefgef]

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.

[•ctlin04]

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 

[•PlayLikeNeverB4]

Cred ca e prea stransa limita.

[•mvcl3]

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

[•Zenus]

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

[•crisovidiu]

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?

[•alex1096]

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