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.

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

h3. Aplicaţii

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

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

????