infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva educationala => Subiect creat de: Adrian Diaconu din Martie 10, 2008, 22:04:05

Titlul: 016 Range minimum query
Scris de: Adrian Diaconu din Martie 10, 2008, 22:04:05

Aici puteti discuta despre problema Range Minimum Query (http://infoarena.ro/problema/rmq).

Titlul: Răspuns: 016 Range minimum query
Scris de: Paicu Alexandru din Martie 12, 2008, 19:55:58

este posibil sa fie o problema cu evaluatorul? pe aceeasi sursa am obtinut 3 rezultate diferite
http://infoarena.ro/job_detail/156915
http://infoarena.ro/job_detail/156891
http://infoarena.ro/job_detail/156909
sursa este identica in toate trei cazurile, se vede
LE: am mai trimis o data aceeasi sursa si am luat 100. e oleak ciudat. :D
http://infoarena.ro/job_detail/156926

Titlul: Răspuns: 016 Range minimum query
Scris de: Andrei Grigorean din Martie 12, 2008, 20:01:14

Nu e o problema cu evalul, insa daca ai o sursa care merge la limita se poate intampla sa iei punctaje diferite.

Titlul: Răspuns: 016 Range minimum query
Scris de: Savin Tiberiu din Martie 12, 2008, 23:05:48

@ alex paicu: M-am uitat putin pe sursa ta ptr ca stiu ca limita de timp e destul de lejera, si mi-a sarit in ochi din prima ca tii matricea a[Nm][LogNm], incearca sa inversezi indici ptr ca astfel spargi limita de cache foarte mult si costa timp.

Titlul: Răspuns: 016 Range minimum query
Scris de: Cosmin Negruseri din Martie 12, 2008, 23:56:52

Un articol foarte util ar merge despre explicatia modului cum functioneaza cacheul procesorului si cateva exemple de cod cu comparatii intre ele ca timp.

Titlul: Răspuns: 016 Range minimum query
Scris de: Paicu Alexandru din Martie 13, 2008, 13:02:31

Citat din mesajul lui: Savin Tiberiu din Martie 12, 2008, 23:05:48

ms asa iau 100 fara probleme. o sa tin minte asta

Titlul: Răspuns: 016 Range minimum query
Scris de: Airinei Adrian din Martie 22, 2008, 12:45:22

Da, evalul o sa fie oprit pana maine cand se face evaluarea pentru runda finala onsite.

Titlul: Răspuns: 016 Range minimum query
Scris de: Musina Rares din Aprilie 02, 2008, 17:35:46

imi puteti recomanda va rog si alte probleme care se rezolva cu rmq?

Titlul: Răspuns: 016 Range minimum query
Scris de: Andrei Grigorean din Aprilie 02, 2008, 18:18:07

Concurs (cere sa afli LCA) si Plantatie.

Titlul: Răspuns: 016 Range minimum query
Scris de: Musina Rares din Aprilie 02, 2008, 18:28:01

mersi mult :ok:

Titlul: Răspuns: 016 Range minimum query
Scris de: Bogdan-Alexandru Stoica din Aprilie 11, 2008, 08:43:43

s-ar fi putut parsa citirea si pusa limita de timp astfel incat sa iei 80-90 cu citire normala. cred ca ar fi fost un exercitiu ultil. :D

Titlul: Răspuns: 016 Range minimum query
Scris de: Filip Cristian Buruiana din Aprilie 11, 2008, 11:10:16

Era impotriva scopului arhivei educationale. La o problema de RMQ trebuie sa inveti sa faci RMQ, nu sa parsezi citirea. Pentru asta merge alta problema, desi e cam dificil sa faci teste datorita marimilor care pot aparea.

Titlul: Răspuns: 016 Range minimum query
Scris de: Vlad Dumitriu din Decembrie 10, 2008, 11:18:22

chiar imi place arhiva educationala.. ma ajuta sa revin in lumea codului.. ahah
utie faceam RMQ si nu imi ieasea o faza (luam tle). m-am uitat prin celelalte coduri.. si m-am prins de ce.. in modu asta e utila.. dar cand ma uitam p'acolo am vazut cineva trimises la fel ca sursa oficiala... :-' creca nu avea increde in autor :-'

care e faza cu cache-ul? (caut amu pe google sa vad)

Titlul: Răspuns: 016 Range minimum query
Scris de: Pripoae Teodor Anton din Martie 14, 2009, 20:22:31

Citat din mesajul lui: alexandru din Martie 14, 2009, 20:16:55

pentru datele de intrare exista mereu solutie :-?
Si pentru prima intrebare : Care este numarul minim intre [2,4] nu este 3,nu 4?

Tu ce parere ai? Poti sa nu ai solutie cand trebuie sa afli minimul pe intervalul [a, b]? Vezi mai bine iti stergi postul ca enervezi lumea si te faci si de ras. 80 % din posturile tale sunt off-topic, sau nu aduc nimic nou sau interesant discutiei.

Apropo, nu am reusit sa descifrez inca o propozitie cu dubla negatie:

Citat

Care este numarul minim intre [2,4] nu este 3,nu 4?

Titlul: Răspuns: 016 Range minimum query
Scris de: Florin Marius Popescu din Martie 21, 2009, 08:18:21

salut ! cum retin vectorul de elemente in pascal? ce artficiu pot sa fac , ca daca ii dau vetor cu 100000 de elemente zice ca depasc memoria.. :-k ms

Titlul: Răspuns: 016 Range minimum query
Scris de: Sima Cotizo din Martie 21, 2009, 11:19:37

Instaleaza-ti freepascal (http://freepascal.org).

Titlul: Răspuns: 016 Range minimum query
Scris de: Florin Marius Popescu din Martie 21, 2009, 12:46:11

pai lasa ca nu conteaza asta . treaba e ca nu se incadreaza in memoria alocata problemei.....

Titlul: Răspuns: 016 Range minimum query
Scris de: Sima Cotizo din Martie 21, 2009, 13:12:28

Ai dreptate. Raspunsesem din inertie dupa ce citisem alt post de-al tau.

M-am uitat pe sursa ta si declari memoria intr-adevar cam multa. Hai sa facem niste calcule:
1) Tu ai un vector de 100.000 de elemente de retinut => una dintre dimensiunile matricei ar trebui sa fie 100.000.
2) 2¹⁰=1024 => 2²⁰= aprox 1.000.000, deci log₂100.000<20 => a doua dimensiune a matricei e ok sa fie 20.

