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

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.

h3. Aplicaţii

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

Prezentam mai jos probleme care pot fi rezolvate eficient cu ajutorul hash-urilor:

????