Omówienie zadania Wspinaczka (II etap XXX OI)

Kilka najważniejszych spostrzeżeń

1. Góra Bajtocka składa się z \(n\) polanek, z których każda ma unikalną wysokość. Wysokości polanek są numerowane od 1 do \(n\), co oznacza, że możemy odwzorować tę strukturę jako zbiór punktów (polanek) połączonych "ścieżkami turystycznymi" – jednakże tylko w kierunku wyższych polanek. Ta właściwość ogranicza ruch fotografów do podążania wyłącznie w górę. Taka struktura odpowiada grafowi skierowanemu bez cykli (DAG), gdzie polanki są wierzchołkami, a ścieżki – skierowanymi krawędziami.
2. Zauważmy, że fotografów jest bardzo dużo, tyle co wszystkich polanek. Może to sugerować, że nie musimy się szczególnie przejmować tym, gdzie pójdzie dany fotograf. Można nawet zauważyć, że dla danej polanki startowej \(s\), do każdej polanki, do której da się dotrzeć z \(s\), możemy wysłać jakiegoś nowego, niewykorzystanego fotografa. Innymi słowy, wynikiem dla \(s\) jest suma współczynników fotogeniczności wszystkich polanek, do jakich da się dotrzeć z \(s\) (oraz z samego \(s\)).

Rozwiązanie kwadratowe (\(n \leq 1000\))

Z drugiego spostrzeżenia wynika dosyć prosta metoda na znalezienie wyniku dla danej polanki startowej \(s\). Najpierw musimy sprawdzić, do jakich polanek jesteśmy w stanie dotrzeć. Możemy w tym celu skorzystać na przykład z algorytmu DFS lub BFS.

Kolejnym krokiem jest zsumowanie współczynników fotogeniczności wszystkich odwiedzonych polanek. Możemy w tym celu dla każdej polanki sprawdzić, czy udało nam się ją odwiedzić. Jeśli tak, należy dodać do wyniku jej współczynnik fotogeniczności.

To rozwiązanie jest jednak niewystarczające dla dużych wartości \(n\).

Przejście do pełnego rozwiązania

Przy większych wartościach \(n\) potrzebujemy bardziej efektywnego podejścia. Zaczniemy od kilku spostrzeżeń, które pozwolą zoptymalizować rozwiązanie.

W tym zadaniu możemy zauważyć, że górne ograniczenie na \(k\) jest bardzo małe (\(k \leq 8\)). Może to sugerować, że w rozwiązaniu skorzystamy z masek bitowych.

Możemy zatem przeanalizować, co się stanie, jeśli zamiast jednej polanki startowej rozważymy równocześnie jakiś ich zbiór. Zauważmy, że gdyby udało nam się znaleźć wynik dla wszystkich takich zbiorów, łatwo byłoby odzyskać wynik dla każdego pojedynczego wierzchołka (wystarczy potraktować go jak zbiór składający się jedynie z niego samego).

Spróbujmy znaleźć wynik dla danego zbioru polanek \(S\), w którym najniższą jest polanka \(s\). Zauważmy, że zakładając, iż znamy już wynik dla wszystkich zbiorów polanek, które znajdują się wyżej niż \(s\), dosyć łatwo jest znaleźć wynik. Wystarczy, że zamiast \(s\) do zbioru dodamy wszystkie polanki, do których bezpośrednio da się dojść z \(s\). Wtedy wynikiem będzie suma wyniku dla nowego zbioru oraz współczynnika fotogeniczności \(s\).

Oczywiście takich zbiorów jest bardzo dużo, więc na pierwszy rzut oka mogłoby się wydawać, że to rozwiązanie będzie znacznie za wolne. Można jednak zauważyć, że wystarczy, iż będziemy rozważać jedynie zbiory, w których różnica wysokości to co najwyżej \(k\). Zbiory składające się z tylko jednego wierzchołka w oczywisty sposób spełniają ten warunek, a w ogólności do policzenia wyniku dla takich zbiorów potrzebujemy jedynie wyników dla zbiorów, które również spełniają ten warunek. Takich zbiorów jest już wystarczająco mało.

Jak dokładnie znaleźć wynik?

W przypadku, w którym wynik dla danego zbioru zależy od wyniku innego zbioru (w sposób nie tworzący cykli), możemy skorzystać z programowania dynamicznego. Każdy zbiór możemy reprezentować jako liczbę \(i\) i maskę bitową \(m\) o długości \(k\) taką, że polanka \(p\) należy do zestawu reprezentowanego przez \(m\) wtedy, gdy bit \(m[p-i]\) jest równy 1. Przez \(\mathit{dp}[i][m]\) oznaczmy wynik dla zbioru reprezentowanego przez \(i\) i \(m\).

Wypełnianie tablicy dynamicznej

• Gdy polanka \(i\) nie należy do zbioru: Jeśli polanka \(i\) nie jest uwzględniona w bieżącym stanie, wynik \(\mathit{dp}[i][m]\) będzie równy \(\mathit{dp}[i+1][m >> 1]\). To przesunięcie maski o jeden bit w prawo oznacza, że analizujemy polanki, które są o jeden poziom wyżej, bez uwzględnienia bieżącej polanki \(i\).
• Gdy polanka \(i\) należy do zbioru: Jeśli polanka \(i\) jest częścią zbioru, sprawdzamy, do jakich polanek istnieją bezpośrednie połączenia z \(i\). Oznaczmy ten zbiór jako \(x\) (\(x\) jest maską bitową), gdzie \(x[j] = 1\) wtedy, gdy istnieje połączenie między \(i\) a \(i + j + 1\). Wartość \(\mathit{dp}[i][m]\) jest wtedy sumą współczynnika fotogeniczności polanki \(i\) oraz \(\mathit{dp}[i+1][(m >> 1) | x]\), przy czym \(m >> 1\) to przesunięcie maski w prawo, a \(x\) jest maską dostępnych polanek.

Takie rozwiązanie działa w złożoności czasowej i pamięciowej \(O(n \cdot 2^k)\), ponieważ dla każdej z \(n\) polanek analizujemy \(2^k\) możliwych stanów maski bitowej. Oznacza to, że dla ograniczeń podanych w zadaniu jest wystarczająco efektywne.