СИО стабло
Аутор: Тадија Шебез
Текст и тест примери: Тадија Шебез
Анализа решења: Тадија Шебез
Тестер: Никола Пешић и Александар Златески
Решење када је n \leq 1000
Временска сложеност: O(N^2)
Покренимо алгоритам претраге у дубину (DFS) од сваког чвора. Чувајмо колико се пута које слово појављује на тренутном путу и са тим информацијама лако можемо да повећамо решење за сваки СИО пар.
Решење када је слово \text{"S"} урезано на тачно једној грани
Временска сложеност: O(N)
Решење је број путева дужине 3 на којима се свако од три слова појављује по једном. Пронађимо грану на којој је урезано слово \text{"S"} и запамтимо њене крајеве. Нека су то чворови U и V. Пребројимо колико има путева дужине 2, чији је јадан крај неки од чворова U и V, такве да је на њима урезано по једно слово \text{"I"} и \text{"O"}. На решење још додајмо број парова грана тако да једна креће из U, а друга из V и на једној је урезано слово \text{"I"}, а на другој слово \text{"O"}.
Решење када је СИО стабло ланац
Временска сложеност: O(N log N)
Направимо стринг од свих слова која се појављују на гранама од једног до другог краја ланца, у том поретку. Решење се своди на број подстрингова у којима се свако од 3 слова појављује једнак број пута. Нека је \text{X(i)} број појављивања слова X у првих i слова. За сваки префикс од дужине 0 до N-1 (имамо N-1 грана па самим тим исто толико слова), запамтимо пар P(i) = (\text{S(i)}-\text{I(i)}, \text{S(i)}-\text{O(i)}). Посматрајмо подстринг од L-тог до R-тог слова. Ако се слова \text{S} и \text{I} појављују исти број пута онда мора да важи (\text{S(R)}-\text{S(L-1)}) - (\text{I(R)}-\text{I(L-1)}) = (\text{S(R)}-\text{I(R)}) - (\text{S(L-1)}-\text{I(L-1)}) = 0 односно прве вредности из парова P(R) и P(L-1) морају бити једнаке. Слично се добија и да друге вредности из ових парова морају бити једнаке, односно парови P(R) и P(L-1) морају бити једнаки. Сада остаје још да пребројимо колико имамо парова префикса са једнаким P. Ово можемо урадити сортирањем низа парова или помоћу \text{std::map}.
Решење када је СИО стабло комплетно бинарно стабло
Временска сложеност: O(N log^2 N)
Нађимо прво за колико СИО парова се корен стабла налази на путу између њих. То морају бити чворови из различитих подстабала. Слично као у решењу за ланац нађимо вредности X(i) колико се пута појављује слово X на путу од корена до чвора i. Такође за сваки чвор запамтимо пар P(i) = (\text{S(i)}-\text{I(i)}, \text{S(i)}-\text{O(i)}). У \text{std::map} запамтимо колико се пута који пар појављује у левом подстаблу. За чвор i у десном подстаблу ако га упаримо са чвором j у левом подстаблу тако да важи P(j) = (\text{I(i)}-\text{S(i)}, \text{O(i)}-\text{S(i)}), свако од три слова ће се појављивати исти број пута на путу између i и j. За сваки чвор i у десном подстаблу помоћу \text{std::map} нађимо колико има таквих чворова j у левом подстаблу и то додајмо на решење. Сада када смо у обзир узели све путеве који прелазе преко корена стабла, знамо да су сви остали путеви између чворова из истог подстабла па можемо рекурзивно да решимо проблем за лево и десно подстабло. Подстабло величине M решавамо у временској сложености O(M log M). Како је висина стабла O(log N) збир величина подстабала је O(N log N) па је временска сложеност целог алгоритма O(N log^2 N).
Решење за 100 поена
Временска сложеност: O(N log^2 N)
Решење је слично као за комплетно бинарно стабло. У сваком стаблу постоји чвор такав да када избришемо њега и све његове гране, свака повезана компонента која остане мора имати барем два пута мањи број чворова него стабло пре брисања. Овај чвор се назива центроид и могуће га је наћи помоћу алгоритма претраге у дубину (DFS). Нађимо за колико СИО парова се центроид налази на путу између њих, на сличан начин као у претходном решењу, затим обришимо центроид и све његове гране. Рекурзивно решимо проблем за повезане компоненте које су нам остале. Због особина центроида дубина ове рекурзије је O(log N) па је временска сложеност целог алгоритма O(N log^2 N).
Алтернативно решење за 100 поена
Временска сложеност: O(N log^2 N)
Као у решењу за комплетно бинарно стабло, нађимо вредности P(i) за сваки чвор. Овај пут прво рекурзивно решавамо подстабла, а затим тражимо број СИО парова тако да се корен налази на путу између њих. Сваки рекурзивни позив ће направити \text{std::map}-у у којој су пребројане вредности P(i) за све чворове i у тренутном подстаблу. Како бисмо направили \text{std::map} за тренутно подстабло потребно је да спојимо \text{std::map}-е за подстабла која остану када се избаци корен овог подстабла, а затим да убацимо P(koren). Како бисмо добили добру временску сложеност, када спајамо \text{std::map}-е увек пролазимо кроз мању и пребацујемо све из ње у већу. Приликом спајања пребројавамо СИО парове. Посматрајмо пут од чвора U до V. Нека је W чвор на најмањем растојању од корена који се налази на путу између U и V. Пар (U, V) је СИО пар ако и само ако важи P(U) + P(V) - 2 P(W) = (0, 0). Ако се U налази у мањој \text{std::map}-и, на решење додајемо број чворова у већој, таквих да је P(V) = 2 P(W) - P(U). Остаје још да анализирамо временску сложеност овог алгоритма. Посматрајмо за неки чвор колико пута је био пребачен из једне у другу \text{std::map}-у. Сваки пут када је пребачен, величина \text{std::map}-е у којој је повећала се бар два пута јер је величина нове \text{std::map}-е збир величина \text{std::map}-е у којој је био и веће \text{std::map}-е. Због тога један чвор није могао бити пребачен више од log N пута. Следи да је укупан број пребацивања O(N log N), па како је за сваку операцију над \text{std::map}-ом потребно O(log N) времена, укупна временска сложеност овог алгоритма је O(N log^2 N).
