...

h3. Indicaţii de rezolvare
 
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.
 
h3. Aplicaţii
 
Prezentam mai jos probleme care pot fi rezolvate eficient cu ajutorul hash-urilor:
 
????
 
* 'String':problema/string
* 'Count':problema/count
* 'Tetris2':problema/tetris2
 

== include(page="template/taskfooter" task_id="hashuri") ==