016 Range minimum query

[•belgun_adrian]

pe pascal se poate lua 90 http://infoarena.ro/monitor?task=rmq&compiler=fpc&score_begin=90

problema e din cauza citirii, care la pascal dureaza ceva.

am intalnit la cateva probleme acest blocaj si se putea rezolva cu o parsare.

daca citirea ar putea fi parsata s-ar rezolva, dar intrebarile sunt pe randuri diferite.

[•mlazari]

Eu cred ca e un pic cam mica limita de timp la aceasta problema. Eu am acumulat 100p. cu un program in C++, iar cu cel in Pascal-80p.(am implementat acelasi algoritm - cel dat la indicatii). Cred ca ar trebui pusa limita de timp astfel incat sa poti lua 100p. si cu un program in Pascal. Oricum voi trece si eu la C++ 

[•Cosmin]

Daca folositi Pascal si citirea e partea inceata, incercati sa folositi SetTextBuf (http://www.freepascal.org/docs-html/rtl/system/settextbuf.html). Si experimentati cu dimensiuni diferite.

Adrian, am trimis sursa ta cu modificarea de a folosi bufferul respectiv si am luat 100. Poti sa vezi aici sursa http://infoarena.ro/job_detail/308944?action=view-source

Diferenta e de doua linii:
Definirea bufferului: bufin : array[1..65000] of byte;
Si folosirea lui: settextbuf(f, bufin);

[•mlazari]

Da, cu SetTextBuf si sursa mea in Pascal ia 100     Merci mult!

[•belgun_adrian]

yey, chiar merge

Cu ocazia asta rezolvai si Deque-ul.

Multumesc!

[•popoiu.george]

Cred ca ar putea fi adaugata ca problema la care se foloseste de ideea de la RMQ : Stramosi

[•APOCALYPTO]

Nu vi se pare ca relatia de recurenta  de pe topcoder pentru calcularea lui M [ i ] [ j ] e gresita?

[•mathboy]

Nu e gresita. Ei considera ca numararea elementelor din vector incepe de la 0 nu de la 1.

[•APOCALYPTO]

Nu e gresita. Ei considera ca numararea elementelor din vector incepe de la 0 nu de la 1.

da dar atunci nu trebuia sa fie si i-1?

[•mathboy]

Vezi ca ai in articol si o sursa care se bazeaza pe recurenta prezentata. Testeaz-o si ai sa vezi ca nu are vreun motiv sa nu functioneze. 

[•APOCALYPTO]

Vezi ca ai in articol si o sursa care se bazeaza pe recurenta prezentata. Testeaz-o si ai sa vezi ca nu are vreun motiv sa nu functioneze.  

Sursa este buna dar

Cod:

  void process2(int M[MAXN][LOGMAXN], int A[MAXN], int N)
  {
      int i, j;
   
  //initialize M for the intervals with length 1
      for (i = 0; i < N; i++)
          M[i][0] = i;
  //compute values from smaller to bigger intervals
      for (j = 1; 1 << j <= N; j++)
          for (i = 0; i + (1 << j) - 1 < N; i++)
              if (A[M[ i ][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]])
                  M[ i ][j] = M[ i ][j - 1];
              else
                  M[ i ][j] =  M[i + (1 << (j - 1))][j - 1];
  } 

partea cu bold nu e aceaiasi cu relatia de recurenta(nu se mai scade 1) desi incepe de la 0  .

[•Bogdan_tmm]

Cod:

0 1 2 3 4 5 indici
0 1 2 3 4 5 elemente
lenght = 2^1
rmq [ i ] [2],i=1,i+2^1-1<6
0 1 i=0 ,dist=2
(1)  
      1 2 i=1 dist=2
      (2)    
            2 3 i=2 dist=2
            (3)       
                  3 4 i=3 dist=2
                  (4)
                         4 5 i=4 dist=2
                         (5)
lenght = 2^2 (defapt limita din dreapta  e i+2^2-1 , de aia apare -1)
rmq [ i ] [4] i=1,i+2^2-1<6
(0 1) (2 3) i=0 dist=4
  (1     3)   i=0,dist =2   sau i=0+2, dist=2
     (3)
               (1 2) (3 4) i=1 dist=4
                (2      4) i=1 dist=2 sau i=1+2,dist= 2
                    (4)
 etc :D
  

Foloseste tag-ul code cand postezi astfel de mesaje. Devin mai usor de inteles.

[•APOCALYPTO]

Cod:

0 1 2 3 4 5 indici
0 1 2 3 4 5 elemente
lenght = 2^1
rmq [ i ] [2],i=1,i+2^1-1<6
0 1 i=0 ,dist=2
(1)  
      1 2 i=1 dist=2
      (2)    
            2 3 i=2 dist=2
            (3)       
                  3 4 i=3 dist=2
                  (4)
                         4 5 i=4 dist=2
                         (5)
lenght = 2^2 (defapt limita din dreapta  e i+2^2-1 , de aia apare -1)
rmq [ i ] [4] i=1,i+2^2-1<6
(0 1) (2 3) i=0 dist=4
  (1     3)   i=0,dist =2   sau i=0+2, dist=2
     (3)
               (1 2) (3 4) i=1 dist=4
                (2      4) i=1 dist=2 sau i=1+2,dist= 2
                    (4)
 etc :D
  

Foloseste tag-ul code cand postezi astfel de mesaje. Devin mai usor de inteles.

Ce-i asta?

[•Bogdan_tmm]

Incercai sa-i explic cum se alege minimul si de ce apare -1 acolo

[•robigi]

as avea si eu o intrebare asa de nepriceput:

de ce imi merge mult mai rapid sursa daca folosesc:    int rmq[18][100001];    decat daca folosesc int rmq[100001][18];    ?

tot restul codului fiind la fel, desigur cu schimbarile de rigoare gen rmq[j][k] schimbat in rmq[k][j]          

[•mathboy]

Presupun ca e vorba de cache. Procesorul executa mai repede operatiile daca se itereaza pe mai putine linii , mai multe coloane ale matricei decat mai multe linii - mai putine coloane

[•gabitzish1]

http://infoarena.ro/12-ponturi-pentru-programatorii-CC
vezi ce zice la pontul #3

[•robigi]

multumesc, acum m-am prins ca era cache-ul de vina

[•livium]

care este relatia de recurenta pe linii?

cumva asta:

Cod:

rmq[i][j]=min(rmq[0][j],...,rmq[0][j+pow(2,i)-1])

?

daca asa e, atunci de ce mie imi da

rmq[3][j]=min(rmq[0][j],...mrmq[0][j+6]);

si nu j+7 la sfarsit ?

[•livium]

formula pentru rmq[ i ][j] am luat-o de aici: http://www.descarca-x.info/showthread.php?tid=568

dar repet: nu se verifica pentru i=3

Am I missing something?

Va rog raspundeti-mi!!!

[•devilkind]

Ai putea sa incerci sa deduci si singur formula, nu e chiar asa complicata, asta denota mai mult faptul ca nu ai inteles algoritmul. De altfel formula pe care o folosesti este ineficienta.

rmq[i ][j] = minimul pe sirul care incepe la pozitia j si are lungime 2^i
rmq[i ][j] = min(rmq[i - 1][j], rmq[i - 1][j + 2 ^ (i -1)])

[•livium]

Extraordinar!
L-am inteles. 
Ptiu... ce algoritm. Ma doare capul si acuma.
Cine a inventat algoritmul asta cred ca n-avea ce face!

Daca nu-mi dadeai explicatiile astea doua nu puteam sa-mi dau seama cum functioneaza .

Merci mult! Toate cele bune

[•AndrewTheGreat]

In sursa http://infoarena.ro/job_detail/542906?action=view-source declarasem gresit matircea in care imi construiesc RMQ-ul, si imi dadea incorect.

Acum intrebarea e de ce nu imi dadea KBS? Adica eu aveam int RMQ[nmax][20] (vezi linia 10) si clar accesam RMQ[ceva][altceva > 20 in majoritatea cazurilor].

Stiam ca daca accesez un element din afara matricii iau KBS 11, nu-i asa?

[•blasterz]

In sursa http://infoarena.ro/job_detail/542906?action=view-source declarasem gresit matircea in care imi construiesc RMQ-ul, si imi dadea incorect.

Acum intrebarea e de ce nu imi dadea KBS? Adica eu aveam int RMQ[nmax][20] (vezi linia 10) si clar accesam RMQ[ceva][altceva > 20 in majoritatea cazurilor].

Stiam ca daca accesez un element din afara matricii iau KBS 11, nu-i asa?

Daca ai int a[10][10] si accesezi a[3][11] defapt accesezi a[4][1] (liniile sunt stocate consecutiv in memorie)

[•livium]

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?