infoarena

Aici puteti discuta despre problema Hashuri (http://infoarena.ro/problema/hashuri) din Arhiva educationala (http://infoarena.ro/arhiva-educationala).

As avea doua intrebari in legatura cu containerul 'Map' din STL.
1) Ce reprezinta cei doi parametri de la declarare ( adica de ce este declarat <int, int>)?
2) Este eficient pentru hashuri?

Multzam anticipat :D

1. Aici folosesti map <int, int> pentru ca vrei sa creezi ascoieri intre doua elemente de tip int (elementul din multime si indicele de ordine). Avantajul principal este ca poti face si map-uri mai complicate folosind stringuri, vectori din STL sau altele (pentru care sa construiesti o functie hash este mai incomod).

2. Nu este destul de eficient pentru a obtine 100 de puncte la aceasta problema, dar de multe ori e de ajuns.

am o nelamurire...in functia erase am chestia asta: daca trimit sursa cu ea imi ia TLE pe un test (nu inteleg dc ca doar e O(1)), daca trimit fara (ceea ce nu este corect intra foarte bine in timp pe testul acela). ma poate ajuta cineva? :winner1:

inainte aveam chestia asta: mi-am dat seama ca e acelasi lucru in if si else si am pus numa ce e mai sus. inainte intra foarte bine in timp....

Aici la hashuri mai intra super frumos si rapid in timp si problema banana http://infoarena.ro/problema/banana

de pe infoarena eqs,oite si take5
si de pe sgu http://acm.sgu.ru/problem.php?contest=0&problem=174

aia de pe sgu a fost bagata la disjoint data set.

As avea si eu o intrebare in legatura cu memoria heap. Stiu ca pe Windows se puteau aloca maxim 64 Kb. Dar cat este maximul in Linux?
Problema mea dadea Killed by signal 11(SIGSEGV) in functie de dimensiunea pe care o alegeam pentru vectorul alocat dinamic (acel modul pentru care calculam n%modul). Cand am dat un numar prim de valoare mai mica problema a luat 100p, desi din cate stiu eu alocam acelasi numar de valori(pt fiecare din valorile inserate alocam spatiu in memorie, indiferent in care lista simplu inlantuita era repartizata).
Puteti sa imi explicati si mie, va rog?  :D

Nu mi se pare ok sa folosesti map pentru hashing. Mai rapid si eficient este hash_set( hash_multiset ), respectiv hash_map ( hash_multimap ). Ambele obtinand 100pct.
http://infoarena.ro/job_detail/390327?action=view-source (hash_set)
http://infoarena.ro/job_detail/390331?action=view-source (hash_map)

Pe gcc 4.3 nu compileaza daca incluzi <hash_set.h>, trebuie inclus <hash_set>.

@echipa-infoarena: Ce ar fi daca am schimba comanda de compilare astfel incat sa includa  -std=gnu++0x? Astfel ar putea fi folosite chestii din noul standard, cum ar fi <unordered_set>.

Care functie de hash e cea mai buna pentru key numere reale ?

Eu folosesc h(x) = [ m * {y*x} ], unde 0<y<1, si m un numar natural. Eu iau m=666013 si y=0.5.
[a] - partea intreaga
{a} - partea fractionara

PS : hash_map si hash_set nu merg cu key double sau float.  :sad:

Acest articol (http://infoarena.ro/tabele-hash-scurta-prezentare) recomanda sa folosesti y = 0.6180339887.
In ce sens nu merge sa folosesti hash_map si hash_set cu chei reale? Singura problema ar fi ca nu au o functie de hash definita pentru numere reale, dar o data ce le dai functia pe care ai scris-o, ar trebui sa mearga.

De ce in solutia oficiala pentru numarul mod se foloseste  666013 si nu un numar mai mare? Si cum e mai eficient? Sa implementez hashuri cu <list> sau cu <vector>? Multumesc

Cu vector. Cu list e si mai incep si consuma si mult mai multa memorie

Poate cineva sa-mi spuna de ce nu iau nici un punct pe sursa mea?
Va multumesc

Ai șanse mici să urmărească cineva sursa, e prea lungă. Mai bine descarcă-ți testele și vezi unde crapă. Dacă nu sunt suficient de mici, generează-ți tu câteva, sigur găsești repede unul.

Nu credeam ca se pot descarca testele.
O sa ma uit mai atent, multumesc.

Eu nu primesc nici un punct...
Am descarcat mai toate testele, si am vazut ca obtin raspunsuri corecte.
Cel putin la primele trei teste(celelalte sunt huge, pentru a putea fi verificate manual), am obtinut raspuns corect,
iar evaluatorul imi da 0...

Atunci când îți merge local dar iei 0 pe infoarena în 90% din cazuri chiar faci ceva greșit, dar probabil comportamentul e nedefinit. Uită-te după out-of-bound access și alte chestii de genul ăsta. Ai și un warning destul de urât.

Multumesc pentru raspuns
Sa vedem ce rezolv...

Multumesc pentru raspuns
Sa vedem ce rezolv...
[EDIT]: Chiar nu inteleg ce gresesc. Am verificat pentru out-of-bonds access, si nu pare sa am.
Folosesc aceleasi "setari" la compilarea sursei, ca si evaluatorul infoarena.

Fii atent la cum faci citirea. Trebuie sa specifici un mod atunci când foloseÈ™ti fstream.open(). Tie nu iti citeÈ™te nimic È™i de asta iei incorect. Uita-te È™i pe timpii foarte mici (4 ms)  :). Am luat 100 cu sursa ta modificând deschiderea fiÈ™ierului în ifstream fin("hashuri.in").

solutie in C++ cu map si P containere set. Smooth! :ok:

Cea mai usoara solutie fara map si set: solutie cu std::vector. Am scos cu tot cu parsare 300ms pe cel mai rau test :)

https://infoarena.ro/job_detail/2203975

Testele descarcate functioneaza in Visual Studio cu outputul corect. Compilatorul de pe infoarena da incorect la toate testele.