A2: Кики
Аутор: Марко Миленковић
Текст: и тест примери: Марко Миленковић
Анализа решења: Марко Миленковић
Тестирање: Димитрије Ердељан
Почетна запажања
Пре свега, јасно је да морамо да користимо 64-битни тип података, јер решење може бити драстично веће од 2\cdot10^9.
Затим, какво стање Лименом дефинитивно не доноси победу? Приметимо да уколико је неки чвор обојен или има обојеног суседа, онда неће бити проблематичан - у смислу да је исфорсирано која боја ће морати да се појави на том чвору. И заправо, врло лако можемо да покажемо да уколико сви чворови испуњавају својство да су или обојени (било којом бојом) или је неки од њихових суседа обојени (поново било којом бојом), онда је то дефинитивно победничка позиција за Лименог. Наравно, лако се и показује да уколико ово не важи, постоји начин да Кики победи (обоји један од чворова који не задовољавају својство обрнуто од очекиване боје).
Шта нам је очекивана боја? Јасно је да уколико имамо неко решење где неке чворове бојимо плавом, а неке друге црвеном бојом, такође је и супротно бојење решење. Ако се претварамо да бојимо само једном бојом, онда можемо на крају само да видимо како да их расподелимо са бојама, једино је важно да не постоје два чвора исте боје на непарном растојању. Нпр, не одговара ако имамо секвенцу чворова црвено-необојено-необојено-црвено, јер унутрашњи чворови морају бити плави а суседни су. Када на крају обојимо ‘једном бојом’ стабло, можемо само да пустимо претрагу у ширину/дубину од произвољног чвора и у односу на парност дубине одлучујемо која боја ће бити додељена том чвору уколико је предвиђено да буде обојен (нпр парне дубине црвеном, непарне плавом).
Успутно, скуп чворова који тражимо се назива доминантан скуп графа/стабла (Доминантни скуп — Википедија). Међу свим таквим ми бирамо минималан.
N \leq 20
У овом подзадатку је довољно да испробамо свих 2^N могућих бојења стабла и видимо које је задовољавајуће и има најмању збирну тежину. Временска сложеност овог решења је \mathcal{O}(N\cdot 2^N).
Чвор 1 је повезан са чворовима 2, 3, \ldots, N
Овакав тип графова се назива звезда (Star (graph theory) - Wikipedia). Једна варијанта је да обојимо само чвор 1. Друга је да обојимо све остале чворове. У оба та случаја добијамо доминантан скуп и потребно је само да изаберемо онај чија је сума тежина мања. У оба случаја бојимо чворове једном бојом по избору. Временска сложеност овог решења је \mathcal{O}(N).
Чвор i је повезан са чвором i+1, за i=1,2,\ldots,N-1
Овакав тип графова се назива пут (Path graph - Wikipedia). Сада задатак практично постаје: дат је низ и потребно је да изаберемо елементе тако да је сваки елемент или изабран или неки његов сусед изабран, а тако да је сума тих елемената минимална. Ово можемо решити на неколико начина, од којих је најинтуитивнији динамичко програмирање.
Једно од могућих стања јесте dp[i][0/1][0/1] - односно колика је минимална сума елемената тако да је до i-тог валидно изабрано, док нам друга и трећа координата означавају да ли су претходна два елемента обојена. У случају када претходна два нису обојена, приморани смо да обојимо тренутни, у свим осталим случајевима можемо да бирамо. На крају нас интересује стање последњег елемента. Временска сложеност овог решења је \mathcal{O}(N).
Све тежине су једнаке међусобно
У овом подзадатку могуће је користити greedy приступ. Приметимо да нам никад није оптимално да бојимо листове стабла, јер уколико њихове родитеље обојимо, већи број чворова релаксирамо и додајемо у доминантни скуп. Уз овај и сличне аргументе може се показати (доказ остављамо читаоцу) да следећа стратегија функционише:
- Изаберимо чвор $X$ са највећим бројем суседа који су листови и обојимо тај чвор
- Бришемо из стабла чвор $X$ и све његове суседе степена мањег или једнаког $2$
- Понављамо поступак рекурзивно док не буду обрисани сви чворови
Подсетник да бојимо у одговарајућу боју на основу почетних закључака. Временска сложеност овог приступа је \mathcal{O}(N) или \mathcal{O}(N\log_2 N), у зависности од имплементације.
Решење без додатних ограничења
За цео задатак је потребно применити поново динамичко програмирање. За чвор кажемо да има исфорсирану боју (односно да је исфорсиран чвор) уколико је обојен он или неки његов сусед.
За почетак ћемо кореновати стабло у произвољном чвору r. Стање ће нам бити dp[i][0/1] - минимална сума обојених чворова у подстаблу чвора i тако да је то оптимално бојење, а притом чвор i јесте форсиран (уколико је друга координата 1), односно није нужно форсиран (уколико је друга координата 0).
Прецизније користимо технику bottom-up динамичког програмирања. Крећемо од листова стабла и рачунамо на горе стања. У ред додајемо чворове чија су сва деца већ обиђена. За листове постављамо dp[l][0] = 0 и dp[l][1] = 1.
Када рачунамо dp[i][1] имамо два избора. Први јесте да обојимо чвор i и онда деца не морају да имају од раније исфорсирану боју. Други јесте да једно од деце буде обојено, затим деца тог детета не морају да имају исфорсирану боју, а сва остала деца чвора i такође морају да имају исфорсирану боју. По свој деци тражимо миниммум. Математички записано: dp[i][1] = min(a[i] + \sum_{x \in deca[i]}dp[x][0], min_{x \in deca[i]}(a[x] + \sum_{y \in deca[x]}dp[y][0] + \sum_{z \in deca[i], z \neq x} dp[z][1])).
Када рачунамо dp[i][0] битно нам је да сва деца чвора i имају исфорсирану боју, јер им чвор i то неће омогућити. Тако да је прелаз $dp[i][0] = min(\sum_{x \in deca[i]}dp[1], dp[i][1]).
На крају, решење је dp[r][1]. Временска сложеност овог решења је \mathcal{O}(N) или \mathcal{O}(N \log(N)), у зависности од имплементације.
Напомена
Подзадатак N \leq 1000 је изостављен јер представља само спорију имплементацију општег решења.