Poti retine deci vectorul v si matricea a de forma:

Cod:

var v:array[1..100000] of longint;
    a:array[1..20,1..100000] of longint;

Titlul: Răspuns: 016 Range minimum query
Scris de: Florin Marius Popescu din Martie 21, 2009, 13:19:11

aham ms mult :peacefingers:

Titlul: Răspuns: 016 Range minimum query
Scris de: Lazari Mihai din Aprilie 22, 2009, 17:40:29

Pot sa iau 100 de puncte cu o sursa Pascal? Eu iau 80 de puncte (TLE la ultimele 2 teste). M-am uitat prin sursele de pe monitor scrise in Pascal si punctajul maxim acumulat este 90. Deci, e posibil sa iau 100p. sau e neaparat sa o scriu in CPP? ???

Titlul: Răspuns: 016 Range minimum query
Scris de: Maria Stanciu din Aprilie 24, 2009, 11:41:25

Am vazut ca din ce in ce mai des se intreaba pe forum daca o sursa Pascal poate obtine punctaj maxim. Se poate ca atunci cand este adaugata o problema in arhiva educationala sa faceti doua surse una in C++ si cealalata in Pascal si sa lasati la indicatii link catre amandoua?

Titlul: Răspuns: 016 Range minimum query
Scris de: Andrei Grigorean din Aprilie 24, 2009, 15:26:31

