Pagini: 1 [2] 3   În jos
  Imprimă  
Ajutor Subiect: 018 Cautare binara  (Citit de 42659 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
razyelx
Client obisnuit
**

Karma: 0
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #25 : Martie 25, 2009, 17:12:00 »

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.
Memorat
mathboy
Moderatori infoarena
Nu mai tace
*****

Karma: 150
Deconectat Deconectat

Mesaje: 259



Vezi Profilul
« Răspunde #26 : Mai 24, 2009, 20:50:37 »

Ar merge adaugata si problema http://infoarena.ro/problema/br la Probleme Suplimentare  Ok.
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #27 : Mai 25, 2009, 12:19:56 »

Am pus.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #28 : Iulie 19, 2009, 12:23:21 »

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.

« Ultima modificare: Iulie 19, 2009, 17:22:27 de către Andrei Grigorean » Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #29 : Iulie 19, 2009, 15:54:20 »

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.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #30 : Iulie 19, 2009, 17:21:32 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #31 : August 14, 2009, 17:50:57 »

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 Smile ).
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #32 : August 14, 2009, 17:56:18 »

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

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #33 : August 14, 2009, 19:15:45 »

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  Think
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #34 : August 14, 2009, 19:28:15 »

Cum ai verificat ca se incadreaza in memorie?
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #35 : August 14, 2009, 20:02:21 »

Citat
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 ?
Memorat
mimarcel
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 10



Vezi Profilul
« Răspunde #36 : Februarie 07, 2010, 14:58:30 »

  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.
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #37 : Februarie 10, 2010, 17:52:07 »

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.
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #38 : Februarie 10, 2010, 19:16:40 »

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.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #39 : Octombrie 18, 2010, 23:09:40 »

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


Karma: 0
Deconectat Deconectat

Mesaje: 10



Vezi Profilul
« Răspunde #40 : Octombrie 18, 2010, 23:33:49 »

Sursă în Free Pascal cu punctaj maxim aici.
Memorat
valentin.harsan
Strain
*

Karma: 33
Deconectat Deconectat

Mesaje: 41



Vezi Profilul
« Răspunde #41 : Ianuarie 22, 2011, 11:56:17 »

ce are serverul? Angry
la toti apare in asteptare
Memorat
mavro
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #42 : Iulie 04, 2011, 19:58:13 »

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!
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #43 : Iulie 04, 2011, 21:54:00 »

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.
Memorat
Bugiros
Strain


Karma: 5
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #44 : Ianuarie 21, 2012, 12:26:30 »

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.  Very Happy
Memorat
Tux2Nicolae
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #45 : Ianuarie 23, 2012, 22:21:42 »

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!  Smile
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #46 : Ianuarie 23, 2012, 22:35:03 »

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.
Memorat
cosmyo
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 14



Vezi Profilul
« Răspunde #47 : Ianuarie 26, 2012, 04:21:31 »

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).
Memorat
alexalbu95
Client obisnuit
**

Karma: -10
Deconectat Deconectat

Mesaje: 57



Vezi Profilul
« Răspunde #48 : Martie 05, 2012, 10:19:03 »

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.
Memorat
Robytzza
De-al casei
***

Karma: -49
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #49 : Martie 05, 2012, 16:51:37 »

uite aici teste http://infoarena.ro/problema/cautbin?action=attach-list
Memorat
Pagini: 1 [2] 3   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines