417 Maxq

[•DITzoneC]

Aici puteţi discuta despre problema Maxq.

[•Darth_Niculus]

   De ce cand aloc 400001 de noduri pentru arborele de intervale iau 70 pct cu SIGKILL pe restul testelor..... si cand aloc 600001 noduri iau 100 pct... in enunt scrie ca sunt maxim 200000 elemente... deci ar trebui sa ajunga 400000 de noduri ?

[•blasterz]

Un arbore de intervale are nevoie de 2^k > 2n elemente ...

[•Darth_Niculus]

aha... daps pare logic..

[•recviem]

Un arbore de intervale nu are nevoie doar de (2*n-1) elemente ?

[•devilkind]

Nu. Daca consideri ca fii lui i sunt 2*i si 2*i+1 atunci frunza care contine elementul a[n] are pozitia 2^( [lg N]+1 ) - adica parte intreaga plus 1.

[•recviem]

Well da, dar ultima frunza va fi pe pozitia (2*n -1). Nu mi-am dat seama ca se intampla sa-i accesezi fii.

[•popoiu.george]

Cred ca ar trebui marita limita de timp la problema asta. Cu solutia oficiala iau 70.

In plus, am facut rost de o sursa care lua 100p inainte de upgradarea evaluatorului si am retrimis-o si aceea ia tot 70p.  

LE : Problema SequenceQuery e aceeasi problema, dar fara update-uri si N,M<=100000 si are tot 0.6 limita de timp.
http://infoarena.ro/problema/sequencequery

[•SpiderMan]

Da stiu si eu am pus la vreo doua probleme, struti si color4, care pe evalu' asta nou, acuma ceva timp lua 100, si acuma, la problema struti ia ceva in gen 60, si color4 ia tot 100, doar ca cu timpi mult mai mari. Dar se pare ca nu are nimeni timp sa se uite sau sa explice de ce a intervenit asta .

[•savim]

Suntem constienti ca exista probleme cu noile limite de timp, in definitiv s-a folosit un algoritm care nu a avut un procentaj de 100% la recalcularea corecta a acestora. De asemenea va reamintesc ca exista o pagina speciala unde e bine sa puneti informatii despre probleme la care aveti impresia ca limita noua de timp este eronata (si daca exista si o sursa oficiala, ar fi extraordinar sa reusiti sa o trimititi si sa precizati cat obtine).

http://infoarena.ro/calibrare-limite-de-timp

@Spiderman: Multe dintre problemele raportate au fost rezolvate, iar la multe dintre celelalte este nevoie si de o schimbare a testelor pentru a putea diferentia complexitati apropiate in mod corect. Nu cred ca este cazul sa te plangi aiurea pe forum despre asta. Exista si un topic special creat unde poti discuta pe tema asta : http://infoarena.ro/forum/index.php?topic=6051.0 .  

Din punctul meu de vedere, e mai bine sa facem totul sa mearga ok, decat sa bagam la repezeala, nu?

P.S.: Am modificat limita la maxq, sper sa fie in regula acum.

[•SpiderMan]

Ok, am inteles mesajul, am postat si acolo, bine macar ca m-a lamurit cineva, nu a fost atat de greu la urma urmei un post pentru clarificare nu ? Totusi, ati putea rezolva eroare de compilare de la sistem2 va rog (daca nu trebuie schimbate testele ...).
PS : Merci savim .