015 Arbori indexati binar

[•sima_cotizo]

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

[•nash]

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

[•sima_cotizo]

daca erau in interiorul unei clase erau direct inline...

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

[•BitOne]

daca erau in interiorul unei clase erau direct inline...

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

[•nash]

daca erau in interiorul unei clase erau direct inline...

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

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

[•marcelcodrea]

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

Citez din Thinking in C++ de Bruce Eckel :

In solving the C++ problem of a macro with access to private class members, all the problems associated with preprocessor macros were eliminated. This was done by bringing the concept of macros under the control of the compiler where they belong. C++ implements the macro as inline function, which is a true function in every sense. Any behavior you expect from an ordinary function, you get from an inline function. The only difference is that an inline function is expanded in place, like a preprocessor macro, so the overhead of the function call is eliminated. Thus, you should (almost) never use macros, only inline functions.

sau

The logical behavior of a function must be identical regardless of whether it’s an inline (otherwise your compiler is broken). The only difference you’ll see is in performance.

[•ion_caliman]

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

Nu posta consecutiv. Editeaza-ti mesajele anterioare!

[•niovan]

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.
Va multumesc anticipat!

[•popoiu.george]

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

Cod:

...
fout<<Compute(dr)-Compute(st-1)<<"\n";
...
fout<<Binar(val)<<"\n";

[•niovan]

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

Cod:

...
fout<<Compute(dr)-Compute(st-1)<<"\n";
...
fout<<Binar(val)<<"\n";

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

[•devilkind]

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:

Cod:

cout << "a" << endl;
cout << "b" << endl;

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.

[•Protoman]

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

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

[•GavrilaVlad]

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

[•razyelx]

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.

[•PlayLikeNeverB4]

Cod:

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

[•razyelx]

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

[•Magnus]

nu exista

[•razyelx]

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

sau?

[•soriyn]

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

[•Magnus]

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

[•soriyn]

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

[•CezarMocan]

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)

Cod:

void update(int poz, int val) {
    int i;
    for (i = poz; i <= N; i += lsb(i)) 
        AIB[i] = max(AIB[i], val);
    
}

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

Cod:

int query(int poz) {
    int i, sol = 0;
    for (i = poz; i > 0; i -= lsb(i)) 
        sol = max(sol, AIB[i]);
    return sol;
}

[•SpiderMan]

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 :

Vad ca solutia cu AIB-uri pentru maxime pe intervale, de complexitate teoretica O(log² N) pe update si query, se comporta mai bine in practica decat cea cu arbori de intervale (cu O(log N) pe fiecare operatie). Cel putin in implementarile mele

[•GavrilaVlad]

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.

[•soriyn]

Multumesc pentru lamuriri.