infoarena

Aici puteti discuta despre problema Arbori indexati binar (http://infoarena.ro/problema/aib).

HELP pls.
Am doua implementari http://infoarena.ro/job_detail/174357 de 50 p in care incerc sa fac operatia de tip 2 in O(log n) si a doua http://infoarena.ro/job_detail/174387 de 100 p in care la operatia de tip 2 gasesc indicele prin cautare binara. Nu reusesc cu nici un chip sa descopar ce gresesc la prima implementare. E sigur ca de la operatia de tip 2 vine greseala cat timp sursele sunt identice in rest. Poate reuseste cineva sa vada unde e greseala.
 Mii de multumiri.

Vezi ce afisezi cand cauti pozitia minima k astfel incat suma valorilor primilor k termeni sa fie exact 0.

Da, de la asta e. Daca k = 0 trebuie afisat -1.

Intr-adevar, asa era. Am facut modificarea si a mers. Inca odata multumesc.

In explicatia de pe ginfo despre aib zice ca pentru suma (a,b) se scad (1,b), si (1,a-1). Dar asta nu merge de exemplu pentru minim ... pentru minim cum se face ?

Nu poti folosi arbori indexati binar pentru astfel de query-uri. Trebuie sa folosesti alte structuri de date, cum ar fi arborii de intervale.

Se poate si cu arbori indexati binar, insa in O(log² n). Cu arbori de intervale ai O(log n).

O problema draguta cu aib-uri 2d e Mobiles de la IOI 2001, alta fiind si cutii de pe infoarena.

O chestie tare pe care tocmai am descoperit-o:

LSB(x) = x & -x :D

E veche. :D

Imi poate recomanda cineva un articol despre AIB in 2D si cum se implementeaza, ca din ce am cautat nu am gasit cine stie ce :)

Aib-urile 2d se implementeaza la fel ca cele 1 d doar ca ai doua foruri:


Uite inca o problema pe ideea asta: http://www.spoj.pl/problems/MATSUM/. De asemenea, vazusem cateva pe z-trening tot asa.

Spor :)

Mersi fain :)

Mobiles, IOI 2001 (http://olympiads.win.tue.nl/ioi/ioi2001/contest/A-2001-7.pdf)

E si pe spoj problema, se poate testa rezolvarea acolo https://www.spoj.pl/problems/NKMOBILE/

In tutorialul de pe topcoder se explica cum s-a ajuns la relatia asta.
Dar nu inteleg egalitatea de la care s-a pornit: Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1.
De ce opusul unui numar este egal cu "negatia" + 1?

Trebuie sa privesti problema din punctul de vedere al masinii, unde x este un sir binar. Asa sunt reprezentate de calculatoare numerele negative, se numeste reprezentare complementara si are importanta proprietate ca nu trebuie examinati bitii de semn la adunarea sau scaderea a doua numere.
http://cs.ubbcluj.ro/~rlupsa/edu/ac/doc/repr-intr.html
http://en.wikipedia.org/wiki/Two%27s_complement

Se pot executa cele 3 tipuri de operații în O(log₂N) și cu un arbore de intervale.
Sursa: http://infoarena.ro/job_detail/370470?action=view-source (http://infoarena.ro/job_detail/370470?action=view-source)

Ce spui tu este cunoscut, insa arborii indexati binar au avantajul spatiului: folosesti doar N elemente (in loc de 4N cat e la arborii de intervale). In plus, mi se pare ca sunt ceva mai rapizi pe operatiile pe care le implementeaza, dar se poate sa fie doar o parere :)

Știam că este cunoscut, numai că în "descrierea soluției" nu am văzut nimic legat de acest lucru.
Iar referitor la memorie, cred că sunt necesari doar 2N la arborii de intervale.

Arborii indexati binar sunt mult mai rapizi decat arborii de intervale, asa ca va recomand sa ii folositi de fiecare data cand puteti.

Legat de memoria folosita de un aint, daca N = 33 cat se aloca? 

O problema ciudata... la problema asta daca pun "inline" in fata functiei "search" .. iau 0 puncte cu raspuns incorect , daca scot  inline de la cautarea binara... iau 100 ...  :-k , probleme cu compilatorul ?

http://infoarena.ro/job_detail/463335
http://infoarena.ro/job_detail/463334

Daca schimbi denumirea functiei iti merge? Cred ca e un name clashing cu o functie din algorithm.

Am schimbat ... dar daca pun inline ... aceasi problema :)
http://infoarena.ro/job_detail/463342

Oricum... daca erau doua functii cu aceasi signiatura ar fi trebuit sa dea o eroare ( ambiguitate .... ) Mie imi compileaza fara nici o eroare .  + "inline" nu schimba signiatura functiei ...

Inline face codul functiei sa fie "copiat" pe unde apare (ma rog, daca compilatorul considera justificat)... De ce ai pune inline la o functie pe care o trimiti in printf? (Nu spun ca asta ar fi problema, doar ca ar putea fi o cauza...)

