040 Lowest Common Ancestor

[•alecsandru]

copiata de la alex cuturela

[•AlexandruValeanu]

Cred ca limita de timp este prea mare. O(N*M) ia 90p si O(M*sqrt(N)) ia 100p.
O(N*M): http://www.infoarena.ro/job_detail/1184901
O(M*sqrt(N)): http://www.infoarena.ro/job_detail/1184904

[•SRadu]

Nu conteaza. E arhiva educationala. Rezolvi problemele ca sa inveti ceva, nu ca sa scoti puncte.

[•AlexandruValeanu]

Ziceam ca idee.

[•https]

Se poate sa fie probleme cu evaluatorul? Primesc 0 puncte, dar am downloadat primul test si il rezolva corect la mine pe calculator.
http://www.infoarena.ro/job_detail/1232715?action=view-source

[•vladrochian]

Se poate sa fie probleme cu evaluatorul? Primesc 0 puncte, dar am downloadat primul test si il rezolva corect la mine pe calculator.
http://www.infoarena.ro/job_detail/1232715?action=view-source

Un prim lucru pe care îl observ e că ai vectorul lg prea mic

[•https]

  asa e ) Multumesc mult. Si, btw, sursa oficiala cu rmq atunci cand e trimisa da eroare de compilare.

[•vladrochian]

dacă înlocuiești typeof cu decltype probabil va merge (C++11 stuff)

[•Butnaru]

Ce sa intimplat cu compilatorul de la pascal,sursele care inainte luau 100 de puncte cu un timp detasat de limita acum primesc 70 de puncte cu 2 TLE.Sper ca o sa rezolvati multumesc mult

[•margiki]

Traiasca Bogdan Batog si smenul lui !

[•witsel]

ar putea sa-mi spuna si mie ce e gresit la sursa mea ? #1415472

EDIT: Am gasit. Pusesem j<<1 in loc de 1<<j

[•Eman98]

Linkul la TopCoder nu merge.
Link bun : https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

[•andreiiii]

Linkul la TopCoder nu merge.
Link bun : https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

Fixed.

[•irimiec]

Am impresia ca nu sunt concludente testele, cu http://www.infoarena.ro/job_detail/1622695 (modificata putin pentru evidentiere) nu tin cont de nivelul nodurilor si fac direct RMQ pe indicele nodurilor, si tot iau 100.

Asta ar insemna ca pentru orice nod, tatal lui are indicele < ca indicele nodului

si un exemplu de test care ar da WA pe sursa mea, dar merge pe o sursa implementata corect:

Cod:

11 5
6 1 6 6 1 4 4 2 3 3
10 11
8 9
5 11
5 6
4 2

gresesc eu pe undeva? sau e specificat asta si n-am inteles eu enuntul?

[•rares96cheseli]

Cred ca ar trebui modificata putin limita de timp deoarece am luat 100p cu dinamica de la Stramosi si intra lejer in timp (2,2sec pe testul 9)

[•dadadada]

Cod:

void dfs(int nod, int lev)
{
    H[++K] = nod; //nodul actual este adaugat in reprezentarea Euler a arborelui
    L[K] = lev; //se retine nivelul fiecarei pozitii din reprezentarea Euler a arborelui
    First[nod] = K; //se retine si prima aparitie a fiecarui nod in reprezentarea Euler a arborelui
     
    foreach(G[nod])
    {
        dfs(*it, lev+1);
         
        H[++K] = nod;
        L[K] = lev;
    }
}

Buna ziua ,
Daca m-ati putea ajuta cu aceasta nelamurire.
Cand se opreste aceasta functie ?
Care e conditia de oprire ?

[•Bodo171]

Nu e nevoie de conditie de oprire in cazul asta,deoarece daca tinem doar fiii in lista de adiacenta,functia nu va mai continua cand va ajunge intr-un nod fara fii.Poti simula asta pe foaie cu un arbore si o sa-ti dai seama mai bine.

[•Andrei-27]

sursele sunt aproape indentice ( structurile de date sunt la fel , ideea e aceasi  ) si totusi diferenta pe ultimul test e de 500 ms


https://infoarena.ro/job_detail/2310708


https://infoarena.ro/job_detail/2308666


rog pe cineva care are timp sa arunce o privire