infoarena

Aici puteti discuta despre problema Cautare binara (http://infoarena.ro/problema/cautbin).

in enunt se cere afisarea numarului cel mai mic mai mare sau egal si cel mai mare mai mic sau egal ca x. asta inseamna ca pentru sirul 5 9 12 12 12 17 23 si x=12 se pot afisa oricare dintre pozitiile 3, 4, 5 pentru ca 12 se afla pe toate acele pozitii, adica 12=12. care pozitie trebuie afisata?

Din ce am inteles eu, si ce am iplementat de 100 de puncte, in primul caz cand trebuie afisat cel mai mic numar mai mare sau egal cu x, rezultatul e 3, iar in cazul cu cel mai mare numar mai mic sau egal, rezultatul e 5.

da, am inteles enuntul si mai sus am dat un exemplu de la mine pentru ca intr-un sir crescator o valoare poate sa fie de mai multe ori.
in testele 5 si 7 o valoare apare de doua ori, programul meu afisand pozitia mai mare pentru ultimul caz al problemei, desi teoretic ambele pozitii sunt corecte (enunt: mai mic sau egal/mai mare sau egal)

Referitor la exemplul tau am raspuns.
Pentru cel mai mic numar mai mare sau egal cu x trebuie afisata pozitia cea mai mica, iar pentru cel mai mare numar mai mare sau egal cu x trebuie pozitia cea mai mare.

La 2 din teste imi iese din timp cu cateva milisecunde... o data la 8 si 10, alta data la 9 si 10:
http://infoarena.ro/job_detail/269188
http://infoarena.ro/job_detail/269185
Cum mai poate fi optimizat?

P.S. Lucrez in pascal.

[Later edit]
Am incercat si cu 3 functii distincte, pt fiecare tip de intrebare. Acum imi iese din timp doar cate un test: 8 sau 10.
http://infoarena.ro/job_detail/269245
http://infoarena.ro/job_detail/269211
Poate ca daca mai incerc sa le evaluez, le prind o data pe toate in timp  ](*,)
Este vreo sursa in pascal cu 100 de pct?

[editat de moderator] nu posta consecutiv. Editeaza-ti ultimul post.

evaluatorul iti opreste programul automat in momentul in care a depasit timpul de executie. Deci desi tie iti arata ca programul tau a depasit timpul de executie cu cateva milisecunde, de fapt acela e timpul la care a fost oprit, nu se stie cat ar mai fi durat pana programul tau s-ar fi terminat.

Programul tau intra in 360 de milisecunde pe testul maxim. Incearca sa parsezi citirea, avand in vedere ca o sursa in c intra in 210 milisecunde. In rest sursa imi pare ok ca complexitate :).

To admins: Se poate mari limita de timp la 0.35? Avand in vedere ca o sursa cu brut depaseste acest timp, scopul arhivei educationale nefiind acela de a parsa citirea.

Da, insa uneori intra in timp, alteori nu. De asta tind sa cred ca nu depaseste cu mult.


Mi se pare o idee buna.  :ok:

Ideea e ca depaseste cu aproximativ 60 de ms, Am trimis programul tau dupa ce am modificat limita de timp la 0.5 si iti intra in 0.36 :). Dupaia desigur am facut-o la loc 0.3. Daca nu ma crezi te poti uita pe ultima sursa trimisa de mine la cautare binara :).

Dar timpul variaza destul de tare. Au fost evaluari la care mi-a intrat si testul maxim (http://infoarena.ro/job_detail/269245).
Am parsat cautarea (pentru prima data; sper ca am facut ce trebuia), si acum iese din timp la toate testele dinultima grupa.

Din ce am vazut eu, tu parsezi cu buffer de 255 de caractere, cat e string-ul normal. Din ce imi amintesc din pascal, poti declara si string de 1 milion, cat poate fi o linie din fisier. E mai rapid sa citesti tot randul decat bucati din el.

Nu sunt sigur, dar parca mergea ceva de genul:

Nu este in free pascal string cu mai mult de 255 caractere.

Ba da, este. Se numeste ansistring :).

Merge cu ansistring, dar acum am probleme cu limita de memorie.  :)

L.E. Poate ca ii totusi buna ideea cu ridicarea limitei de timp.  :wink:

De ce nu incerci sa citesti intr-un array de char?

De ce ar fi citirea caracter cu caracter mai rapida decat citirea cu numere?

Toate problemele din arhiva educationala vor fi revizuite in timp. Daca vom considera necesar in momentul revizuirii, vom modifica limita de timp.

Nu neaparat citirea char cu char, ci citirea in "bucati" mai mari decat e un int/long. In general bucati de lungime putere a lui 2.

Dar un array de char nu poate fi citit decat caracter cu caracter, asta inseamna "bucati" mai mici decat un numar intreg.

Ba poti citi, cu blockread de exemplu: citeste aici (http://coleweb.dc.fi.udc.es/docencia/edi/freepascal/doc/ref/node17.html#SECTION04138000000000000000). Cineva care stie pascal mai bine ca mine sa ma corecteze/completeze va rog :)

Trec pe c++ [-(

Pana la urma cum se acorda punctaj pe urmatoarele 2 cerinte?

1 x - pozitia pe care se afla elementul cel mai mare mai mic sau egal cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
2 x - pozitia pe care se afla elementul cel mai mic mai mare sau egal cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x

Din enunt nu se intelege ca trebuie cea mai mare pozitie posibila(1) sau cea mai mica pozitie posibila(2)... daca se iau in considerare doar astea doua nu e corect..

Pentru operatia de tip 1, elementul cel mai mare mai mic decat x, in caz ca sunt mai multe egale (desi nu cred), iei pozitia cea mai mare. La 2 invers, pozitia cea mai mica pe care apare.

Nu crezi? :)

verifica sursa jobului
http://infoarena.ro/job_detail/280859 (http://infoarena.ro/job_detail/280859)

Chiar cred ca ar fi necesara o modificare in enunt(sau in evaluator).

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.

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

Am pus.

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.

De ce este sursa oficiala gresita ? Mie imi pare ok, daca la  asta (http://infoarena.ro//job_detail/181397?action=view-source) te referi. Si legat de teste, o sa incerc sa ma ocup de ele saptamana asta.

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.

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

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

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 ?

  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:
  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:
  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  (http://infoarena.ro/job_detail/392400) 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.

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

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.

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

Sursă în Free Pascal cu punctaj maxim aici (http://infoarena.ro/job_detail/392400).

ce are serverul? :angry:
la toti apare in asteptare

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!

Aici (http://infoarena.ro/job_detail/601101) 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.

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

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

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.

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

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.

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

Articolul de pe topcoder se gaseste aici: https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/.
Link-ul de mai sus nu mai functioneaza

Niste observatii legate de problema aceasta (pentru cine folosteste C++):
- este indicat sa folositi printf in loc de cout
- vector<int> se comporta mai incet decat int v[nr_aici]
Eu aveam prima data cout si vector si primeam Time Limit Exceeded. Cand am modificat cum am scris mai mult am primit maxim.
Acestea sunt niste observatii. Poate cineva sa confirme sau sa infirme acestea?

Nu stiu de ce imi da doar 40 puncte pe sursa si pe teste imi apare o chestie ciudata : Wall time limit exceded
sursa : http://www.infoarena.ro/job_detail/1995650?action=view-source

As fi recunoscator sa ma ajutati !


Multumesc  :D

nUSH DC DRQ IMI DA 0 PUNCTE DA LA TOATE TESTELE CARE LE-AM LUAT DE PE ATASAMENTE IMI DA CORECT :angry: :angry: :angry: :angry: :angry: