018 Cautare binara

[•razyelx]

Solutia de 100 de puncte oferita de voi nu pare sa fie corecta. Sa luam exemplul urmator:

5
12 12 12 12 12
1
0 12

Programul oferit de voi afiseaza 3, raspunsul corect fiind 5.

[•mathboy]

Ar merge adaugata si problema http://infoarena.ro/problema/br la Probleme Suplimentare  .

[•toni2007]

Am pus.

[•wefgef]

Am modificat enunţul şi exemplul astfel încât să nu mai existe ambiguităţi.

Prima sursă oficială este greşită. Ar trebui implementată altă sursă şi schimbat link-ul. În plus, ar trebui specificate şi funcţiile lower_bound(), upper_bound() din STL şi pus link către o sursă.

Deasemenea, testele sunt foarte proaste. Soluţii de complexitate O(N) pentru query-urile 2 şi 3 obţin 100 de puncte, precum şi unele surse care ar trebui să primească WA.

Sper că postul meu nu va rămâne fără ecou şi responsabilul de problemă va lua măsuri cât mai repede.

[•toni2007]

De ce este sursa oficiala gresita ? Mie imi pare ok, daca la asta te referi. Si legat de teste, o sa incerc sa ma ocup de ele saptamana asta.

[•wefgef]

Ma refer la prima sursă de 100 de puncte: http://infoarena.ro/job_detail/194421?action=view-source. E greşită deoarece pe exemplul de mai sus rezultatul furnizat este 3, nu 5.

[•alexandru92]

Doresc sa rezolv problema folosind containarul map, din stl. In mare parte am reusit, dar pe testele 6-10 iau Memory limit excited si nu inteleg de ce?
Sursa este aceasta: http://infoarena.ro/job_detail/340462?action=view-source
Folosesc un vector v in care retin  numarul, prima si ultima lui aparitie in sir ( pentru a face economie la memorie ).

[•wefgef]

Pai limita de memorie este de 1 Mega, iar tu aloci mai mult de atat.

[•alexandru92]

Pai limita de memorie este de 1 Mega, iar tu aloci mai mult de atat.

Am  generat un test cu N=100000 si  s-a incadrat in memorie ........hm 

[•devilkind]

Cum ai verificat ca se incadreaza in memorie?

[•alexandru92]

Cum ai verificat ca se incadreaza in memorie?

Scuze , debea cand ai pus tu intrebarea mi-am dat seama de greseala,  dupa ce memoram toate datele din fisier, dadeam sizeof(v); dar am uitat ca map este tinut printr-un arbore alocat dinamic, nu ?

[•mimarcel]

  In sfarsit am gasit care era problema pentru care nu obtineam punctaj maxim aici. Lucrez in Free Pascal si nu am gasit o sursa de 100 de puncte. Am observat insa ca algoritmul lucreaza [putin] mai repede daca functiile care le creez eu au si parametrii sau variabile locale, adica daca nu utilizeaza variabilele globale.
  Pentru a ma lamuri am folosit:

Cod:

uses sysutils;
const n=2000;
type vector=array[0..n]of longint;
const pasi=100000000;
var v:vector;
    i,m:longint;
    t1,t2:ttimestamp;

procedure abc1;
begin
m:=((1+i)div 2)mod n;
v[m]:=i;
end;

procedure abc2(a,b:longint);
begin
m:=((a+b)div 2)mod n;
v[m]:=b;
end;

procedure abc3(a,b:longint);
var m:longint;
begin
m:=((a+b)div 2)mod n;
v[m]:=b;
end;

procedure abc4(var v:vector;a,b:longint);
var m:longint;
begin
m:=((a+b)div 2)mod n;
v[m]:=b;
end;

procedure abc5(v:vector;a,b:longint);
var m:longint;
begin
m:=((a+b)div 2)mod n;
v[m]:=b;
end;

begin

for i:=1 to n do v[i]:=i;
t1:=datetimetotimestamp(now);
for i:=1 to pasi do abc1;
t2:=datetimetotimestamp(now);
writeln(t2.time-t1.time);

for i:=1 to n do v[i]:=i;
t1:=datetimetotimestamp(now);
for i:=1 to pasi do abc2(1,i);
t2:=datetimetotimestamp(now);
writeln(t2.time-t1.time);

for i:=1 to n do v[i]:=i;
t1:=datetimetotimestamp(now);
for i:=1 to pasi do abc3(1,i);
t2:=datetimetotimestamp(now);
writeln(t2.time-t1.time);

for i:=1 to n do v[i]:=i;
t1:=datetimetotimestamp(now);
for i:=1 to pasi do abc4(v,1,i);
t2:=datetimetotimestamp(now);
writeln(t2.time-t1.time);

for i:=1 to n do v[i]:=i;
t1:=datetimetotimestamp(now);
for i:=1 to pasi div 100 do abc5(v,1,i);
t2:=datetimetotimestamp(now);
writeln(t2.time-t1.time);
end.

  Adica am creeat un program cu 5 proceduri care fac de fapt acelasi lucru (in afara de procedura a 5-a). Prima procedura nu foloseste insa nici un parametru, numai variabilele globale, iar incepand cu a 2-a procedura am mai adaugat parametri si variabile locale. Pentru fiecare procedura am cronometrat timpul in care se executa aceasta de pasi ori. Astfel se observa mici diferente intre timpi.
  Unul dintre rezultatele care le-am obtinut acasa este:

Cod:

3813
3687
3500
3469
6484

  Daca procedurile au mai multi parametri sau au si variabile locale, atunci acestea se executa mai repede. Nu stiu daca este valabil pentru toate exemplele, dar se pare ca sursa aceasta pentru cautare binara se incadreaza in timp [la limita]. Se poate observa ca ultima procedura se executa totusi intr-un timp mult mult mai mare decat celelalte, acest lucru se datoreaza faptului ca vectorul v nu a fost transmis ca parametru de referinta.

[•SpiderMan]

Cu un program gresit pentru punctul 1 iau 100pct (sursa exact ca cea de care a spus Andrei, aici ). As dori daca s-ar putea modificarea testelor (pentru ca nu pot departaja corect ) , si reevaluarea surselor. Multumesc.

[•toni2007]

Am modificat sursele oficiale. Testele nu cred ca se pot schimba pt ca ar trebui reevaluate 1600 de surse, ti-am zis asta si pe privat.

[•PlayLikeNeverB4]

Mda, m-am chinuit si eu sa scot timpul in Pascal, dar degeaba Exista macar sursa de 100p pentru Pascal? Daca nu, sugerez si eu (la fel ca si altii) marirea limitei de timp.

[•mimarcel]

Sursă în Free Pascal cu punctaj maxim aici.

[•valentin.harsan]

ce are serverul?
la toti apare in asteptare

[•mavro]

Salut!

Am o problema la corectare. Imi pica doar testul 5 si singura diferenta este la linia 10343 unde mie nu-mi gaseste numarul in sir (el chiar nefiind), iar in testele atasate pe site este.
Cumva este strecurata vreo greseala in checker?

Va multumesc!

[•SpiderMan]

Aici e sursa ta de 100 puncte. Sa-ti spun si ce are gresit programul tau, referitor la operatia de tip 0 : tie nu-ti ia in considerare daca elementul se afla pe ultima pozitie, adica pe N. De exemplu, daca avem N = 5 sa zicem, si cautam elementul 10, care este pe ultima pozitie, 5, la un moment dat st si dr o sa fie 4 si 5, si cum respecta conditia dr - st == 1, si cum v[mij(4)] != 10 o sa returneze -1. De aceea, cand dai de cazul asta : mij + 1 == N, trebuie sa verifici daca nu cumva v[mij + 1], adica v[N] este egal cu numarul tau, adica intr-un cuvant, daca numarul tau este pe ultima pozitie. Am modificat putin codul, doar pentru CB0, sper sa intelegi, nu este riguros.

[•Bugiros]

Date de intrare

Pe prima linie a fisierului de intrare cautbin.in se afla numarul N reprezentand numarul de elemente alea sirului.

O mica greseala. 

[•Tux2Nicolae]

Interesant ! Obtin 60 de puncte doar si de 1 ora numi dau seama ceam gresit! Ma uit mai atent si observ ca limita de memorie e cam mica pe chind eu facusem recursiv problema ! Si cel mai interesant ca ari trebui sa anunte cel putin prin Limita de memorie depasita sau ceva de genu dar sa nu scrie la teste Incorect! 

[•klamathix]

Scrie ca e incorect fiindca e incorect. Iti si scrie cata memorie ai folosit, si e sub limita binisor. N-are cum sa te afecteze recursivitatea fiindca stiva nu depaseste niciodata log(2, n) apeluri, ceea ce e foarte putin.

[•cosmyo]

De obicei cautarea binara normala se poate busi foarte usor. Exista si un articol pe blog despre asta. Poti folosi functiile de cautare binara din STL sau faci cautarea binara a lui Patrascu care este mai "stabila"(nu are cazuri de considerat).

[•alexalbu95]

Cine are problema facuta de 100 pct cu implementarea STL-urilor: lower_bound si Upper_bound? Am facut-o dar imi da 0 pct si as vrea si eu sa vad ce gresesc. Eu incerc sa accesez problema de la indicatii, dar imi da mesaj de eroare.

[•Robytzza]

uite aici teste http://infoarena.ro/problema/cautbin?action=attach-list