infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva educationala => Subiect creat de: Adrian Diaconu din Februarie 26, 2008, 23:43:39



Titlul: 007 Arbori de intervale
Scris de: Adrian Diaconu din Februarie 26, 2008, 23:43:39
Aici puteti discuta despre problema Arbori de intervale (http://infoarena.ro/problema/arbint).


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Mugurel-Ionut Andreica din Februarie 27, 2008, 20:25:43
Misto ideea cu arhiva educationala. Anyway, daca tot ati atins subiectul arborilor de intervale, as vrea sa propun, in scop educational, sa facem (si m-as implica si eu aici, daca va fi cazul) niste probleme care pun in evidenta mai bine ceea ce pot face arborii de intervale. M-am lovit de cateva ori de situatia in care elevi care ziceau ca stiu bine arbori de intervale nu au reusit sa ii extinda pentru a suporta niste query+update-uri mai "smechere". De exemplu, pare "inradacinata" ideea ca update-ul sau query-ul sunt aplicate pe un interval, iar operatia cealalta este aplicata asupra unui element (adica: update pe interval si query pe element sau update pe element si query pe interval).

Arborii de intervale sunt mult mai flexibili si suporta cel putin urmatoarele 4 situatii care apar prin probleme:

* creste valoarea fiecarui element dintr-un interval cu x (update) si intreaba care e suma elementelor dintr-un interval (query)
* creste valoarea fiecarui element dintr-un interval cu x (update) si intreaba care e minimul/maximul elementelor dintr-un interval (query)
* seteaza valoarea fiecarui element dintr-un interval la x (update) si intreaba care e suma elementelor dintr-un interval (query)
* seteaza valoarea fiecarui element dintr-un interval la x (update) si intreaba care e minimul/maximul elementelor dintr-un interval (query)

Nu o sa mai mentionez utilizarea altor tipuri de update-uri si query-uri (de exemplu, bazate pe operatii pe biti sau query-uri pentru minimul sumelor partiale sau pentru subsecventa de suma maxima - ultima problema aflandu-se si in arhiva infoarena).


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Savin Tiberiu din Februarie 27, 2008, 20:39:46
desi nu are legatura cu arbori de intervale, ar fi frumos sa se dea niste punctaje partiale (si sa fie mentionata in "indicatii de rezolvare" ) si ideea cu impartirea in bucati de sqrt(n) a vectorului.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Filip Cristian Buruiana din Februarie 27, 2008, 20:41:09
Ar fi foarte utile problemele pe care le-ai specificat. Am completat tabelul (nu am stiut cum sa trec mai concis, am scris arbori de intervale aplicatie 1, etc ).
Am adaugat problema separata pentru bucati de sqrt N. :)


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Cosmin Negruseri din Februarie 27, 2008, 21:30:37
Ar merge puse operatii de update diferite ca sa tinem tot in acelasi loc. Practic fiecare problema e un articol, nu are rost sa le dispersam prea tare.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Radu Zernoveanu din Februarie 29, 2008, 12:19:08
Cred ca limita de timp ar putea fi scazuta la 0.3 sec. :wink: Cu toate ca nu e chiar asa de important, ca daca face cineva cu arbori de intervale oricum intra in 0.3, iar daca face brut iese din 0.4...


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Cosmin Negruseri din Februarie 29, 2008, 12:20:29
Cartesian tree se poate face in O(n) ... si nu iti trebuie arbori de intervale. Poti citi rezolvarea in cartea lui Catalin Francu.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Lucian Boca din Aprilie 23, 2008, 19:59:17
Vad ca solutia cu AIB-uri (http://infoarena.ro/job_detail/184549) pentru maxime pe intervale, de complexitate teoretica O(log2 N) pe update si query, se comporta mai bine in practica decat cea cu arbori de intervale (http://infoarena.ro/job_detail/184554) (cu O(log N) pe fiecare operatie). Cel putin in implementarile mele :P


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Andrei Grigorean din Aprilie 23, 2008, 20:00:22
Nu doar in implementarile tale :). AIB ruleaza! :yahoo:


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Gogu Marian din Aprilie 24, 2008, 21:10:27
un AIB e mult mai cache-friendly decat un arbore de intervale.
cum in ultimii ani viteza procesoarelor a crescut mult mai repede ca viteza memoriilor, e din ce in ce mai important cache-ul.

Stiu ca multi din cei ce fac jocuri pentru Xbox / PS3 transforma in array-uri simple multe structuri de date avansate mai rapide asimptotic dar care sparg des cache-ul pentru ca au procesoare foarte rapide dar RAM mult mai incet.

In concluzie, folositi varianta in O(sqrt(N)) :)

http://infoarena.ro/job_detail/154183


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Cezar Mocan din Aprilie 24, 2008, 21:18:55
Stiti vreun articol mai pe intelesul tuturor in legatura cu cacheul? Ca nu prea inteleg cum sta treaba cu asta...


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Gogu Marian din Aprilie 29, 2008, 23:27:53
As baga eu un articol despre cache si ceva optimizari in general, daca se ofera cineva sa-l formateze frumos. :)


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Stefan Istrate din Aprilie 29, 2008, 23:39:46
Da, sigur. Hai ca ma ocup eu de aspect. Redacteaza-l. :)


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Oprescu Radu Constantin din Aprilie 30, 2008, 12:05:10
 
Stiu ca a fost prezentat acum cativa ani la Lot ceva legat de cache ... ( sper sa nu ma insel ) ...


Titlul: Răspuns: 007 Arbori de intervale
Scris de: vi zitator din Septembrie 08, 2008, 14:29:05
Cum pot creste la un arbore de intervale in care retin minimul de ex. toate elementele dintr-un interval cu un anumit numar (update-ul) ?


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Pripoae Teodor Anton din Septembrie 08, 2008, 14:45:31
 in o(n)...

gandeste-te ca tu tre sa faci update si la frunzele din arbore (elem cele mai de jos, la care intervalul are doar un elem) si pierzi pe alea o(n)


Titlul: Răspuns: 007 Arbori de intervale
Scris de: vi zitator din Septembrie 08, 2008, 14:55:09
la O(n) ma gandeam si eu....da e cam mare limita


am vazut si o problema pe infoarena......biscuiti......la care trebuie facut update pe un interval, si nu incape daca faci in O(n)


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Airinei Adrian din Septembrie 08, 2008, 15:17:49
Se poate O(logN), sunt mai multe detalii chiar in forum la problema biscuiti.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: vladiana micu din Octombrie 20, 2008, 21:29:15
cum pot face sa folosesci un vector de numa 2*n-1 elemente? ce conditii trebuie sa pun in plus? normal un arbore de intervale are numa 2*n-1 noduri.....


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Stefan-Alexandru Filip din Octombrie 21, 2008, 10:01:03
cum pot face sa folosesci un vector de numa 2*n-1 elemente? ce conditii trebuie sa pun in plus? normal un arbore de intervale are numa 2*n-1 noduri.....
Cand declari tabloul in care tii arborele de intervale, acesta nu trebuie sa aibe dimensiunea 2*n, ci mai degraba cea mai mica valoare mai mare sau egala cu 2*n care este si putere a lui 2. Adica pentru un n = 100000, ar trebui sa declari tabloul de 262144 ( 218 ).
Asta datorita codificarii pe care o faci nodurilor si a faptului ca arborele tau nu este un arbore complet binar. Pe penultimul nivel nu toate nodurile o sa aibe 2 noduri ca fii, ci multe o sa aibe un singur fiu. Indicile nodului curent poate insa sa ajunga pana la 2ceil(log(n))+1-1, pentru ca arborele are ceil(log(n)) + 1 niveluri.
Asta se intampla in cele mai multe implementari, si in sursa ta, poti sa folosesti si numai 2*n noduri, insa codificarea lor este mult mai dificila.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Florin Marius Popescu din Aprilie 02, 2009, 23:06:07
salut . ce optimizari pot sa fac la nivel de program pascal ca sa mi iasa in timp, pt imi depasheshte timpu cu 0.02, si nush ce sa fac. plus ca treaba e relativa, pe aceiashi sursa iau punctaje diferite, plus ca la unele teste timpul in care iese programu e mai mic decat cel impus de problema si totushi imi zice timp depashit...... 

si inca ceva : in pascal daca declaram un vector de intregi. si apoi il afisham pe ecran de ex, fara a face nici o modificare asupra lui. sau nu neaparat un vector: normal ar trebui sa apara valoarea nula adica 0 nu?  ms


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Philip din Octombrie 29, 2009, 23:21:08
Au fost schimbate testele la problema asta?
Rezolvarea mea (in pascal) nu reuseste nicicum sa intre in timp.
Am reintrodus si niste surse mai vechi, tot in pascal, care au luat 100 p cu cateva luni in urma, si nici ele nu scot mai mult de 50 p.


