Fişierul intrare/ieşire:hashuri.in, hashuri.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test1.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Hashuri

Fie o multime de numere naturale initial vida. Asupra acestei multimi se efectueaza operatii de urmatoarele tipuri:

  • operatia de tipul 1: se adauga elementul x la multime (unde x este un parametru al operatiei). Daca x este deja in multime, atunci aceasta ramane neschimbata.
  • operatia de tipul 2: se sterge elementul x, daca acesta este deja in multime. In caz contrar, multimea ramane neschimbata.
  • operatia de tipul 3: returneaza 1 daca si numai daca x este in multime, iar in caz contrar returneaza 0.

Date de intrare

Fişierul de intrare hashuri.in contine pe prima linie numarul N de operatii efectuate. Fiecare din urmatoarele N linii contine o pereche de numere naturale (op x), unde op este numarul operatiei care se efectueaza (de la 1 la 3), iar x este parametrul operatiei.

Date de ieşire

Fişierul de ieşire hashuri.out va contine un numar de linii egal cu numarul de operatii de tipul 3 din fisierul de intrare. Pe fiecare linie se va afla raspunsul returnat de operatia corespunzatoare.

Restricţii

  • 3 ≤ N ≤ 1.000.000
  • Fiecare operatie are un parametru numar natural din intervalul [1, 2.000.000.000]

Exemplu

hashuri.inhashuri.out
7
1 3
1 20
2 7
3 4
3 20
2 20
3 20
0
1
0

Indicaţii de rezolvare

O abordare directa a problemei are complexitatea O(N2) si trebuie sa obtina 30 de puncte. Sursa pe aceasta idee se gaseste aici.

Problema poate fi rezolvata si in complexitate O(NlogN) folosind arbori echilibrati de cautare, precum AVL-uri, arbori rosu-negru sau treapuri. Aceste structuri de date au dezavantajul ca sunt dificil de implementat, fapt care le face inabordabile in timp de concurs. Programatorii C++ pot totusi evita implementarea manuala a acestor structuri, putand folosi ca alternativa container-ul set din STL. Acest container simuleaza comportamentul unui arbore echilibrat, efectuand toate cele trei operatii mentionate in enunt in timp logaritmic. O sursa pe aceasta idee se gaseste aici si obtine 70 de puncte.

Pentru a rezolva eficient in practica problema de fata putem folosi tabele hash (cunoscute in literatura de specialitate si ca tabele de dispersie). Un articol referitor la acelasi subiect se gaseste si pe wikipedia. Desi teoretic complexitatea acestei structuri de date ramane O(N) pe cazul cel mai defavorabil, in practica operatiile uzuale precum cautarea, adaugarea sau stergerea se realizeaza foarte rapid. Ideea din spatele hashurilor este de a asocia fiecarui element dintr-o multime data o valoare unica, obtinuta printr-o functie de hash H. Valorile functiei H sunt de obicei numere naturale. Elementele multimii (care pot fi numere naturale, siruri de caractere, matrici, etc.) se vor numi chei. Avantajul asocierilor de tipul cheie-valoare este dat de usurinta cu care putem manipula valorile, in special in cazul in care acestea au dimensiuni mici. Astfel, vom retine o a doua multime (pe care o vom nota cu M), care sa contina toate valorile de forma H(i), unde i apartine multimii asupra careia se efectueaza operatiile. Atunci cand adaugam un element i la prima multime trebuie de fapt sa adaugam H(i) la multimea M, iar cand stergem un element i sa stergem H(i). Interogarea unui element i se reduce la a afla daca elementul H(i) se gaseste in M. Aceasta abordare functioneaza cand functia H este injectiva, adica din oricare doua chei distincte se obtin valori distincte. Cel mai simplu exemplu este sa alegem H(x) = x si sa retinem multimea M ca un vector boolean, in care pe pozitia i apare true daca si numai daca i este in multime.

Totusi, pentru aceasta problema nu putem construi o functie H injectiva, deoarece in acest caz codomeniul ar contine cel putin 2 miliarde de elemente iar memoria este limitata la 16 MB. In acest caz putem considera o functie H neinjectiva, insa trebuie sa tratam aparitia coliziunilor, adica acele cazuri in care doua chei distincte furnizeaza aceeasi valoare. Fie functia de hash H(x) = x modulo P, unde P este un numar natural, ales de obicei ca fiind un numar prim. Vom retine P liste simplu inlantuite, indexate de la 0 la P-1, unde lista i va retine toate acele chei x din multime care au H(x) = i, sau, altfel spus, toate numerele din multime care dau restul i la impartirea cu P. Atunci cand efectuam o operatie de tipul 1, vom adauga elementul x la lista corespunzatoare din cele P (si anume la lista H(x)), iar pentru o operatie de tipul 2 vom sterge elementul x din lista H(x). Operatia 3 se trateaza similar. Se observa ca daca P este comparabil cu N, distributia cheilor se face in practica cat mai uniform, adica cele P liste au lungime mica iar toate cele trei operatii executa putine calcule, programul devenind deci foarte rapid. Sursa de 100 de puncte se gaseste aici.

Programatorii C++ mai au la indemana in STL container-ul map, care creeaza asocieri intre elemente ce pot fi si de tipuri diferite. Din pacate operatiile efectuate de acest container au tot complexitate O(logN), dar este foarte usor de manevrat; o sursa demonstrativa se gaseste aici.

Aplicaţii

O aplicatie utila si interesanta este algoritmul Rabin-Karp pentru potrivirea sirurilor. Alte probleme ce pot fi rezolvate eficient cu ajutorul hashurilor sunt:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content