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, 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.in | hashuri.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(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 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). Alt 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, daca oricare doua chei au valorile asociate prin funtia H diferite (altfel spus, daca functia H este injectiva) atunci este suficient... Daca H nu este injectiva, pot aparea coliziuni, adica sa existe doua valori x1 si x2 diferite astfel incat H(x1) = H(x2). In acest caz, Aceste coliziuni se pot trata cu ajutorul listelor liniare simplu inlantuite.
Sursa de 100 de puncte aici.
Aplicaţii
Prezentam mai jos probleme care pot fi rezolvate eficient cu ajutorul hashurilor:
????
