040 Lowest Common Ancestor

[•Marius]

Aici puteţi discuta despre problema Lowest Common Ancestor.

[•Bogdan_tmm]

Cod:

Următoarea linie conţine n-1 numere naturale, cel de-al i-lea număr reprezentând tatăl nodului i+1 (nodul 1 fiind rădăcină nu are tată).

Ar trebui sa se specifice ca se incepe numaratoarea de la i=2 ca sa fie totul perfect:D. Daca se subintelege(probabil toata lumea a inteles) atunci sa ma scuzati
L.E. da eu nu intelesesem cum trebuie:D

[•Mishu91]

Numărătoarea începe de la 1, primul număr de pe linie este tatăl nodului 2, al doilea tatăl nodului 3, etc.

@Marius: Mă cheamă Mișarca, nu Mișarcă

[•APOCALYPTO]

Ce se intampla cu evaluatorul la problema asta ? iau intre 3600 si 3700 ms si imi da TLE . Streamurile sunt de vina? Sau ce ca vad ca multi au luat 70 de puncte:|

[•Mishu91]

Limita de timp este destul de strânsă  , dar diferenÈ›a de timp între soluÈ›ia cu RMQ È™i cea în O(NlogN + MlogN) este foarte mică. De altfel, dacă citeÈ™ti cu streamuri È™i afiÈ™ezi standard ai È™anse mari să iei 100 È™i cu soluÈ›ii care au complexitatea logN/query

[•Andrei_Scorpio]

Am 3644ms pe ultimul test si imi da TLE cand limita de memorie este 3.7sec adica 3700ms  cred ca sunt vreun geniu daca am ajuns la performanta asta: sa nu mi se puncteze pe motiv de TLE ceva care intra in timp.

[•Marius]

Am 3644ms pe ultimul test si imi da TLE cand limita de memorie este 3.7sec adica 3700ms  cred ca sunt vreun geniu daca am ajuns la performanta asta: sa nu mi se puncteze pe motiv de TLE ceva care intra in timp.

Dacă te-ai fi gândit un pic ţi-ai fi dat seama că timpii sunt estimativi. Dacă vei reuşi să creezi un evaluator ce opreşte la fix 3700ms atunci să ni-l trimiţi şi nouă.

[•gabitzish1]

Nu s-ar putea afisa la TLE niste timpi cu 0.2-0.3s mai mari?
Sa nu mai existe persoane intrigate de chestia asta, ca tot apare cate unul nou si iar intreaba de ce are tle pe un timp mai mic decat limita...

[•wefgef]

Am 3644ms pe ultimul test si imi da TLE cand limita de memorie este 3.7sec adica 3700ms  cred ca sunt vreun geniu daca am ajuns la performanta asta: sa nu mi se puncteze pe motiv de TLE ceva care intra in timp.

Dacă te-ai fi gândit un pic ţi-ai fi dat seama că timpii sunt estimativi. Dacă vei reuşi să creezi un evaluator ce opreşte la fix 3700ms atunci să ni-l trimiţi şi nouă.

Evaluatorul opreste la timp programul concurentului. Doar timpii afisati sunt estimativi, in realitate programul este lasat sa ruleze exact cat e limita.

[•Cosmin]

Nu puteti schimba codul sa afiseze timpii putin diferit sau sa puneti o explicatie acolo. Vad ca problema asta cu timpii aproximativi si programele oprite la limita de timp apare destul de frecvent pentru incepatori.

[•bogdan2412]

Am modificat, apare "Limită depăşită" acum.

[•Mishu91]

Am modificat, apare "Limită depăşită" acum.

La Memory Limit Exceeded apare așa

Cod:

Limită depăşită/td>

Deși era un lucru care se cam impunea, nu pot să nu remarc că acum borderoul de evaluare arată foarte urât.

[•andrei-alpha]

Am modificat, apare "Limită depăşită" acum.

Mai bine afisezi timpul normal +200 ms ca sa fie peste tot timpul peste limita sau pui doar "-".
Arata destul de aiurea asa.

[•bogdan2412]

Am modificat, apare "Limită depăşită" acum.

La Memory Limit Exceeded apare așa

Cod:

Limită depăşită/td>

Deși era un lucru care se cam impunea, nu pot să nu remarc că acum borderoul de evaluare arată foarte urât.

Am rezolvat cu /td> Am observat si eu ca arata urat dar nu prea mi se pare bine sa bag timp +200ms cum a sugerat Andrei pentru ca o sa fie oameni care o sa zica ca le merge programul mai bine / mai prost in urma unei optimizari, desi de fapt nu e relevanta diferenta. Am pus "Depasit" in loc de "Limita depasita" si arata mai ok.

[•Andreid91]

cred ca fisierele de intrare au un spatiu in plus...dupa ce citesti cele n-1 valori

[•Mishu91]

Dap, este foarte posibil sa fie aşa, dar nu prea văd cu ce ar putea încurca citirea. Dacă va fi nevoie, voi modifica testele astfel, ca acel spaţiu să nu mai fie acolo.

[•Bit_Master]

Pe TopCoder scrie ca pot fi folosite oricare 2 pozitii ale aparitiilor nodurillor din query in reprezentarea Euler a arborelui.
Eu cred ca ar trebui specificat ca se pot lua oricare aparitii, dar pentru simplitate se pot lua primele.
Asa ar parea ca primele au vreo proprietate speciala.

[•sunt_emo]

Nu vad cu ce ar putea simplifica lucrurile faptul ca alegi primele aparitii, odata ce folosesti rmq (varianta <O(n*logn),O(1)>

[•Mishu91]

Am modificat timpul de execuţie, şi acum ar trebui să fie în regulă. Am să dau şi un re-eval de îndată ce revine butonul

[•R.A.R]

Timpul de executie cred ca este prea mare deoarece pe sursa O(N*M) am luat 90pct.

[•visanr]

Done.

[•dutzul]

hmm nus prea bune testele cu solutie n*m iei 90 de pcte si cu o sursa gresita iei 80,plus solutia mea cu in O(n+m*sqrt) ia mai mult timp decat cea n*m;

[•alexalghisi]

Buna , pentru o Reprezentarea Euler a unui arbore cu N noduri si M muchii , ce memorie e recomandata in alocarea vectorului care va stoca reprezentare ? [ Pura curiozitate ]

[•SebiSebi]

Dimensiunea vectorului ar trebui sa fie 2*m+1. Poți deduce asta dacă te gândești la cum parcurgi graful ca sa obții reprezentarea Euler.

[•alexalghisi]

Ahh da , intradevar  multumesc !