Omówienie zadania Dostawy (I etap XXXIII OI, tura zdalna)

Analiza warunku o kolizjach

Jako \(d_{i,j}\) zdefiniujmy minimalną liczbę pól, które musi pokonać bohater, aby dostać się do pola \((i, j)\), jednocześnie nie przechodząc przez pola z przeszkodami. Wartość \(d_{i,j}\) będziemy nazywali odległością pola \((i, j)\). Załóżmy na chwilę, że nie istnieje warunek, który mówi, że dwaj bohaterzy nie mogą znajdować się w jednym momencie na tym samym polu - wtedy każdy bohater wybrałby najkrótszą możliwą ścieżkę do pola, do którego musi dostarczyć wiadomość.

Czy jesteśmy w stanie wymusić na bohaterach, aby obierali ścieżki o najkrótszej możliwej długości, przy jednoczesnym respektowaniu warunku o braku "kolizji"? Odpowiedź brzmi: Tak. Załóżmy bez straty ogólności, że pierwszy zrekrutowany bohater dostarczy wiadomość do jednego z najdalszych fortów, kolejny dostarczy wiadomość do jednego z najdalszych fortów, do których nie został przydzielony jeszcze żaden bohater, i tak dalej. Zachodzi własność, że dla każdej pary bohaterów, którzy nie dotarli jeszcze na docelowe miejsce, ten, który wyszedł wcześniej, znajduje się na polu bardziej oddalonym od zamku Bajtazara niż ten, który wyszedł później.

Co jednak dzieje się, kiedy któryś z bohaterów dotarł już do docelowego fortu? Wtedy bohaterowie mogą stać na jednakowo odległych polach, lecz wiemy, że są to różne pola, gdyż docelowe pola różnych bohaterów są różne.

Jak odzyskać wynik?

Skoro każdy bohater może dostać się do swojego fortu w \(d_{i, j}\) turach, a \(k\)-ty w kolejności bohater czeka \(k-1\) tur na wyruszenie w drogę, to wynikiem jest maksymalna wartość spośród \(k-1 + d_k\), gdzie \(d_k\) oznacza dystans, który musi przebyć \(k\)-ty bohater, aby dostać się do wybranego fortu. Strategia wysyłania bohaterów do najdalszych fortów nie tylko zapobiega kolizjom, ale jest również optymalna dla minimalizacji czasu ostatniej dostawy. Intuicyjnie: chcemy, aby forty wymagające najdłuższej podróży (duże \(d_k\)) czekały jak najkrócej (małe \(k-1\)).

Rozwiązanie brutalne

Zacznijmy od obliczenia wartości \(d_{i, j}\) dla każdego pola, do którego da się dostać, zaczynając w zamku Bajtazara. Najprostszym sposobem na osiągnięcie tego jest użycie algorytmu BFS na grafie, w którym wierzchołkami są pola planszy, a krawędzie istnieją pomiędzy wierzchołkami pól sąsiadujących ze sobą.

Po znalezieniu powyższych wartości, możemy dla konkretnego zapytania przygotować ciąg odległości fortów dla kolejnych bohaterów, czyli ciąg odległości fortów posortowany malejąco. Następnie w czasie liniowym od liczby fortów odzyskujemy wynik: \(\max_k \{ k-1 + d_k \}.\) Takie rozwiązanie działa w czasie \(O(qn^2)\) lub \(O(qn^2 \log n)\) w zależności od implementacji.

Optymalizacja

Zastanówmy się, co możemy zoptymalizować w naszym rozwiązaniu. Póki co częścią zaporową było brutalne przeliczanie wyniku po każdej aktualizacji - przyjrzyjmy się więc, w jaki sposób wynik zmienia się po operacjach dodania lub usunięcia fortu. Gdy usuwamy fort, to oprócz tego, że nie będziemy liczyć go do wyniku, to bohaterowie, którzy wyruszali do swoich fortów po bohaterze, który szedł do obecnie usuwanego fortu, będą mogli wyruszyć o jedną turę szybciej. Znaczy to tyle, że w ciągu fortów posortowanych po odległości, znajdą się one o jedną pozycję wcześniej.

Co dzieje się, kiedy fort pojawia się na planszy? Jeżeli spojrzymy na ciąg fortów posortowany po odległości od zamku, to nowo dodany fort pojawi się na najdalszej pozycji przed fortem bliższym od niego. Znaczy to tyle, że wszystkie forty, które są bliższe od dodawanego, znajdują się teraz o jedną pozycję dalej, więc doliczają o 1 więcej do wyniku.

Rozwiązanie wzorcowe

Do czego przydają się powyższe obserwacje? Zamiast ciągu odległości fortów rozważmy ciąg odległości wszystkich pól, po których mogą poruszać się bohaterowie (tj. fortów i wolnych pól), przy czym miejsca w ciągu, odpowiadające polom, na których aktualnie znajdują się forty, oznaczmy jako "zapalone".

Jak odzyskać wynik z takiego ciągu? Dla każdego zapalonego pola jego wartość zdefiniujmy jako sumę jego odległości od zamku oraz liczby zapalonych pól, znajdujących się wcześniej w ciągu niż ono. Wartość niezapalonego pola wynosi zaś \(-\infty\). W jaki sposób odpowiadać na zapytania oraz w szybki sposób aktualizować wartości poszczególnych pól?

Drzewo przedziałowe

Do tego zadania możemy użyć drzewa przedziałowego, które w każdym węźle trzyma liczbę zapalonych pól na przedziale oraz największą wartość na przedziale. Niech \(i\) będzie pewnym węzłem drzewa przedziałowego, zaś \(l\) oraz \(r\) węzłami, które są jego synami (odpowiednio lewym oraz prawym synem).

Liczba zapalonych pól na przedziale węzła \(i\) to suma liczby zapalonych pól na przedziałach węzłów \(l\) oraz \(r\). Największa wartość na przedziale węzła \(i\) jest zaś równa maksimum z największej wartości na przedziale węzła \(l\) oraz sumy największej wartości na przedziale węzła \(r\) oraz liczby zapalonych pól na przedziale węzła \(l\).

Konstruując drzewo przedziałowe w ten sposób, w głównym węźle zawsze znajdziemy informację o maksymalnej wartości w ciągu. Aktualizacja naszego drzewa przedziałowego zajmuje \(O(\log n)\) czasu, więc końcowa złożoność naszego algorytmu to \(O(n^2 + q \log n)\)