Revizia anterioară Revizia următoare
Holiday
Autobuze2
Litere2
- Două cuvinte fac parte din acelaşi grup dacă sunt formate din aceleaşi litere, repetate de oricâte ori.
Vom lua astfel fiecare cuvânt în parte şi vom marca toate cele 26 litere ale alfabetului englez ('a' - 'z') cu 1, dacă litera apare în cuvânt respectiv cu 0, dacă nu apare. Vom obţine astfel un şir binar de lungime 26. Putem privi acest şir binar ca fiind un număr scris în baza 2. Putem transforma acest număr în baza 10, reformulând afirmaţia iniţială astfel:
- Două cuvinte fac parte din acelaşi grup dacă numărul astfel obţinut asociat celor două cuvinte este acelaşi.
Deci, numărul de grupuri va fi egal cu numărul de valori distincte asociate numerelor. Pentru a determina acest număr ne vom folosi de o structură de date tip Hash sau de o sortare (aceasta fiind teoretic, soluţia de complexitate mai mare).
Timpul de execuţie al acestei probleme se putea mări destul de uşor dacă în program se foloseau elemente din STL sau tipul de date string, care se miscă mai lent în practică.
Treesmen
Vom face o liniarizare a arborelui, cu ajutorul căreia vom efectua eficient cele două operaţii. Soluţia se bazează pe prima idee care ne vine în minte, adică, pentru prima operaţie facem update pe intervalul [first[stramos], first[node]] si pentru a doua căutam ce valoare avem pe poziţia first[node]; dar, s-ar putea, ca la update să avem noduri care nu se află pe lanţ dar apar şi în interval. Plecând de la această observaţie ajungem la observaţia : aceste noduri vor avea first-ul si last-ul incluse în [first[stramos], first[node]]. Astfel putem defini în last[node] = suma valorilor când node nu a apare pe lanţ. Făcând această observaţie răspunsul pentru un query va fi first[node] - last[node]. Update-ul e o progresie arimetica, aşa că, nodul X o să crească cu valoarea p + (nivel[X] - nivel[stramos])*r. Dacă desfacem paranteza si grupam termenii convenabil obtinem p-nivel[stramos]*r + nivel[X]*r. Astfel, problema devine la a face update pe un interval cu o valoare X; ne putem folosi de arbori de intervale sau arbori indexati binar.
Complexitate O(M * log N).
