h2. Indicaţii de rezolvare
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.
Problema poate fi rezolvata si in complexitate {$O(NlogN)$} 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_}). Un 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, vom retine o a doua multime (pe care o vom nota cu {$M$}), care sa contina toate valorile de forma {$H(i)$}, unde $i$ apartine multimii asupra careia se efectueaza operatiile. Atunci cand adaugam un element $i$ la prima multime trebuie de fapt sa adaugam {$H(i)$} la multimea {$M$}, iar cand stergem un element $i$ sa stergem {$H(i)$}. Interogarea unui element $i$ se reduce la a afla daca elementul {$H(i)$} se gaseste in {$M$}. Aceasta abordare functioneaza cand functia $H$ este injectiva, adica din oricare doua chei distincte se obtin valori distincte. Cel mai simplu exemplu este sa alegem {$H(x) = x$} si sa retinem multimea $M$ ca un vector boolean, in care pe pozitia $i$ apare $true$ daca si numai daca $i$ este in multime.
Totusi, pentru aceasta problema nu putem construi o functie $H$ injectiva, deoarece in acest caz codomeniul ar contine cel putin $2$ miliarde de elemente iar memoria este limitata la {$16 MB$}. In acest caz putem considera o functie $H$ neinjectiva, insa trebuie sa tratam aparitia coliziunilor, adica acele cazuri in care doua chei distincte furnizeaza aceeasi valoare. Fie functia de hash {$H(x) = x modulo P$}, unde $P$ este un numar natural, ales de obicei ca fiind un numar prim. Vom retine $P$ liste simplu inlantuite, indexate de la $0$ la $P-1$, unde lista $i$ va retine toate acele chei $x$ din multime care au {$H(x) = i$}, sau, altfel spus, toate numerele din multime care dau restul $i$ la impartirea cu {$P$}. Atunci cand efectuam o operatie de tipul $1$, vom adauga elementul $x$ la lista corespunzatoare din cele $P$ (si anume la lista {$H(x)$}), iar pentru o operatie de tipul $2$ vom sterge elementul $x$ din lista {$H(x)$}. Operatia $3$ se trateaza similar. Se observa ca daca $P$ este comparabil cu $N$, distributia cheilor se face in practica cat mai uniform, adica cele $P$ liste au lungime mica iar toate cele trei operatii executa putine calcule, programul devenind deci foarte rapid. Sursa de $100$ de puncte se gaseste 'aici':job_detail/236765?action=view-source.
Programatorii C++ mai au la indemana in STL container-ul "map":http://www.cplusplus.com/reference/stl/map/, care creeaza asocieri intre elemente ce pot fi si de tipuri diferite. Din pacate operatiile efectuate de acest container au tot complexitate $O(logN)$, dar este foarte usor de manevrat; o sursa demonstrativa se gaseste 'aici':job_detail/237991?action=view-source.
h2. Aplicaţii
Prezentam mai jos probleme care pot fi rezolvate eficient cu ajutorul hashurilor:
O aplicatie utila si interesanta este algoritmul "Rabin-Karp":http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm pentru 'potrivirea sirurilor':problema/strmatch. Alte probleme ce pot fi rezolvate eficient cu ajutorul hashurilor sunt:
* 'Secv5':problema/secv5
* 'Map':problema/map
