071 Concurs

[•devilkind]

ati putea sa imi dati si mie un test mai mare sau mai complicat  . tot iau 30 de pct si nu inteleg de ce. Fac o parcurgere euler si apoi determin lca in o(n), si culmea ca nu iau TLE ci WA si nu inteleg de ce.

Retin maximu la fiecare query si dak lca(x,y)=sol[0] (sol[0]=maximu intalnit pana atunci, sol[1]=prima persoana care a lucrat la proiect si sol[2] - a doua persoana) atunci verific dak (sol[1]*10+sol[2]>x*10+y). chiar nu inteleg unde gresesc.

PS: Parcurgerea o fac recursiv am vazut ca sunt cateva posturi referitoare la acest lucru, insa nu inteleg ce legatura are chestia asta. arborele il retin folosind o lista de muchii pe care le ordonez dupa tata respectiv fiu dak e acelasi tata.

[•Marius]

Testul 8 nu merge nicicum! Este cineva amabil sa imi spuna cum as putea sa trec de el ?

Am rezolvat Atac cu acelasi LCA!

 

[•bogdan2412]

Radacina nu e neaparat in nodul 1... Eu din cauza asta picam testu 8

[•Marius]

Foarte subtil...

[•devilkind]

parca la lca puteam sa agatam arborele in orice radacina ?? nu vad ce importanta are radacina arborelui

[later edit] mda ca de obicei ziceam prostii, cu determinarea radacinii am luat 70 pct

[•sima_cotizo]

Are ceva testul 7 mai special ?!? ... ca e singurul pe care iau TLE.

Fac cam asa: un DF recursiv / BF cu o coada dinamica / BF cu coada = vector... si LCA in log₂(n) mai altfel decat in articol... adica:
1) aduc nodurile pe acelasi nivel [pe care il scot din DF/BF] ... adica pe ala care e mai "adanc" il urc pana cand ajung la aceeasi adancime
2) cat timp sunt diferite, urc ambele noduri prin tati...

La celelalte teste am maxim 0.5 secunde, si testul 7 mi se pare ca s-a zis ca nu ar fi unul maxim... deci inseamna ca cicleaza undeva acel LCA... sau ca am alta problema...

[•devilkind]

si daca ai un arbore de genu
1 2
2 3
3 4
5 6
...
N-1 N.
In cat timp determini lca dintre 1 si n. Mie mi se pare cam o(n). Sper ca exemplu nu contrazice datele problemei, am facut-o mai demult

[•sima_cotizo]

Yep stiu asta. Pai ummm... daca e asa se poate trata caz separat in problema, dar ar fi urat din partea mea... totusi daca e ceva de genu radacina are 2 fii si pe urma sa zicem ca restu sunt toti atarnati la rand de unul dintre ei... [nu toti ceilalti n-3 de unul din fii radacinii, ci unul dupa altul... in jos]... sau cazuri d-astea...

Ar mai fi ca abordarea mea ia log₂(n) in general daca e heap... sau daca majoritatea nodurilor au minim doi fii.

[•domino]

Exista pe site o groaza de documentatie despre LCA in O(sqrt(N)), O(lg^2 N), O(1), etc. .. pentru gusturile tuturor

[•devilkind]

care e ala in o(1) ?? eu nu am gasit nici un articol cu lca in o(1)

[•domino]

care e ala in o(1) ?? eu nu am gasit nici un articol cu lca in o(1)

Se pare ca in articolul cu LCA cu turul Euler e O(lgN), dar reducerea e triviala la O(1). Daca faci query intr-un interval [i..j] si k e cea mai mare putere a lui 2 a.i. 2^k <= j-i+1 ai RMQ(i, j) = min(A[ i ][k], A[j-2^k+1][k]) unde A[ x ][y] e minimul pe intervalul [x...x+2^y-1]

[•wefgef]

uite aici un articol care ar putea sa iti fie de folos:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

[•CezarMocan]

Nu reusesc sa fac programul sa treaca testul 8. Am citit ce s'a scris mai sus si radacina o aflu dupa citire, nu o iau direct 1. Ar mai fi si altceva?
[L.E.] Solved.

[•andunhill]

Testul 4 are ceva special? Orice as face iau WA pe el 

[•lucian666]

Ce are mai special testul 8 ?  

LE : Done 

[•stoianmihail]

Ce se intelege prin "cel mai mic sef comun al celor doi componenti din echipa"? - valoarea nodului ce reprezinta LCA-ul nodurilor sau seful comun cu valoarea cea mai mica?
Multumesc!

[•FlorinHaja]

Vă rog să corectați cerința... 

In cazul in care un component al unei echipe este seful celuilalt atunci proectul primeste puncte chiar de la acesta.