h2. Exemplu
table(example). |_. trie.in |_. trie.out |
| 0 lat
0 mare
0 lac
2 la
0 mare
1 lat
0 ma
0 lung
3 latitudine
0 mari
2 mare
0 lat
0 mic
3 latime
2 lac
3 mire
| 0 lung
0 lume
2 lu
2 lume
3 lungime
0 lume
1 lung
3 luntre
0 lacat
2 lume
2 lung
3 lac
| 0
1
4
2
2
0
3
1
2
|
h2. Solutie
O rezolvare brute-force a problemei mentine o lista a tuturor cuvintelor si rezolva operatiile de tip $0 w$ si $1 w$ in timp $O(L)$, iar operatiile de tip $2 w$ si $3 w$ in timp $O(N*L)$, unde $N$ este numarul de cuvinte din lista, iar $L$ lungimea cuvantului $w$. Memoria folosita este $O(LungTot)$, unde $LungTot$ este suma lungimilor cuvintelor din lista. O astfel de abordere ar trebui sa obtina in jur de 30 de puncte, iar o sursa demonstrativa se afla 'aici':http://infoarena.ro/job_detail/226155?action=view-source.
Exista metode de rezolvare care folosesc containerul $set$ din STL, fie pentru multimi de numere intregi (obtinute dupa citirea si normalizarea tuturor cuvintelor) [sursa 'aici':http://infoarena.ro/job_detail/226602?action=view-source], fie direct pe multimi de cuvinte, impreuna cu multiplicitatile lor [sursa 'aici':http://infoarena.ro/job_detail/226601?action=view-source]. Astfel de abordari adauga insa un factor logaritmic (specific structurii $set$) pentru fiecare operatie, iar timpul total de executie devine prea mare. Aceste abordari obtin 50, respectiv 70 de puncte.
Solutia eficienta foloseste o structura de date arborescenta cunoscuta sub numele de $Trie$. Spre deosebire de alte structuri de date, intr-un trie cheile nu sunt identificate prin informatia dintr-un singur nod, ci prin drumul de la radacina trie-ului pana la un anumit nod. Astfel, fiecare nod are un numar de fii egal cu dimensiunea alfabetului folosit, iar fiecare muchie catre un fiu este etichetata cu litera corespunzatoare din alfabet. In figura de mai jos este ilustrat starea trie-ului din exemplu, dupa ce toate operatiile au fost executate. Pentru simplitate grafica, am eliminat din desen muchiile irelevante si am reprezentat ca informatie intr-un nod doar numarul de cuvinte care corespund cheii nodului respectiv:
p=. !problema/trie?trie.png!
Pornind de la radacina (careia i se asociaza sirul vid), fiecarui nod i se asociaza (va memora informatii suplimentare despre) cheia al carei nume se obtine prin concatenarea etichetelor tuturor muchiilor de pe drumul de la radacina trie-ului pana in nodul respectiv (in desen este evidentiat modul in care putem identifica nodul a carui cheie este $"lat"$).
Acest mod de gestionare a listei de cuvinte permite executarea fiecarei operatii in timp $O(L)$. Spatiul de memorie folosit depinde de structura cuvintelor din lista, mai exact de prefixele lor comune. Totusi, el nu va depasi $O(LungTot * |Sigma|)$, unde $Sigma$ este alfabetul folosit (in cazul de fata $|Sigma|=26$). Se poate observa ca memoria totala folosita in cazul cel mai defavorabil pentru restrictiile din enuntul problemei ar putea depasi $50 MB$. Cu toate acestea, testele folosite pentru evaluare au fost construite in asa fel incat sa garanteze (datorita omogenitatii operatiilor din fisierele de intrare) ca in niciun moment dimensiunea trie-ului nu va fi mai mare de $16 MB$. Aceasta decizie a fost luata in vederea incurajarii unei folosiri eficiente a memoriei (in urma stergerii unor ramuri complete din trie, toate locatiile respective vor fi eliberate).
O rezolvare brute-force a problemei mentine o lista a tuturor cuvintelor si rezolva operatiile de tip $0 w$ si $1 w$ in timp $O(L)$, iar operatiile de tip $2 w$ si $3 w$ in timp $O(N*L)$, unde $N$ este numarul de cuvinte din lista, iar $L$ lungimea cuvantului $w$. Memoria folosita este $O(LungTot)$, unde $LungTot$ este lungimea totala a cuvintelor din lista. O astfel de abordere ar trebui sa obtina in jur de 30 de puncte, iar o sursa demonstrativa se afla aici.
Mai multe informatii despre structura de date veti gasi 'aici':http://en.wikipedia.org/wiki/Trie. De asemenea, un tutorial util se afla pe 'TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries. Pentru detalii de implementare puteti consulta 'sursa demonstrativa':http://infoarena.ro/job_detail/248138?action=view-source.
Solutia eficienta foloseste o structura de date arborescenta cunoscuta sub numele de *Trie*. Aceasta permite executarea tuturor operatiilor in timp $O(L)$. Spatiul de memorie folosit depinde de structura cuvintelor din lista, mai exact de prefixele lor comune. Totusi, ea nu va depasi $O(LungTot * |Sigma|)$, unde Sigma este alfabetul folosit (in cazul de fata $|Sigma|=26$). Mai multe informatii despre structura de date vezi gasi 'aici':http://en.wikipedia.org/wiki/Trie. De asemenea, un tutorial util se afla pe 'TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries.
h2. Aplicatii
Ideile din spatele aceastei structuri de date pot fi adaptate si integrate intr-o larga varietate de algoritmi. O aplicatie ingenioasa este solutia problemei 'xormax':http://infoarena.ro/problema/xormax. O alta problema, care se foloseste de cautare binara pe niveluri intr-un trie este 'ratina':http://infoarena.ro/problema/ratina. De asemenea, cu ajutorul unui trie pot fi rezolvate si:
Ideile din spatele aceastei structuri de date pot fi adaptate si integrate intr-o larga varietate de algoritmi. O aplicatie ingenioasa este solutia problemei 'xormax':http://infoarena.ro/problema/xormax. O alta problema, care se foloseste de cautare binara pe niveluri in Trie este 'ratina':http://infoarena.ro/problema/ratina. De asemenea, cu ajutorul unui Trie pot fi rezolvate si urmatoarele:
* 'sub':problema/sub
* 'dictree':problema/dictree
* 'xormax':problema/xormax
* 'ratina':problema/ratina
* 'Password Search':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=843
* "Type printer":http://www.ioi2008.org/images/stories/ioi2008/tasks/day1/printer.pdf, _IOI 2008_
* "Toponyms":http://boi2007.edu.md/index.php?option=com_content&task=view&id=25&Itemid=51, _BOI 2007_
* 'sub':http://infoarena.ro/problema/sub (infoarena)
* 'dictree':http://infoarena.ro/problema/dictree (infoarena)
* 'Password Search':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=843 (uva)
* _Type printer_ (IOI 2008)
* _Toponyms_ (BOI 2007)
== include(page="template/taskfooter" task_id="trie") ==
