Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | hashuri.in, hashuri.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.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, in caz contrar returnand 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.in | hashuri.out |
|---|---|
| 7 1 3 1 20 2 7 3 4 3 20 2 20 3 20 | 0 1 0 |
Explicaţie
...
Indicaţii de rezolvare
O abordare directa a problemei are complexitatea O(N2) si trebuie sa obtina 20 de puncte. Sursa pe aceasta idee se gaseste aici.
Problema poate fi rezolvata si in complexitate O(Nlog2N) 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 50 de puncte.
Pentru a rezolva eficient in practica aceasta problema putem folosi tabele hash (cunoscute in literatura de specialitate si ca tabele de dispersie). Desi teoretic complexitatea acestei structuri de date ramane O(N) pe cazul cel mai defavorabil, in practica operatiile uzuale precum cautarea, adaugarea si stergerea se realizeaza foarte rapid. Ideea din spatele hashurilor este de a asocia fiecarui element dintr-o multime oarecare o valoare unica, de obicei un numar natural obtinut printr-o functie de hash H. 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 . Astfel, daca oricare doua chei au valorile asociate prin funtia H diferite (altfel spus, daca functia H este injectiva) atunci este suficient... coliziuni
Aplicaţii
Prezentam mai jos probleme care pot fi rezolvate eficient cu ajutorul hashurilor:
????
