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}, \dots, 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) \to (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}, \dots, 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}, \dots, 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} + \dots + 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}, \dots, 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}, \dots, w_{i - 1}$ na mieczach $1, \dots, 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))$ .