Omówienie zadania Rycerz (II etap XXXI OI)

Ogólne podejście

Będziemy rozpatrywać kolejne miecze od pierwszego i obliczać dla nich największą możliwą do uzyskania wartość przy założeniu, że chcemy uzyskać też (już obliczone) wartości mieczy o mniejszych numerach.

Podproblem

Zanim zajmiemy się obliczaniem tych maksymalnych wartości, zastanówmy się nad następującym podproblemem. Powiedzmy, że mamy dany ciąg \(w_1, \ldots, w_k\) i naszym zadaniem jest tylko stwierdzić, czy jesteśmy w stanie uzyskać zestaw mieczy taki, żeby wartość \(i\)-tego miecza była równa przynajmniej \(w_i\).

Zdefiniujmy nowy graf, w którym wierzchołek oznacza parę (miasto, podzbiór mieczy), przy czym podzbiór mieczy oznacza miecze, dla których osiągnęliśmy już zamierzony cel. Dla każdej krawędzi sprawdzamy, jaki podzbiór mieczy osiąga cel, i tworzymy przejście między wierzchołkami: $$(v, s) \rightarrow (u, s \cup z)$$ dla krawędzi z \(v\) do \(u\) oraz wyliczonym dla niej podzbiorem \(z\). Na tym nowym grafie możemy wykorzystać algorytm BFS z wierzchołka \(1\) aby sprawdzić, czy jesteśmy w stanie dotrzeć do wierzchołka \(n\) z pełnym zbiorem mieczy po co najwyżej \(d\) krokach. Ten podproblem rozwiązaliśmy w czasie \(O(2^k \cdot (n + m))\).

Wyszukiwanie binarne

Powiedzmy, że chcemy obliczyć wynik dla \(i\)-tego miecza i znamy już wartości \(w_1, \ldots, w_{i - 1}\). Możemy wyszukiwać binarnie szukaną wartość \(w_i\): możemy sprawdzić, czy zachodzi \(w_i \geq x\), poprzez rozwiązanie podproblemu dla \(w_1, \ldots, w_{i - 1}, x\). Ważnym jest, aby rozwiązywać ten podproblem przy założeniu, że jest tylko \(i\) mieczy (zamiast \(k\)), ponieważ pozostałe nie wpływają na szukaną wartość \(w_i\). Wtedy uzyskamy złożoność \(O((2^1 + 2^2 + \ldots + 2^k) \cdot (n + m) \cdot \log m) = O(2^k \cdot (n + m) \cdot \log m)\).

Rozwiązanie wzorcowe

Korzystając ze wspomnianego podproblemu, trudno jest uzyskać rozwiązanie lepsze niż to z wyszukiwaniem binarnym. Chcemy, aby rozwiązanie podproblemu dawało nam więcej informacji. Załóżmy, że mamy obliczone już wartości \(w_1, \ldots, w_{i - 1}\). Chcielibyśmy teraz dla każdej krawędzi stwierdzić, czy jesteśmy w stanie przejść daną krawędzią na jakiejś ścieżce długości co najwyżej \(d\) z \(1\) do \(n\), uzyskując wartości \(w_1, \ldots, w_{i-1}\) na mieczach \(1, \ldots, i - 1\). W tym celu obliczymy za pomocą BFS odległości z wierzchołka \(1\) oraz odległości z wierzchołka \(n\). Nazwijmy je \(p_{v, s}\) oraz \(q_{v, s}\), gdzie \(v\) to numer miasta, a \(s\) to podzbiór mieczy. Następnie dla krawędzi z \(u\) do \(v\) sprawdzamy, czy \(p_{u, s} + q_{v, z} + 1 \leq d\), gdzie \(s \cup z\) jest pełnym zbiorem \(i - 1\) mieczy. Aby nie przeglądać każdej pary \(s\) oraz \(z\) wystarczy sprawić, aby tablica \(q_{v, s}\) oznaczała minimalną liczbę kroków potrzebną do uzyskania co najmniej zbioru mieczy \(s\) w mieście \(v\). Po takiej poprawce wystarczy dla pojedynczej krawędzi przeiterować się po każdym zbiorze \(s\) i przyjąć za \(z\) dopełnienie \(s\) do zbioru wszystkich mieczy. To rozwiązanie działa w analogiczny sposób w złożoności \(O(2^k \cdot (n + m))\).