|
Titlul: 090 Delay Scris de: Mircea Pasoi din August 30, 2005, 17:47:11 Aici puteţi discuta despre problema Delay (http://infoarena.ro/problema/delay).
Titlul: 090 Delay Scris de: Filip Cristian Buruiana din Septembrie 06, 2005, 10:43:40 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)? :oops: 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? :-s Ma poate ajuta cineva? Titlul: 090 Delay Scris de: Mircea Pasoi din Septembrie 06, 2005, 12:30:20 Citat din mesajul lui: 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)? :oops: 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? :-s 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! :D Titlul: 090 Delay Scris de: Filip Cristian Buruiana din Septembrie 06, 2005, 12:45:57 DFN = Depth first number, adica da, timpii din DFS.
Mersi de sfaturi! Titlul: 090 Delay Scris de: VladS din Februarie 06, 2006, 15:36:09 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 :shock: . Mai trimit odata 90, mai trimit odata iar 100. Testele sunt alese un pic naspa, nu credeti ?
Titlul: 090 Delay Scris de: u-92 din Februarie 06, 2006, 16:12:53 cum ai facut tu O(1) pe query? nu cumva sqrt(N)?
Titlul: 090 Delay Scris de: VladS din Februarie 06, 2006, 16:46:27 Pai la query: lca e O( 1 ) si interogarea aia tot O(1).
Titlul: Raspuns: 090 Delay Scris de: Marius Petcu din Iunie 14, 2006, 14:06:38 Am primit mesaj de compilare nereusita la Delay, iar la mine acasa merge.
Titlul: Re: 090 Delay Scris de: Adrian Vladu din Iunie 14, 2006, 15:06:20 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... Titlul: Răspuns: 090 Delay Scris de: Andrei Homorodean din Iulie 25, 2007, 15:31:44 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 :(
Titlul: Răspuns: 090 Delay Scris de: Andrei Misarca din Mai 29, 2009, 21:44:46 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 :)
Titlul: Răspuns: 090 Delay Scris de: Marius Stroe din Mai 29, 2009, 23:35:07 ... 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. ;) Titlul: Răspuns: 090 Delay Scris de: Andrei Misarca din Mai 30, 2009, 14:51:52 Acuma vazui articolu despre descompunerea arborilor. :D Foarte tare faza cu liniarizarea =D>
Titlul: Răspuns: 090 Delay Scris de: mihai craciun din Februarie 05, 2017, 23:46:09 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 |