Se poate, si probabil ca din anumite puncte de vedere este indicat.

Insa eu personal consider ca lumea ar trebui descurajata sa mai lucreze in pascal, din diverse motive. E timpul sa evoluam ;).

Titlul: Răspuns: 016 Range minimum query
Scris de: Maria Stanciu din Aprilie 24, 2009, 18:58:16

Eu iti dau dreptate, dar vad ca le-a intrat multora in cap ideea asta ca Pascalul "e de vina" pentru punctajul lor si atata timp cat se poate mi se pare normal sa fie descurajata si chiar contrazisa. Adica are si limbajul asta de programare defectele lui si trebuie blamat pentru ele. Ori, in cazul de fata, mi se pare ca se exagereaza cu ideologia "in Pascal nu se poate 100" :).

Titlul: Răspuns: 016 Range minimum query
Scris de: Sima Cotizo din Aprilie 24, 2009, 20:33:04

Citat din mesajul lui: Stanciu Maria din Aprilie 24, 2009, 18:58:16

Eu iti dau dreptate, dar vad ca le-a intrat multora in cap ideea asta ca Pascalul "e de vina" pentru punctajul lor

Daca cineva nu are determinarea sa scoata 100 cu cunostintele pe care le are sau pe care le poate acumula, atunci nu cred ca merita continuata discutia. E clar ca daca s-a luat 100, atunci poate lua oricine, e nevoie doar de determinare si nu poti blama limbajul.

Cum mare parte din cei care se ocupa de arhiva si de infoarena in general presupun ca nu au/nu vor sa aiba foarte multe tangente cu Pascalul, propun ca cei interesati sa anunte pe forum ca au o sursa de 100 pentru a putea fi introdusa de helperi in enuntul problemelor.

O alta solutie ar fi sa se largeasca putin constrangerile la timp acolo unde se poate, dar problema asta poate fi "fentata" cu rezolvari neoptime din cate tin minte. S-ar putea mentiona asta in text, daca este cazul, alaturi de ceva gen "fiti linistiti, in concurs este sigur ca limitele vor permite si pascalistilor o astfel de abordare daca este cea corecta :thumbup:".

Titlul: Răspuns: 016 Range minimum query
Scris de: Bogdan-Cristian Tataroiu din Aprilie 24, 2009, 20:38:20

In general cand se intreba daca se putea lua 100 de puncte in pascal, exista deja o sursa sau mai multe care luasera 100. La problema asta nu e niciuna: http://infoarena.ro/monitor?task=rmq&compiler=fpc&score_begin=100 . E posibil totusi sa fie limita prea stransa :) . La o problema din arhiva educationala nu cred ca trebuie sa ne facem asa mari griji daca cineva ia 100 cu solutii ineficiente, deci nu cred ca trebuie limitele puse stranse. E treaba fiecaruia daca vor sa implementeze solutii ineficiente si sa fenteze problema in loc sa invete rezolvarea corecta.

Titlul: Răspuns: 016 Range minimum query
Scris de: Belgun Dimitri Adrian din Aprilie 24, 2009, 21:40:29

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.

Titlul: Răspuns: 016 Range minimum query
Scris de: Lazari Mihai din Aprilie 28, 2009, 19:26:14

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++ :)

Titlul: Răspuns: 016 Range minimum query
Scris de: Cosmin Negruseri din Aprilie 29, 2009, 02:50:55

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Lazari Mihai din Aprilie 29, 2009, 11:35:21

Da, cu SetTextBuf si sursa mea in Pascal ia 100 \:D/ Merci mult!

Titlul: Răspuns: 016 Range minimum query
Scris de: Belgun Dimitri Adrian din Mai 05, 2009, 20:09:14

yey, chiar merge :D

Cu ocazia asta rezolvai si Deque-ul.

Multumesc!

Titlul: Răspuns: 016 Range minimum query
Scris de: George Popoiu din Ianuarie 10, 2010, 11:31:50

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Dragos din Ianuarie 30, 2010, 13:53:38

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Dragos-Alin Rotaru din Ianuarie 30, 2010, 14:06:41

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Dragos din Ianuarie 30, 2010, 14:22:15

