090 Delay

[•domino]

Aici puteţi discuta despre problema Delay.

[•filipb]

Imi poate spune cineva ce structura ar trebui aplicata la asta, pentru a modifica valoarea unui nod in O(logN) si pentru a afla suma nodurilor de la radacina la un nod tot in O(logN)?   Eu am incercat cu AIB, unde al i-lea element retine suma nodurilor pana la al 2^k-1-lea stramos, unde k este numarul de 0 terminale din reprez. binara a NIVELULUI nodului i. Astfel, suma pana la radacina o pot calcula in O(logN), dar pentru modificare pot modifica tot O(N) elemente... Am incercat in loc de reprez. binara a NIVELULUI sa pun DFN-ul, da' tot nu iese nimic...  
  Poate sa aplic ceva in vreo parcurgere euler?

  Ma poate ajuta cineva?

[•domino]

Imi poate spune cineva ce structura ar trebui aplicata la asta, pentru a modifica valoarea unui nod in O(logN) si pentru a afla suma nodurilor de la radacina la un nod tot in O(logN)?   Eu am incercat cu AIB, unde al i-lea element retine suma nodurilor pana la al 2^k-1-lea stramos, unde k este numarul de 0 terminale din reprez. binara a NIVELULUI nodului i. Astfel, suma pana la radacina o pot calcula in O(logN), dar pentru modificare pot modifica tot O(N) elemente... Am incercat in loc de reprez. binara a NIVELULUI sa pun DFN-ul, da' tot nu iese nimic...  
  Poate sa aplic ceva in vreo parcurgere euler?

  Ma poate ajuta cineva?

Ca structura de date poti folosi usor un arbore de intervale, evantual si un AIB, important e cum il folosesti... ideea de a folosi parcurgea euler sau timpii din DFS (asta e DFN, nu?) este buna, incearca sa te folosesti de asta. Spor la treaba!  

[•filipb]

DFN = Depth first number, adica da, timpii din DFS.
   Mersi de sfaturi!

[VladS]

Sa vedeti ce-am descoperit. Am facut rezolvarea cu O( sqrt(N) ) pe update si O( 1 ) pe query si luam 7 TLE-uri si 3 WA. Si ca sa vad unde gresesc  am trimis O( N ) pe update si O(1) pe query si am luat 100   . Mai trimit odata 90, mai trimit odata iar 100. Testele sunt alese un pic naspa, nu credeti ?

[u-92]

cum ai facut tu O(1) pe query? nu cumva sqrt(N)?

[VladS]

Pai la query: lca e O( 1 ) si interogarea aia tot O(1).

[•marius21]

Am primit mesaj de compilare nereusita la Delay, iar la mine acasa merge.

[•azotlichid]

Intr-adevar...am o vaga impresie ca e ceva din cauza compilatorului de fpc instalat pe sistemul de evaluare
Sper sa rezolvam problema cat de repede posibil...

[•peanutz]

A mai facut cineva O(n) pe update si O(logn) pe query? Eu am facut lca, minimul dintre pozitiile din parcurgerea euleriana il aflu cu arbori de intervale. Imi cicleaza pe undeva sau chiar nu ar trebui sa mearga? Cu metoda asta iau 10, iar cu brute-ul iau 30

[•Mishu91]

Imi puteti da o idee cum sa fac atunci cand schimb valoarea unui nod? Ca am incercat sa fac update pe parcurgerea euler folosind arbori de intervale, dar m-am impotmolit la aflarea sumei tuturor updatelor pentru un nod de la radacina pana la nodul respectiv. Si alta idee nu prea am

[•Marius]

... m-am impotmolit la aflarea sumei tuturor updatelor pentru un nod de la radacina pana la nodul respectiv.

Dacă te vei uita în Articole vei găsi ce cauţi.

[•Mishu91]

Acuma vazui articolu despre descompunerea arborilor. Foarte tare faza cu liniarizarea 

[•mihai.alpha]

Foarte ciudat. Mi-am facut cateva teste si toate merg, comparand rezultatele cu sursa comisiei. Ce ar putea sa-mi scape?!
Va rog, ajutati-ma