LE: Trebuia folosit "shl" si "shr" in loc de "*2", "/2", si in pascal trebuie parsata si citirea, altfel nu intra in timp.

LE2: Inca ceva... La testele 1 si 7 este cate un spatiu (" ") in plus la sfarsitul liniei cu elementele vectorului.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: alexandru din Ianuarie 28, 2010, 20:51:56
Imi putei spune, va rog frumos, cum as putea rezolva query-ul folosind aib-uri ? :)


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Andrei Misarca din Ianuarie 28, 2010, 21:18:22
Păi nu prea poți. Cu aib poți face query-uri doar pe intervalul [1, x], iar la minim/maxim nu prea mai merge treaba. Totuși, dacă citești toate posturile acestui topic vei afla că există o abordare a problemei cu aib în O(log2N) pe query.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: alexandru din Ianuarie 28, 2010, 21:23:11
Totuși, dacă citești toate posturile acestui topic vei afla că există o abordare a problemei cu aib în O(log2N) pe query.
M-am uitat peste sursa lui @Lucian si nu inteleg cum face acel query :(


Titlul: Răspuns: 007 Arbori de intervale
Scris de: nash mit din Iunie 27, 2010, 17:52:18
Am incercat sa fac cu AIB-uri. Nu realizez insa ce am gresit...
Folosesc doi vectori , unul pentru AIB si unul pentru numere .
Cand fac update modific vec[] ... punand noul element, apoi pun in AIB maximul dintre noul element si query( P - ZERO(p) , p-1 ) - adica maxim pana la elementul respectiv.
Apoi iau toate intervalele care cuprind acel element si fac update .

query() - merg de la "b" la "a" . Cand intervalul curent depaseseste capatul "a" .. nu ma uit in AIB ci direct la numarul de acolo si fac maximul cu rezultatul momentan apoi reiau AIB-ul de la urmatorul element. altfel.. iau maxiumul dintre ce am deja si ce este in AIB.

Este normal sa imi depasesca timpul... dar nu inteleg de ce da rezultat gresit.

http://infoarena.ro/job_detail/466835


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Pripoae Teodor Anton din Iunie 27, 2010, 22:02:25
Nu poti face query de maxim pe aib, pentru ca o sa ai maximul pe intervalul (1, b), nu pe intervalul (a, b).


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Mircea Dima din Iunie 27, 2010, 22:52:25
Ba poti!

Uite sursa:

http://infoarena.ro/job_detail/245035?action=view-source



Titlul: Răspuns: 007 Arbori de intervale
Scris de: nash mit din Iunie 27, 2010, 23:57:49
Normal ca poti...  :) Trebuie doar sa ai putina atentie la modul cum gandeste... citeste ce am scris eu... a mai fost discutat pe topicul acesta ... , evident complexitatea creste log^2N


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Pripoae Teodor Anton din Iunie 28, 2010, 08:08:03
Si de ce ai face asa ? Complexitatea e mai proasta, de scris scri mai mult, ...  :-k


Titlul: Răspuns: 007 Arbori de intervale
Scris de: nash mit din Iunie 28, 2010, 08:55:43
Pentru ca practic se comporta mai bine ( este mai  cache-friendly ) chiar daca complexitatea e mai mare  + pentru ca se poate + pentru ca vreau sa vad cum merge + pentru amorul artei + ca sa ma aflu in treaba, sirul ar putea continua...
 Dupa cum spuneam, s-a mai discutat pe subiectul acesta chiar in acest topic. ( citeste prima pagina ). Nu cred ca scrii mai mult...

Later edit:
  Am gasit eroarea, era o problema de un indice :d
http://infoarena.ro/job_detail/467671

Sursa ia decat 40p datorita faptului ca update-ul meu face doua query-uri si chiar daca complexitatea este tot log^2(n) dubleaza constanta . Am vazut ca se poate doar cu un singur apel de query() dar nu realizez cum se face asta. Poate sa explice cineva?

O optimizare care se poate face tine de initializarea vectorului care se poate face in O(n) fata de O( nlog^2(n) ) prin update-uri repetate.
http://infoarena.ro/job_detail/467686

Plus diferenta care duce de la 70p la 100p
http://infoarena.ro/job_detail/467851


Titlul: Răspuns: 007 Arbori de intervale
Scris de: nash mit din Iulie 01, 2010, 00:58:50
Se poate face query() si update() pentru max/min pentru secvente in logn ? ( cu AIB-uri )


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Petru Trimbitas din Iulie 24, 2010, 11:41:18
De ce in sursa oficiala dimensiune e 4*dim+66 si nu 2*dim-1 ?