Citat din mesajul lui: Rotaru Dragos Alin din Ianuarie 30, 2010, 14:06:41

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?

Titlul: Răspuns: 016 Range minimum query
Scris de: Dragos-Alin Rotaru din Ianuarie 30, 2010, 14:32:09

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Dragos din Ianuarie 30, 2010, 15:13:26

Citat din mesajul lui: Rotaru Dragos Alin din Ianuarie 30, 2010, 14:32:09

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Tirca Bogdan din Ianuarie 31, 2010, 10:34:29

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.

Titlul: Răspuns: 016 Range minimum query
Scris de: Dragos din Ianuarie 31, 2010, 14:12:18

Citat din mesajul lui: Tarca Bogdan din Ianuarie 31, 2010, 10:34:29

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? :-s

Titlul: Răspuns: 016 Range minimum query
Scris de: Tirca Bogdan din Ianuarie 31, 2010, 16:25:43

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

Titlul: Răspuns: 016 Range minimum query
Scris de: irimias robert din Iulie 23, 2010, 15:50:13

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]

Titlul: Răspuns: 016 Range minimum query
Scris de: Dragos-Alin Rotaru din Iulie 23, 2010, 16:03:41

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Gabriel Bitis din Iulie 23, 2010, 16:05:13

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

Titlul: Răspuns: 016 Range minimum query
Scris de: irimias robert din Iulie 24, 2010, 12:12:23

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

Titlul: Răspuns: 016 Range minimum query
Scris de: livica din Februarie 24, 2011, 22:01:16

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 ?

Titlul: Răspuns: 016 Range minimum query
Scris de: livica din Februarie 25, 2011, 15:03:28

formula pentru rmq[ i ][j] am luat-o de aici: http://www.descarca-x.info/showthread.php?tid=568 (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!!!

Titlul: Răspuns: 016 Range minimum query
Scris de: Savin Tiberiu din Februarie 26, 2011, 01:28:44

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

Titlul: Răspuns: 016 Range minimum query
Scris de: livica din Februarie 26, 2011, 21:12:23

Extraordinar!
L-am inteles. :yahoo:
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

Titlul: Răspuns: 016 Range minimum query
Scris de: Andrei Alexandrescu din Februarie 27, 2011, 10:24:35

In sursa http://infoarena.ro/job_detail/542906?action=view-source (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?

Titlul: Răspuns: 016 Range minimum query
Scris de: Mircea Dima din Februarie 27, 2011, 13:46:41

Citat din mesajul lui: Andrei Alexandrescu din Februarie 27, 2011, 10:24:35

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

Titlul: Răspuns: 016 Range minimum query
Scris de: livica din Martie 06, 2011, 21:58:51

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?

Titlul: Răspuns: 016 Range minimum query
Scris de: Simoiu Robert din Martie 06, 2011, 22:07:11

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Mihai Calancea din Martie 06, 2011, 22:46:08

Citat din mesajul lui: livica din Martie 06, 2011, 21:58:51

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

Titlul: Răspuns: 016 Range minimum query
Scris de: livica din Martie 07, 2011, 10:05:58

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Dragos Oprica din Martie 07, 2011, 14:15:00

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.

Titlul: Răspuns: 016 Range minimum query
Scris de: livica din Martie 07, 2011, 23:06:16

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?

Titlul: Răspuns: 016 Range minimum query
Scris de: Paul-Dan Baltescu din Martie 08, 2011, 03:18:14

Da, ambele solutii au complexitate O(1).

