* _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$.

* _operatia de tipul 3_: returneaza $1$ daca si numai daca $x$ este in multime, in caz contrar returnand $0$.

h2. Date de intrare

0
|

h2. Indicaţii de rezolvare

h3. Explicaţie

O abordare directa a problemei are complexitatea $O(N^2^)$ si trebuie sa obtina $30$ de puncte. Sursa pe aceasta idee se gaseste 'aici':job_detail/236704?action=view-source.
Problema poate fi rezolvata si in complexitate {$O(Nlog{~2~}N)$} 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":http://www.sgi.com/tech/stl/set.html 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':job_detail/236705?action=view-source si obtine $70$ de puncte.
Pentru a rezolva eficient _in practica_ problema de fata putem folosi 'tabele hash':tabele-hash-scurta-prezentare (cunoscute in literatura de specialitate si ca {_tabele de dispersie_}). Alt articol referitor la acelasi subiect se gaseste si pe "wikipedia":http://en.wikipedia.org/wiki/Hash_table. 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.

h3. Indicaţii de rezolvare

Sursa de $100$ de puncte 'aici':job_detail/236765?action=view-source.

O abordare directa a problemei are complexitatea $O(N^2^)$ si trebuie sa obtina $20$ de puncte. Sursa pe aceasta idee se gaseste 'aici':.
Problema poate fi rezolvata si in complexitate {$O(Nlog{~2~}N)$} 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":http://www.sgi.com/tech/stl/set.html 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':http://en.wikipedia.org/wiki/Hash_table (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

h2. Aplicaţii

h3. Aplicaţii

Prezentam mai jos probleme care pot fi rezolvate eficient cu ajutorul hashurilor: