016 Range minimum query

[•SpiderMan]

Ai putea da edit prost si ai putea sa lasi spatii intre [] si i, ca sa nu scrie italic ( [ i ] ) .

[•klamathix]

eu am inteles rmq-ul asta dar am o intrebare:

de ce folosim puteri ale lui 2 si nu ceva mult mai simplu precum o progresie aritmetica?
in felul asta matricea ar fi mai mare ce-i drept insa query-ul ar fi mai rapid pentru ca nu ar mai fi nevoie sa calculam minimul dintre doua valori (deoarece nu vom mai folosi log)

cum m-am gandit eu:

a[ i ][ j ]=min(a[i-1][j],a[i-1][j+i-1]);
a[ i ][ j ]=min(a[0][j],...,a[0][j+i]);
deci a[ i ][ j ] este minimul pe sirul care incepe la j si are lungimea de i+1

prin urmare minimul din intervalul [x,y] ar fi pur si simplu a[ y-x ][ x ] (fara sa trebuiasca sa mai folosim vreo functie de minim)

deci, eu zic ca metoda asta a mea e mai eficienta fata de cea de pe site, atunci cand se  
folosesc foarte multe interogari.

Gresesc undeva?

Pai din modul in care ai descris matricea sa inteleg ca ocupa O(n ^ 2) memorie (si timp pentru preprocesare) ?

[•livium]

Da, cel mult O(N^2). Insa avantajul se va concretiza la query, deoarece nu mai trebuie sa aflam vreun minim ci doar returnam a[ y-x ][ x ].

[•DraStiK]

Idea ta nu este optima, pentru ca ai aceasi complexitate pentru o interogare ca si solutia optima.

Complexitatea ta totala este: O (N^2+M), iar cea optima este O (N^log N + M).

Pe langa asta, si complexitatea memoriei e ineficienta la tine.

[•livium]

care este complexitatea lui min(a[ h ][ x ],a[ h ][ x+sh ])?
este O(1)?

dar complexitatea lui a[ y-x ][ x ]?
este tot O(1)?

nu ia mai mult timp prima varianta pt. ca se compara doua valori, pe cand in a doua doar se returneaza o valoare?

Daca e asa, atunci pt. un milion de interogari sa zicem,  nu e metoda mea mai eficienta, desi ocupa mai multa memorie si timp la crearea matricei?

[•pauldb]

Da, ambele solutii au complexitate O(1).

Poti citi mai multe despre notatia "O" pentru complexitatea timp: aici si aici, dar se mai gasesc si multe alte articole pe net sau in carti de specialitate (de exemplu in "Introducere in algoritmi" de Cormen, Lieserson, Rivest, Stein).

Vei intelege de ce este utila astfel de ierarhizare a complexitatii algoritmilor si nu numararea efectiva a operatiilor dupa ce vei lucra ceva mai mult.

[•livium]

OK.
Merci pentru informatii.

[•vladtarniceru]

imi puteti da va rog un articol unde sunt explicati pe larg arborii de intervale, RMQ si LCA?
multumesc

[•MciprianM]

Mie mi s-a parut foarte bun articolul de pe Topcoder, pentru RMQ si LCA. Pentru arbori de intervale ar trebui sa ajunga sa intelegi ideea din arhiva educationala.

Apoi mai ramane sa faci multe probleme cu fiecare.

[•Bit_Master]

eu iau 40 cu arbori de intervale
si am implementat la fel cum am implementat la "arbori de intervale" din arhiva educationala, unde am luat 100.

[•SpiderMan]

Cod:

Putem de asemenea rezolva problema folosind un arbore de intervale ( vezi problema Arbori de intervale ). 
Aceasta idee are complexitatea O(NlogN+MlogN) si ar trebui sa obtina 60-70 de puncte.

[•ELHoria]

Se poate folosi rmq sa tii subsecventa de suma maxima de pe un interval ?

[•devilkind]

Da se poate, doar ca e ceva mai complicat.

[•informatician28]

Eu am rezolvat problema cu arbori de intervale si am luat 100

[•dan_tudor]

Buna ziua!
As avea si eu o intrebare. Cand rezolv problema in timp ce imi construiesc matricea de RMQ daca fac for-urile asa:

Cod:

     for(int i = 1 ; (1<<i) <= n ; ++ i)
           for(int j = 1 ; j <= n - ( 1 << i ) ; ++ j)

pe test nu imi da bine pe al treilea interval. Insa daca trimit sursa iau 100 de puncte.  Deci practic din forul cu j lipseste acel " + 1 " la conditia j-ului.
Intreb asta fiindca am vazul ca la solutia oficiala pentru LCA forul e facut la fel ca mai sus. Imi puteti spune si mie care ar putea fi explicatie acestui fapt? Multumesc anticipat si o seara cat mai placuta.

[•PlayLikeNeverB4]

E gresit daca nu pui "+1" fiindca nu vizitezi toate pozitiile. Probabil ca nu exista in teste intervale pentru care minimul e la sfarsitul sirului.

[•Thomas]

La restrictii spune ca numerele sunt in intervalul [1,100 000]

Cred ca in testul 3 apare si numarul 0, pentru ca solutia mea cu:

Cod:

M[i][j]=min(M[i][j-1],M[i+put[j-1]][j-1]);
        if(!M[i][j]) M[i][j]=M[i][j-1];

Ia doar 90 de puncte (pica testul 3), pe cand cu:

Cod:

if(i+put[j-1]<=n) M[i][j]=min(M[i][j-1],M[i+put[j-1]][j-1]);
        else M[i][j]=M[i][j-1];

Ia 100.

EDIT: Acum am aflat ca poti vedea testele si am vazut ca nu e niciun 0. Mi se pare totusi ciudat comportamentul la acea schimbare

[•PlayLikeNeverB4]

Daca i + put[j-1] > n atunci M[i+put[j-1]][j-1] e 0(cel mai probabil).

[•pop_bogdan]

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

Imi spune cineva de ce iau doar 10 puncte? unde am gresit?

[•klamathix]

Ai declarat invers matricea.

[•pop_bogdan]

  mersi mult

[•AlexandruValeanu]

Doar ca fapt divers, ce faci tu nu este eficient deoarece faci O(logN) pe query calculand logaritmul. Incearca sa preprocesezi [logX] pentru fiecare X <= N, altfel nu are sens sa faci RMQ.

[•RusuAlexei]

Sint probleme cu evaluatorul (pentru Pascal) sau au fost schimbate testele?
Sursa care mai devreme trecea lejer toate testele acum ia 80p cu TLE.

[•ctlin04]

S-au schimbat versiunile de evaluator de ceva timp pe infoarena respectiv si timpii de executie la fiecare problema s-au micsorat si acum este destul de probabil ca unele surse sa ia tle

[•MciprianM]

Cu solutia in complexitate sqrt(N) se poate lua 70p (in loc de 40p), daca se calculeaza pentru fiecare pozitie i din sir, minimul pe intervalul [i, i + sqrt(n) - 1]. Asta se poate face in O(N), folosind solutia de la problema deque. Apoi pentru a afla raspunsul la un query se merge prin vectorul calculat, prin pozitiile x, x + sqrt(n), ... atata cat e posibil, apoi se parcurg restul(maxim sqrt(N)), element cu element. Are aceeasi complexitate, dar la query se fac 2*sqrt(N) in loc de 3*sqrt(N) operatii, in cel mai rau caz. O solutie se gaseste aici(nu am implementat neaparat frumos).