Poti citi mai multe despre notatia "O" pentru complexitatea timp: aici (http://en.wikipedia.org/wiki/Big_O_notation) si aici (http://ro.wikipedia.org/wiki/Teoria_complexit%C4%83%C8%9Bii), 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.

Titlul: Răspuns: 016 Range minimum query
Scris de: livica din Martie 08, 2011, 11:02:40

OK.
Merci pentru informatii.

Titlul: Răspuns: 016 Range minimum query
Scris de: Vlad Tarniceru din Mai 10, 2011, 18:38:17

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

Titlul: Răspuns: 016 Range minimum query
Scris de: MciprianM din Mai 10, 2011, 18:41:19

Mie mi s-a parut foarte bun articolul (http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor) 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.

Titlul: Răspuns: 016 Range minimum query
Scris de: Alexandru-Iancu Caragicu din Iunie 04, 2011, 16:27:14

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.

Titlul: Răspuns: 016 Range minimum query
Scris de: Simoiu Robert din Iunie 04, 2011, 17:20:45

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.

Titlul: Răspuns: 016 Range minimum query
Scris de: Horia Cretescu din Noiembrie 18, 2011, 23:32:15

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Savin Tiberiu din Noiembrie 19, 2011, 01:31:50

Da se poate, doar ca e ceva mai complicat.

Titlul: Răspuns: 016 Range minimum query
Scris de: Andrei Dinu din Februarie 08, 2012, 14:57:35

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Dan Tudor din Iulie 10, 2013, 19:50:46

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.

Titlul: Răspuns: 016 Range minimum query
Scris de: George Marcus din Iulie 10, 2013, 20:08:48

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.

Titlul: Răspuns: 016 Range minimum query
Scris de: FMI Suditu Thomas din Martie 30, 2014, 15:24:51

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

Titlul: Răspuns: 016 Range minimum query
Scris de: George Marcus din Martie 30, 2014, 21:17:16

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Bogdan Pop din Aprilie 11, 2014, 14:29:37

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

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

Titlul: Răspuns: 016 Range minimum query
Scris de: Mihai Calancea din Aprilie 11, 2014, 14:49:58

Ai declarat invers matricea.

Titlul: Răspuns: 016 Range minimum query
Scris de: Bogdan Pop din Aprilie 11, 2014, 15:06:12

:aha: mersi mult

Titlul: Răspuns: 016 Range minimum query
Scris de: Alexandru Valeanu din Aprilie 11, 2014, 15:11:03

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.

Titlul: Răspuns: 016 Range minimum query
Scris de: Rusu Alexei din Iulie 28, 2014, 09:56:22

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

Titlul: Răspuns: 016 Range minimum query
Scris de: UAIC.VlasCatalin din Iulie 29, 2014, 22:45:05

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 :D

Titlul: Răspuns: 016 Range minimum query
Scris de: MciprianM din Mai 26, 2015, 11:30:30

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 (http://www.infoarena.ro/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 (http://www.infoarena.ro/job_detail/1442782?action=view-source)(nu am implementat neaparat frumos).

Titlul: Răspuns: 016 Range minimum query
Scris de: Sorin-Gabriel din Ianuarie 13, 2016, 19:00:20

Pe exemplu la iesire nu ar trebuii sa fie 3 pentru primul interval?

Titlul: Răspuns: 016 Range minimum query
Scris de: Vlad Rochian din Ianuarie 13, 2016, 20:02:14

Citat din mesajul lui: FMI Marica Sorin-Gabriel din Ianuarie 13, 2016, 19:00:20

Pe exemplu la iesire nu ar trebuii sa fie 3 pentru primul interval?

Vectorul este indexat de la 1 la N, deci in intervalul [2, 4] avem valorile 5, 6 și 4. Într-adevăr, ar trebui precizat acest lucru, dar se cam deduce din exemplu.

Titlul: Răspuns: 016 Range minimum query
Scris de: Arhire Andrei din Iulie 27, 2018, 16:41:29

https://www.infoarena.ro/job_detail/2225571 pacaleste testele :))

Titlul: Răspuns: 016 Range minimum query
Scris de: Arhire Andrei din Ianuarie 17, 2019, 21:33:09

O simpla indexare ia 100 . :peacefingers: