Dzisiaj zajmiemy się zadaniem Poborcy podatkowi z Potyczek Algorytmicznych 2021. W zadaniu mamy do dyspozycji drzewo ważone na krawędziach. Chcemy wybrać zbiór rozłącznych krawędziowo ścieżek o długości 4, który maksymalizuje sumę wartości na krawędziach.
Mamy drzewo. Chcemy coś maksymalizować. Więc prawdopodobnie trzeba użyć programowania dynamicznego na drzewach. Dla każdego wierzchołka v chcemy policzyć cztery wartości: D[v, 0], D[v, 1], D[v, 2] oraz D[v, 3]. D[v, 0] oznacza rozwiązanie naszego problemu dla poddrzewa zaczepionego w wierzchołku v. Pozostałe D[v, i] oznaczają takie rozwiązanie w którym jest jeszcze jedna ścieżka, która nie ma jeszcze długości 4. Ma ona długość i oraz jest zakończona w wierzchołku v.
Załóżmy, że wszystkie te wartości są policzone dla każdego syna wierzchołka v. Postarajmy się na ich podstawie policzyć wartość D[v, 0] (pozostałe wartości D[v, i] policzymy później). Dla każdego syna s, możemy:
- Wziąć D[s, 0] i nie brać krawędzi (v, s)
- Wziąć D[s, 0] i wziąć krawędź (v, s)
- Wziąć D[s, 1] i wziąć krawędź (v, s)
- Wziąć D[s, 2] i wziąć krawędź (v, s)
- Wziąć D[s, 3] i wziąć krawędź (v, s)
Ponadto musimy spełnić następujące warunki:
- Synów dla których wybraliśmy opcję 3 musi być parzyście wiele
- Synów dla których wybraliśmy opcję 2 musi być tyle samo co synów dla których wybraliśmy opcję 4
To wynika z tego, że dwaj synowie dla których wybraliśmy opcję 3 jak i synowie dla których wybraliśmy opcję 2 i 4, tworzą ścieżkę o długości 4.
W jaki sposób możemy wybrać opcję dla każdego z synów aby otrzymać optymalne rozwiązanie? No cóż… możemy użyć… programowania dynamicznego. Niech s1, s2, …, sm oznaczają synów wierzchołka v. Niech DP[ i ][ n / p ][ diff ] oznacza optymalne rozwiązanie dla synów s1, s2, …, si gdzie opcję 3 wybraliśmy nieparzyście wile razy (n) lub parzyście wiele razy (p) i dla której różnica między liczbą synów dla których wybraliśmy opcję 2 a liczbą synów dla których wybraliśmy opcję 4 wynosi diff. Wartość tablicy możemy teraz łatwo policzyć na podstawie wartości poprzednich:
DP[ i ] [ parity ] [ diff ] = maximum( D[si, 0] + DP[i-1][parity] [diff],
D[si, 0] + w(v, si) + DP[i-1][parity] [diff-1],
D[si, 1] + w(v, si) + DP[i-1][!parity][diff],
D[si, 2] + w(v, si) + DP[i-1][parity] [diff+1],
D[si, 3] + w(v, si) + DP[i-1][parity] [diff])Każda z linijek odpowiada każdej z opcji przedstawionej wyżej. Ponieważ diff może być z przedziału -m/2 .. m/2 dynamik działa w czasie O(n2) i na konkursie można było otrzymać za niego 4 punkty.
Aby otrzymać 10 punktów wystarczyło lekko zmodyfikować powyższy program. Najsłabszym punktem naszego programu jest przedział -m/2 .. m/2 wspomniany wyżej. Musi on być taki, gdyż może się okazać, że dane są tak wrednie dobrane, że pierwszych m/2 synów będzie opłacało się wziąć w opcji 2, a ostatnich m/2 w opcji 4. Co się jednak stanie jeśli weźmiemy losową permutację synów wierzchołka v? Wtedy taka sytuacja będzie niezwykle mało prawdopodobna dla dużych wartości m. Jeśli znasz podstawy procesów stochastycznych, to być może wiesz, że z bardzo dużym prawdopodobieństwem wystarczy nam przedział -m^(1/2) .. m^(1/2) hasło do wygooglania: random walks. Ta prosta zmiana daje nam algorytm O(n1.5). Istnieją algorytmy deterministyczne rozwiązujące to zadanie w czasie O(n lg n). Ale zostawmy je na inną okazję.
