Fişierul intrare/ieşire:	trie.in, trie.out	Sursă	Arhiva educationala
Autor	Arhiva Educationala	Adăugată de	Lucian Boca •amadaeus
Timp execuţie pe test	0.2 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Trie

Se dau mai multe operatii care gestioneaza o lista de cuvinte, dupa cum urmeaza:

• 0 w - adauga o aparitie a cuvantului w in lista
• 1 w - sterge o aparitie a cuvantului w din lista
• 2 w - tipareste numarul de aparitii ale cuvantului w in lista
• 3 w - tipareste lungimea celui mai lung prefix comun al lui w cu oricare cuvant din lista

Date de intrare

Fisierul trie.in va contine mai multe linii, pe fiecare linie fiind descierea unei operatii, in formatul precizat mai sus.

Date de iesire

Fisierul trie.out va contine, pentru fiecare operatie de tip 2 si 3 din fisierul de intrare, raspunsul operatiei corespunzatoare (in ordinea ceruta in fisierul de intrare).

Restrictii

• Pentru toate operatiile, cuvantul w este format din maxim 20 de caractere din intervalul 'a'..'z'
• Numarul total de operatii nu va depasi 100 000
• Operatiile de tip 1 w vor aparea numai daca w apare cel putin o data in lista de cuvinte

Exemplu

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.

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], fie direct pe multimi de cuvinte, impreuna cu multiplicitatile lor [sursa aici]. 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:

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).

Mai multe informatii despre structura de date veti gasi aici. De asemenea, un tutorial util se afla pe TopCoder. Pentru detalii de implementare puteti consulta sursa demonstrativa.

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. O alta problema, care se foloseste de cautare binara pe niveluri intr-un trie este ratina. De asemenea, cu ajutorul unui trie pot fi rezolvate si:

• sub
• dictree
• Password Search
• Type printer (IOI 2008)
• Toponyms (BOI 2007)

Cum se trimit solutii?