016 Range minimum query

[•DITzoneC]

Aici puteti discuta despre problema Range Minimum Query.

[•rethos]

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.
http://infoarena.ro/job_detail/156926

[•wefgef]

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

[•devilkind]

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

[•Cosmin]

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

[•rethos]

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

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

[•astronomy]

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

[•cretu]

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

[•wefgef]

Concurs (cere sa afli LCA) si Plantatie.

[•cretu]

mersi mult

[•fireatmyself]

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.

[•filipb]

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.

[•vlad_D]

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)

[•toni2007]

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:

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

[•florin_marius90]

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

[•sima_cotizo]

Instaleaza-ti freepascal.

[•florin_marius90]

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

[•sima_cotizo]

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;

[•florin_marius90]

aham ms mult 

[•mlazari]

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? 

[•sigrid]

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?

[•wefgef]

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 .

[•sigrid]

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

[•sima_cotizo]

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

[•bogdan2412]

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.