830 Arb

[•DITzoneC]

Aici puteti discuta despre problema Arb.

[•mihai0110]

se poate rezolva aceasta problema, parcurgand la fiecare interogare i j toate nodurile de pe nivelul lvl [ i ]  + j + 1 ? momentan iau 60, insa fara afisare ia doar o secunda pe cel mai mare test.

[•CezarMocan]

Incearca sa gasesti o solutie mai eficienta

[•vendetta]

Salut! Iau 90 de puncte cu tle pe ultimul test. Am complexitatea (n+m) log n folosind un arbore de intervale si am folosit citerea parsata.
Am incercat cu aib si iau 60 de puncte cu tle pe ultimele 4.

[•retrograd]

Este solutie liniara la problema asta.

[•klamathix]

Erau testele slabe. E O(n * m) ce ai tu acolo, gândește-te de ce and fix it  .

[•retrograd]

Mi-am dat seama, asa e. Oricum, nu cred ca am ce imbunatati la solutie, ca sa ii reduc timpul. Trebuie sa ma gandesc la altceva...

[•Archazey]

Am doua surse aproape identice.
http://www.infoarena.ro/job_detail/1461891 -timpi mai buni
http://www.infoarena.ro/job_detail/1461890 - timpi rai
Diferenta intre cele doua este ca in loc de NMAX+MMAX(la declararea vectorilor) am mai facut o variable XMAX.Daca fac XMAX am timpi cu 100 ms mai prosti(foarte mult).
Mai mult am observat ca surse cu 2*NMAX la declarari in loc de MMAX sau 3*NMAX in loc de NMAX+MMAX au timpi cu 150ms mai prosti
Imi poate explica cineva de ce e asa?
Am stat o ora cu sursa oficiala in fata pentru ca nu stiam ce sa mai optimizez,facusem tot cum era acolo,inafara de asta...

EDIT:
inca 2 surse prea ciudate
http://www.infoarena.ro/job_detail/1461906 - testul 6 720ms
http://www.infoarena.ro/job_detail/1461905 - testul 6 388ms

E prea mare diferenta,nu inteleg...
Am schimbat din 2*NMAX in MMAX,doar la un vector,atat. Si cu 2*NMAX merge mai bine

[•pas.andrei]

Cred ca limita de timp e prea mica, solutia oficiala nu intra nici daca bag parsare