Acolo e ceva recursiv... si doar anumite recursivitati este capabil sa le transforme in ceva inline compilatorul cu toate astea teoretic am voie sa pun in fata oricarei functii si daca compilatorul considera oportun transforma in inline... daca erau in interiorul unei clase erau direct inline... Deci sigur e aberant sa fie de la asta.

Oricum, am pus inline pentru a vedea efectul pe care poate sa il aiba asupra unei functii care se autoapeleaza... ma asteptam sa nu apara modificari la timpi dar nu sa dea raspuns gresit...

Compilatorul nu face chiar o copiere acolo :d

Nu vreau sa pornesc o polemica, dar ... esti sigur de chestia asta? :)

Si da, nu e o copiere, dar ceva echivalent... Ma rog, mai bine retrag ce am zis pentru ca oricum nu pare sa fie de la asta problema :) ramane un puzzle interesant...

Din cate stiu cam asa este si am mai cititi ca programatorul nu are un control asupra ce functii sunt inline sau nu, acest lucru fiind in mare parte gestionat de compilator :)
Cand apelezi functia pune :: si apoi numele functiei si vezi :)

100% :) In general afli chestia asta printre primele cursuri de POO ( declarate si definite , nu doar declarate )

Eu votez pentru : bug de compilator sau incompatibilitati intre sistemul de evaluare infoarena si compilator

Citez din Thinking in C++ de Bruce Eckel :


sau

In exemplu suma de la 1 la 8 este 229 si nu 241, sau ma gresesc cu ceva?

I-mi cer scuze, m-am gresit eu :roll:

 Nu posta consecutiv. Editeaza-ti mesajele anterioare!

Salut! am si eu o intrebare! Ce metoda mai optima sa folosesc pt operatia 2? fac cautare binara pt gasirea lui K minim.
Las si sursa. Iau doar 40 p, imi cade pe timp pe ultimele 6. :sad:
Va multumesc anticipat!

Nu folosi endl ! Foloseste caracterul \n. Vezi cum iti intra in timp asa.

WAW ms... Iau 100 asa? chiar asa diferenta sa fie intre endl si \n? Stii cumva cauza?
Ms mult inca odata!

In C++ atunci cand afisezi ceva, programul tau nu va afisa imediat, ci va incarca ceea ce tu vrei sa afisezi intr-un buffer, pe care din cand in cand el il scrie pe disc. E mult mai rapid asa deoarece operatiile care lucreaza cu discul sunt foarte costisitoare, si e mai eficient daca ai de scris un sir de N biti sa il scrii pe tot odata decat sa scrii odata N / 2 biti si mai incolo sa mai scrii restu de N / 2 biti. Astfel caracterul '\n' este interpretat ca un simplu caracter si este adaugat in buffer pe cand endl adauga caracterul '\n' in buffer si da si o comanda de golire a bufferului.

De ex:
Va face urmatoarele operatii. Adauga pe "a" in buffer. Adauga '\n' in buffer, si scrie tot continutul bufferului pe disc. Acelasi lucru pentru a doua instructiune de scriere. Dupa cum vezi s-au facut 2 scrieri pe disc. Daca in loc de endl as pune '\n' atunci s-ar face o singura scriere pe disc pentru stringul "a\nb\n". Dimensiunea totala scrisa pe disc in ambele cazuri este aceeasi, difera insa frecventa cu care golesti bufferul.

Pe testul urmator majoritatea solutiilor observ ca dau 16 5 desi ar trebui sa dea 6 5...
17 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 5 1
0 6 1
2 2
2 1

se pare ca nu merge chiar atat de bine algoritmul la partea cu search... :P

Stiu ca numerele A[ i ] > 1 si nu se intalneste situatia in teste... dar sunt curios cum se rezolva in cazul in care apar si elemente nule :-?

Cred ca poti modifica algoritmul a.i. sa cauti cea mai mare pozitie pe care se afla o valoare mai mica decat K, doar ca de data asta pe pozitia maxima (fix acelasi algoritm de cautare, doar ca nu-l opresti cand ai gasit K-1 de exemplu, il lasi sa mearga pana la final). Daca pe pozitia urmatoare e K (asta afli tot in log cu un query normal) ai gasit solutie. Ia incearca, zic ca da bine :)

rezolvand problema initial nu am verificat ca acel K sa fie minim si luam 100. Ma gandesc ca ar fi ok sa puneti un test cu acel caz in care sa fie o valoare de 0.

1 ≤ Ai ≤ 10 000, pentru orice i, 1 ≤ i ≤ N

atunci care caz ar putea fi cand avem pozitii distincte pentru aceeasi suma?

nu exista :-'

pai... asta ziceam. ce rost are atunci acel "minim" din enunt? daca s-ar schimba conditiile ar avea.

sau?

Imi explica si mie cineva cum se face query de maxim ? Am vazut mai multe surse dar nimeni nu a explicat ideea si nu imi pot da seama ce fac oamenii astia pe acolo  :roll:. Apropo s-a discutat pe aici ca pentru un astfel de query , desi au complexitatea mai mare fata de arborii de intervale, in practica AIB se de descurca mai bine. Atunci mai exista vreun tip de query cand e de preferat sa se foloseasca arborii de intervale ?

Nu se poate face query de min/max pe un aib. :) De-asta se folosesc arborii de intervale.

Daca te uiti in arhiva educationala la arbori de intervale o sa vezi la comentarii surse care fac asta.

AIB-urile se pot folosi si pentru update/query de minim si maxim doar daca toate intervalele cu care au de a face sunt de forma 1..x. Se folosesc exact la fel ca si in cazul adunarii, doar ca se inlocuiesc operatiile de "+" cu cele de max( , ).

Update-ul arata cam asa: (poz e pozitia la care se face update-ul, val e valoarea cu care se face update)

Query-ul merge asa (se face query pe intervalul 1..poz):

Subscriu ce a zis Cezar, in arhiva educationala la problema arbori de intervale, solutia cu AIB merge mai bine decat cea cu AI, desi complexitatea teoretica e mai mare la AIB. Citez din mesajul lui Lucian Boca, din topicul adresat problemei AI :

Ca o completare la ce a zis Cezar, nu vei putea folosi AIB-urile in cazul in care poti avea update-uri de forma: la pozitia i, schimbi valoarea precedenta x cu o valoare y, x>y.

Multumesc pentru lamuriri.

 Arbori indexati binar se pot utiliza in calcularea min/max la fel ca si arborii de intervale. Mai important, exista solutie in logN amortizat folosint arbori indexati binar.
 
Practic, cele doua structuri de date sunt la fel de puternice !

Cum faci? Ai link către un articol? :D

Modific modul in care lucreaza update() si query().
Cand o sa am un link de la articol o sa il postez aici.

Poți detalia puțin? Sunt foarte curios cum faci pentru că mi-am pus și eu de mult timp problema asta și nu am găsit nicio soluție.

o aplicatie frumoasa :) http://acm.timus.ru/problem.aspx?space=1&num=1470

Sunt curios daca a incercat cineva sa implementeze AIB-uri cu update pe intervale :D (nu se adauga valoarea v la elementul de pe pozitia x, ci la toate elementele curinse intre pozitiile x si y), iar daca da, as aprecia daca mi-ar explica si mie cum a facut. Multumesc anticipat.

Poate cineva sa imi explice ideea care efectueaza oparatia 2 in log_n, eu lucrez in pascal si am facut in log^2_n dar asa iau TLE pe ultimile trei teste  ](*,)

hmm se poate uita cineva pe sursa mea iau 40 de pcte cu tle pe restu desi nu cred ca iau tle chiar pe 6 teste am facut solutia cu cautare binara oare de la aia e problema?

Editat de admin: Scrie corect, te rog.

Daca avem si elemente de 0 , cum facem cautarea pentru pozitia minima tot in log ?

Exact la fel. Nu te opresti cand gasesti un element cu suma identica, ci lasi cautarea pana la capat.

Nu cred ca merge pentru testul urmator :
n= 8
0 1 1 0 1 0 0 0
Cautare pozitia minima pentru suma = 3

La primul pas , o sa verifice exact T[8] = 3 si deja asta inseamna ca valoarea pe care o caut eu e cel putin egala cu 8 .

Cum adica la primul pas 8? Nu ceva gen (1 + n) / 2 ? Sau poate nu inteleg eu ce vrei sa spui. In cazul in care gasesti un element identic mergi pe intervalul din stanga.

Daca fac cum zici tu , atunci am un log pentru cautarea binara si inca un log pentru calculul sumei partiale , asta inseamna log^2. eu voiam in log simplu.

Ah, scuze. Probabil merge o varianta putin modificata a functiilor prezentate aici http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#find

E posibil de facut operatia de tipul 2 cu arbori de intervale in O(log n)?

Da.

Extrem de informativ. Un indiciu macar?
Scap de cautare binara sau gasesc suma 1..i in O(1)?

În principiu simulezi căutarea binară pe arbore. Dacă tu vrei să obții suma A, iar fiul stâng al rădăcinii are suma B >= A te duci în fiul stâng și continui căutarea, altfel o continui în fiul din dreapta pentru valoarea A - B.

Înțeleg că răspunsul pe care l-ai primit anterior nu te-a ajutat (deși tehnic ți s-a răspuns la întrebare), dar încearcă să fii mai politicos. Nu are niciun sens să fii sarcastic când ceri ajutor.

Thanks. Cam problematica aceasta operatie.

Îmi cer scuze că nu am detaliat răspunsul. Am crezut că vrei să știi doar dacă se poate rezolva în O(log N). Nu am vrut să îți stric plăcerea de a găsi o rezolvare, crezând că vrei să știi doar dacă are sens să te gândești la acea complexitate.

Salutare,

Cred că limita de memorie pentru Java este un pic cam strânsă.

in loc de x&-x puteti pune x-(x&(x-1))

O problema interesanta cu arbori indexati si de intervale s-a dat anul trecut la InfoOltenia.
Se gasesc aici problemele : http://mircea.unet.ro/io2015.zip (http://mircea.unet.ro/io2015.zip)