Titlul: Răspuns: 007 Arbori de intervale
Scris de: nash mit din Iulie 28, 2010, 21:55:39
Citat
Cand declari tabloul in care tii arborele de intervale, acesta nu trebuie sa aibe dimensiunea 2*n, ci mai degraba cea mai mica valoare mai mare sau egala cu 2*n care este si putere a lui 2. Adica pentru un n = 100000, ar trebui sa declari tabloul de 262144 ( 218 ).
Asta datorita codificarii pe care o faci nodurilor si a faptului ca arborele tau nu este un arbore complet binar. Pe penultimul nivel nu toate nodurile o sa aibe 2 noduri ca fii, ci multe o sa aibe un singur fiu. Indicile nodului curent poate insa sa ajunga pana la 2ceil(log(n))+1-1, pentru ca arborele are ceil(log(n)) + 1 niveluri.
Asta se intampla in cele mai multe implementari, si in sursa ta, poti sa folosesti si numai 2*n noduri, insa codificarea lor este mult mai dificila.
In mod evident ar fi putut sa aleaga 2*n elemente. Dar ar fi fost mai urat la implementare ( ar fi trebuit sa aiba grija cu ultimul nivel din arbore ) . A ales forma aceea ca sa fie sigur ca numarul este suficient de mare cat sa intre in cea mai mica valoare mai mare sau egala cu 2*n care sa fie putere a lui 2 ( in mod cert ar fi putut sa o calculeze )



Titlul: Răspuns: 007 Arbori de intervale
Scris de: livica din Februarie 22, 2011, 13:28:01
Eu nu pot sa inteleg cum se reprezinta valorile din exemplu 4 3 5 6 1, ca un arbore de intervale.
 
Poate cineva sa-mi zica cum sunt asezate aceste valori in vectorul care memoreaza arborele?

Eu stiu si cum functioneaza un heap, dar aici nu-mi pot da seama.
Va multumesc!


Titlul: Răspuns: 007 Arbori de intervale
Scris de: George Marcus din Februarie 22, 2011, 14:26:40
Nu sunt reprezentate valori, ci (cum spune si numele) intervale. Daca luam A ca arborele de intervale, atunci el va arata cam asa:

A[1] (1,5) = 6 -maximul intregului sir
A[2] (1,3) = 5
A[3] (4,5) = 6
A[4] (1,2) = 4
A[5] (3,3) = 5
A[6] (4,4) = 6
A[7] (5,5) = 1
A[8] (1,1) = 4
A[9] (2,2) = 3

Edit: LoL... telepatie :)
P.S.: Acum ca ma uit mai atent...si se scrie "Fiii"


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Gabriel Bitis din Februarie 22, 2011, 14:28:18
Desi a mai postat cineva inainte, scrisesem si eu mesajul si poate te ajuta si ce'am scris eu :)

notam asa : [x,y](z) - intervalul x -> y are valoarea maxima z
[1,5](6) -radacina. Fii lui sunt [1,3](5) si [4,5](6)
[1,3](5) are fii [1,2](4) si [3,3](5)
[1,2](4) are fii [1,1](4) si [2,2](3)
[4,5](6) are fii [4,4](6) si [5,5](1)

Observi ca valorile citite se afla in frunze (adica in intervale de lungime 1 [x,x]). Pentru a construi arborele se pleaca din frunze.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: livica din Februarie 24, 2011, 15:37:32
Gata, am inteles.
Piuhh, greu de tot query-ul ala de inteles. Mi-a ars multi neuroni. #-o


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Alexandru-Iancu Caragicu din Martie 25, 2011, 13:46:42
Mai mariti limitele de timp un pic.
50 cu scanf, 100 cu fstream.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Gabriel Bitis din Martie 25, 2011, 17:26:34
100 cu scanf : http://infoarena.ro/job_detail/146448?action=view-source (http://infoarena.ro/job_detail/146448?action=view-source)
sunt bune limitele.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Boaca Cosmin din Martie 27, 2011, 20:51:33
Poate cineva sa-mi explice cum se face update-ul cand se sterge un element dintr-un interval ? M-am izbit de acest lucru la problema zeap . Nu am gasit alta solutie decat a decala toate elementele spre stanga ...


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Paul-Dan Baltescu din Martie 27, 2011, 21:41:36
Depinde ce operatie vrei sa faci. Daca vrei minim, pui infinit, daca vrei maxim, pui -infinit, daca vrei suma, pui 0, etc.

E mai bine sa pui intrebarile privind problemele din arhiva in topicul lor.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Boaca Cosmin din Martie 28, 2011, 08:33:52
Multumesc pentru raspuns si imi cer scuze pentru offtopic dar in topicul problemei respective era inactiv din 2008 si m-am gandit ca nu imi va raspunde nimeni . Mai am o intrebare ... o voi adresa tot in acest topic deoarece nu este neaparat legata d vreo problema anume . Am un sir d elemente si ma intereseaza maximul pe un interval la fiecare moment . Daca ar trebui sa sterg al 3-lea si al 4-lea element si as pune -infinit in locul lor apoi as interoga pentru intervalul [3,4] nu mi-ar -infinit ? Sau ar trebui sa consider ca pozitiile respective din sir devin inaccesibile ?


Titlul: Răspuns: 007 Arbori de intervale
Scris de: George Marcus din Martie 28, 2011, 13:37:54
Daca te referi la faptul ca dupa eliminarea pozitiilor 3 si 4, a treia si a patra pozitie vor deveni 5 si 6, atunci trebuie sa afli mai intai pentru un interval [a,b] pozitia celui de-al a-lea termen dupa eliminare si la fel pentru b si apoi faci query intre pozitiile aflate. Deci, pe exemplul tau vei face query pe [5,6].
Sper ca am inteles bine intrebarea ta.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Pirtoaca George Sebastian din Decembrie 28, 2011, 11:46:39
Cum pot sa cresc valorile dintr-un interval [a,b] cu o constanta val in O(log n)? Multumesc anticipat!


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Savin Tiberiu din Decembrie 28, 2011, 14:02:39
Tii o informatie suplimentara in fiecare nod, reprezentand valoare pe care ai adunat-o pe tot intervalu respectiv. Acuma cand faci un update, daca ai ajuns la un nod al carui interval asociat este inclus in intervalul [a, b] atunci updatezi valoarea respectiva, si atentie, NU mai continui recursvitatea in jos de acolo.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Pirtoaca George Sebastian din Decembrie 29, 2011, 13:46:19
Da, dar pe urma nu pot sa inteleg cum aflu maximul pe un interval. Daca poti sa imi scrii un cod sa inteleg mai bine.
Procedura de actualizare din articolul doamnei Lica ar arata cam asa ( sa spunem ca dorim marirea valorilor din intervalul [a,b] cu 5 ) :

void update(int nod, int st, int dr)
{
   int mij;
   if((a<=st)&&(dr<=b)) {
      MaxArb[nod]=MaxArb[nod]+5;
      return;
   }
   else {
      mij=(st+dr)/2;
      if(a<=mij)
         update(2*nod,st,mij);
      if(mij<b)
         update(2*nod+1,mij+1,dr);
      MaxArb[nod]=MaxArb[nod]+5;
   }
}

Gresesc undeva, dar nu imi dau seama unde.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Paul-Dan Baltescu din Decembrie 29, 2011, 15:02:08
Tu gresesti pentru ca cresti maximul indiferent daca esti sau nu in interval (datorita instructiunii cu + 5 in else).

Daca vrei ca apoi sa obtii maximul pe intreg sirul, functia ar trebui sa fie ca mai jos. Daca vrei sa faci query-uri de maxim pe anumite intervale, atunci trebuie sa faci lazy update si lucrurile devin mai complicate.

Cod:
void Update(int update_left, int update_right, int value, int left, int right, int node) {
if (update_left <= left && right <= update_right) {
add[node] += value;
maxim[node] += value;
} else {
int mid = (left+right) / 2;
if (update_left <= mid) {
Update(update_left, update_right, value, left, mid, node*2);
}
if (update_right > mid) {
Update(update_left, update_right, value, mid+1, right, node*2+1);
}
maxim[node] = max(maxim[node*2], maxim[node*2+1]) + add[node];
}
}


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Andrei Dinu din Ianuarie 19, 2012, 21:56:20
Nu stiu ce se intampla.. Am facut o sursa la problema asta pe care eu o consider corecta si i-a 0 pct.
In final am testat si sursa oficiala care i-a 0 pct:
http://infoarena.ro/job_detail/664311?action=view-source (http://infoarena.ro/job_detail/664311?action=view-source)

Need HELP!!!


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Mihai Calancea din Ianuarie 19, 2012, 22:34:50
Din functia de query:

Cod:
else if(div < finish) Query(2*nod+1,div+1,right);

Esti sigur de chestia asta? Gandeste-te un pic. Also, gandeste-te un pic si la cratime :).


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Andrei Dinu din Ianuarie 19, 2012, 23:15:05
Merci mult!
Am reusit pana la urma!  =D&gt;


Titlul: Răspuns: 007 Arbori de intervale
Scris de: stardust din 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.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Mircea Dima din 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


Titlul: Răspuns: 007 Arbori de intervale
Scris de: George Marcus din Iunie 13, 2012, 15:21:39
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...


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Andrei Grigorean din Iunie 13, 2012, 17:30:40
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.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: George Marcus din 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.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Mircea Dima din Iunie 13, 2012, 23:56:42
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.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Bratu Alexandru din 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 !!!


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Pirtoaca George Sebastian din 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.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Oncescu Costin din 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.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Salajan Razvan din 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;


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Pirtoaca George Sebastian din Februarie 09, 2013, 12:45:39
Cred ca ar trebui marita limita de timp. Se poate lua 100 doar cu parsare. Multumesc!


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Stratulat Alexandru din Martie 15, 2013, 17:00:40
Imi poate spune cineva ce reprezinta vecotul A in care se retin elemente din vector ? :sad:


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Ionita Bogdan Constantin din 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!


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Anonymous din 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


Titlul: Răspuns: 007 Arbori de intervale
Scris de: John Peter din 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


Titlul: Răspuns: 007 Arbori de intervale
Scris de: FMI Cornoiu Vlad din Aprilie 01, 2014, 13:33:41
Imi explica si mie cineva, va rog, de unde vine 4*dim+66 ?  :D


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Lup Vasile din Aprilie 01, 2014, 15:50:20
Ce dimensiune trebuie sa aiba un arbore de intervale?


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Vlad Badelita din 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).


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Gogu Marian din 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.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Marius Nicoli din 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 ...


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Mihai Calancea din Iulie 14, 2014, 02:46:14
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.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: FMI-Coteanu Vlad din 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?


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Pirtoaca George Sebastian din 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.


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Parfene Narcis din 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?


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Dragos-Alin Rotaru din August 10, 2015, 21:26:27
Poţi ca în fiecare nod să îţi ţii o structură (http://www.cplusplus.com/doc/tutorial/structures/) în care memorezi valoarea şi poziţia elementului din vector. În felul acesta, atunci când alegi maximul pentru fiecare nod, poţi doar să compari cele 2 structuri între ele folosind un operator de comparare (http://ideone.com/cqqZWt).

Sau poţi doar să îţi mai ţii un vector în care memorezi poziţia fiecărui element dintr-un nod şi îl actualizezi în timp ce faci update clasic pe valoarea nodului din arborele de intervale. :)


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Ardeleanu Vlad George din Octombrie 29, 2015, 09:26:02
Puteti sa-mi raspunde-ti la topic al deschis de mine


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Patrick Sava din Mai 23, 2016, 20:39:10
Implementez eu ceva intr-un mod neoptim, sau la problema asta chiar e imposibil sa iei 100 in Java ?


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Valeriu Motroi din Mai 24, 2016, 09:56:16
Incearca sa construiesti arborele in timp O(N)... poate ajuta

UPD: dar nu cred să ajute..


Titlul: Răspuns: 007 Arbori de intervale
Scris de: andrei din August 18, 2016, 22:36:50
Poate ar trebuii modificata limita de timp:
Brute force trebuie sa ia 30-40 dar ia 50 (http://www.infoarena.ro/job_detail/1743886)
Cu intervale de radical(n) trebuie sa ia 50 dar ia 100(http://www.infoarena.ro/job_detail/1743939)


Titlul: Răspuns: 007 Arbori de intervale
Scris de: mihai craciun din August 19, 2017, 20:37:50
WTF imi da 0 puncte cu incorect pe primele 3 teste si TLE pe ultimele 7, insa am verificat Testul 1 (si 2) si raspunsul este exact la fel. ???????

Sursa: http://www.infoarena.ro/job_detail/2012947


Titlul: Răspuns: 007 Arbori de intervale
Scris de: Matteo Verzotti din August 08, 2019, 19:18:34
Salut, nu vreau sa fac reclama la alt site sau ceva dar mi-a fost greu sa inteleg de pe wikipedia, insa pe csacademy arborii de intervale sunt prezentati foarte bine si intr-o maniera interactiva, poate puteti adauga link catre site?
https://csacademy.com/lesson/segment_trees