007 Arbori de intervale

[•informatician28]

Merci mult!
Am reusit pana la urma! 

[•stardust]

Cum pot face update sa incrementez valorile dintr-un interval [x,y] ? Daca cobor pana in frunze si updatez fiecare interval de lungime 1 presupun ca este ineficient.

[•blasterz]

Cum pot face update sa incrementez valorile dintr-un interval [x,y] ? Daca cobor pana in frunze si updatez fiecare interval de lungime 1 presupun ca este ineficient.

Trebuie sa folosesti tehnica "lazy update/delete".
In fiecare nod al arborelui trebuie sa mentii 3 valori:
Full[nod] = true daca tot intervalul corespunzator nodului are aceeasi valoare, false altfel
V[nod] = valoarea in cazul in care Full[nod] == true
Sum[nod] = suma pe interval

In plus, cand faci update, trebuie sa pasezi informatiile la fii inainte sa apelezi recursiv.

Uite aici o sursa
http://hickery.net/info/aint2.html

[•PlayLikeNeverB4]

Uite aici o sursa
http://hickery.net/info/aint2.html

Intr-o sursa in care vrei sa explici ceva, nu inteleg de ce ai scrie chestii gen "p^=q^=p^=q" sau sa inlocuiesti "/2" cu ">>1". Ar trebui sa o faci cat mai clara, in stil Python. Parerea mea...

[•wefgef]

Uite aici o sursa
http://hickery.net/info/aint2.html

Intr-o sursa in care vrei sa explici ceva, nu inteleg de ce ai scrie chestii gen "p^=q^=p^=q" sau sa inlocuiesti "/2" cu ">>1". Ar trebui sa o faci cat mai clara, in stil Python. Parerea mea...

a ^= b ^= a ^= b interschimba valorile celor doua variable.

[•PlayLikeNeverB4]

a ^= b ^= a ^= b interschimba valorile celor doua variable.

Intamplator am mai intalnit asta si stiam ce face. In fine, daca altii inteleg inseamna ca nu e nicio problema.

[•blasterz]

Uite aici o sursa
http://hickery.net/info/aint2.html

Intr-o sursa in care vrei sa explici ceva, nu inteleg de ce ai scrie chestii gen "p^=q^=p^=q" sau sa inlocuiesti "/2" cu ">>1". Ar trebui sa o faci cat mai clara, in stil Python. Parerea mea...

Sursa, precum si siteul, le.am facut prin 2008 si nu le.am revizuit de atunci. In plus asta e ceva mai avansat de aint si consider ca cineva care a ajuns sa invete asta ar trebui sa stie operatii pe biti. Sursa unde prezint aint normal nu foloseste operatiile pe biti.

[•bratualex]

Imi poate spune si mie cineva de ce sursa asta nu ia decat 50 de puncte ? ce ar trebui sa modific ca sa intre intr-un timp mai bun pt testul 7 . sursa :   https://infoarena.ro/job_detail/760233?action=view-source                       Multumesc !!!

[•SebiSebi]

Incearca sa pui inline la functii iar apoi scapa de parametrii aceeia multi de la functii( de ultimii 2 ), ei se salveaza pe stiva pentru nimic. Tu oricum nu ii mai folosesti.

[•geniucos]

Imi mai puteti da o data sursa care la update incrementeaza un interval [x,y] si apoi pune query despre sum pe niste intervale?
Link-ul http://hickery.net/info/aint2.html dat de Mircea Dima nu mai merge  .Multumesc anticipat.

[•vendetta]

Uite aici : http://ideone.com/FmVovv o sursa pentru udpate pe un interval cu o valoarea x si apoi sa zici care e suma pe un interval;

[•SebiSebi]

Cred ca ar trebui marita limita de timp. Se poate lua 100 doar cu parsare. Multumesc!

[•Fayed]

Imi poate spune cineva ce reprezinta vecotul A in care se retin elemente din vector ?

[•bodyionita]

Limita de timp cu adevarat trebuie marita intrucat rezolvarea acestei probleme nu tine de "ingeniozitatea" de a parsa citirea ci de a lucra cu arbori de intervale... Multumesc!

[•Anonymouslegion]

Nu as zice, mie imi intra in timp si fara parsare, si cu un mod dubios de a implementa ainturile mult mai incet decat ar fi normal:
http://www.infoarena.ro/job_detail/998234?action=view-source

[•JohnPeter]

Pe de alta parte, daca modul devine de a implementa devine mult mai dubios, parsarea devine necesara:
http://www.infoarena.ro/job_detail/1053869?action=view-source

[•vladutz15]

Imi explica si mie cineva, va rog, de unde vine 4*dim+66 ? 

[•https]

Ce dimensiune trebuie sa aiba un arbore de intervale?

[•toranagah]

Pai fiind un arbore binar echilibrat, ai 1 nod(radacina), cu 2 fii, urmati de 4 noduri, 8 etc, pana la ultimul nivel unde ai fix N noduri.
Asta e egal cu 2⁰ + 2¹ + 2² ... +2^X = 2^X+1 - 1, unde 2^X = N.
2^X+1 = 2 * 2^X = 2 * N. Deci un 3 * N ar trebui sa ajunga(pentru ultimul nivel, incomplet).

[•gogu]

De fapt 3*N nu e de ajung tot timpul, 4*N e mai sigur.
Concret, nivelul K are 2^K noduri, deci in total o sa fie 2*Pow-1 noduri in arbore, unde Pow e cea mai mica putere a lui 2, mai mare sau egala cu N.
Cand N e de forma 2^K+1, ai nevoie de cam 4*N elemente.
Pe scurt, 4*N+10 e cel mai sigur, si nu iti mai faci griji de cazuri particulare. Niciodata nu e recomandat sa bagi limite stricte la array-uri decat atunci cand chiar esti fortat.

[•mariusn01]

Cred ca ar trebui marita putin limita de timp. Pentru a obtine 100 trebuie scris un algoritm bine optimizat, adica elevul trebuie sa sa ocupe si de altceva decat de implementarea corecta a structurii de date (de exemplu trebuie evitate unele variabile locale, functia de query trebuie sa nu returneze valoare, trebuie renuntat la unii parametri ai functiilor de update si query - in ultimul caz algoritmul devine mai putin clar cand il explici cuiva prima data ...).
Cand cineva invata prima data algoritmul si vede ca nu obtine 100 poate crede ca algoritmul lui nu e bun si se poate descuraja ... Si sursa prezentata drept oficiala ruleaza aproape de timpul maxim pe unele teste ... In fine, e doar o parere ...

[•klamathix]

Am mărit la 0.5 . În general dacă mai vedeți limite prea strânse, mai ales în arhiva educațională, anunțați, fiindcă n-avem nicio intenție să le ținem așa dacă nu e nevoie.

[•sicsic]

http://www.infoarena.ro/job_detail/1320123?action=view-source
Mesajul evaluatorului pentru toate testele :
www.infoarena.ro/job_detail/1320123

Si totusi, programul ruleaza si daca folosesc testele de la atasamente, imi da raspuns corect. Ajutor?

[•SebiSebi]

Faptul ca primesti SIGSEGV depinde de sistemul de operare pe care se testeaza solutia. De exemplu Unix-urile sunt mai "sensibile" decat Windows-ul. Exista situatii cand un program functioneza pe Windows dar pe Unix (ex. Ubuntu, Mint) primeste SIGSEGV.

[•nparfene2004]

Va rog sa ma ajutati si pe mine cu urmatoarea problema:
Cum pot modifica functia Query astfel incat sa furnizeze pozitia maximului si nu maximul?