Pagini: 1 2 [3] 4   În jos
  Imprimă  
Ajutor Subiect: 007 Arbori de intervale  (Citit de 62516 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
informatician28
Strain
*

Karma: 6
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #50 : Ianuarie 19, 2012, 23:15:05 »

Merci mult!
Am reusit pana la urma!  Applause
Memorat
stardust
Strain
*

Karma: 13
Deconectat Deconectat

Mesaje: 39



Vezi Profilul
« Răspunde #51 : Iunie 13, 2012, 13:08:20 »

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.
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #52 : Iunie 13, 2012, 13:49:22 »

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
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #53 : Iunie 13, 2012, 15:21:39 »

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...
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #54 : Iunie 13, 2012, 17:30:40 »

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.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #55 : Iunie 13, 2012, 23:30:52 »

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.
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #56 : Iunie 13, 2012, 23:56:42 »

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.
Memorat
bratualex
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #57 : Iunie 20, 2012, 17:05:03 »

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 !!!
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #58 : Iunie 20, 2012, 17:10:45 »

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.
« Ultima modificare: Iunie 20, 2012, 17:19:22 de către Pirtoaca George Sebastian » Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #59 : Octombrie 30, 2012, 17:22:57 »

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  sad.Multumesc anticipat.
Memorat
vendetta
De-al casei
***

Karma: 72
Deconectat Deconectat

Mesaje: 122



Vezi Profilul
« Răspunde #60 : Octombrie 30, 2012, 21:08:01 »

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;
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #61 : Februarie 09, 2013, 12:45:39 »

Cred ca ar trebui marita limita de timp. Se poate lua 100 doar cu parsare. Multumesc!
Memorat
Fayed
Client obisnuit
**

Karma: -24
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #62 : Martie 15, 2013, 17:00:40 »

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


Karma: -2
Deconectat Deconectat

Mesaje: 6



Vezi Profilul
« Răspunde #63 : Septembrie 21, 2013, 18:30:24 »

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!
Memorat
Anonymouslegion
Strain


Karma: 6
Deconectat Deconectat

Mesaje: 10



Vezi Profilul
« Răspunde #64 : Septembrie 21, 2013, 22:16:28 »

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
Memorat
JohnPeter
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #65 : Decembrie 12, 2013, 23:36:39 »

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
Memorat
vladutz15
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #66 : Aprilie 01, 2014, 13:33:41 »

Imi explica si mie cineva, va rog, de unde vine 4*dim+66 ?  Very Happy
Memorat
https
Strain
*

Karma: 0
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« Răspunde #67 : Aprilie 01, 2014, 15:50:20 »

Ce dimensiune trebuie sa aiba un arbore de intervale?
Memorat
toranagah
Strain


Karma: 2
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #68 : Aprilie 03, 2014, 13:53:52 »

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 20 + 21 + 22 ... +2X = 2X+1 - 1, unde 2X = N.
2X+1 = 2 * 2X = 2 * N. Deci un 3 * N ar trebui sa ajunga(pentru ultimul nivel, incomplet).
Memorat
gogu
Client obisnuit
**

Karma: 42
Deconectat Deconectat

Mesaje: 98



Vezi Profilul
« Răspunde #69 : Aprilie 03, 2014, 20:16:58 »

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.
Memorat
mariusn01
Strain


Karma: 4
Deconectat Deconectat

Mesaje: 16



Vezi Profilul
« Răspunde #70 : Iulie 13, 2014, 12:54:18 »


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 ...
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #71 : Iulie 14, 2014, 02:46:14 »

Am mărit la 0.5 Smile. Î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.
Memorat
sicsic
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #72 : Ianuarie 17, 2015, 17:26:28 »

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?
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #73 : Ianuarie 18, 2015, 00:23:46 »

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.
Memorat
nparfene2004
Client obisnuit
**

Karma: 22
Deconectat Deconectat

Mesaje: 81



Vezi Profilul
« Răspunde #74 : August 10, 2015, 19:02:46 »

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?
Memorat
Pagini: 1 2 [3] 4   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines