Omówienie zadania Surowa zima (III etap XXVIII OI)

Rozwiązanie wykładnicze

Żeby zaimplementować rozwiązanie brutalne, skorzystamy z obserwacji, która zostanie niebezpośrednio udowodniona później: opłaca się zawracać odśnieżarką tylko w punktach całkowitoliczbowych. Można już na tym zbudować rozwiązanie wykładnicze: rozpatrzymy wszystkie możliwe stany (pozycja, zapas baterii, maska bitowa z odśnieżonymi fragmentami drogi). Mając takie stany i wyznaczając przejścia (ruch w lewo lub w prawo), można policzyć (dynamikiem lub algorytmem BFS) minimalną liczbę ruchów potrzebną do odśnieżenia całej drogi. Złożoność takiego rozwiązania to \(O(d 2^\ell \ell^2)\) i pokonuje pierwsze podzadanie.

Co ciekawe, bardzo mało uczestników podczas zawodów zdecydowało się zaimplementować takie rozwiązanie. Wszystkie pozostałe podzadania wymagały już sporej liczby obserwacji i ich rozwiązania głównie różniły się złożonością lub trochę prostszymi obliczeniami, więc był zauważalny skok trudności między pierwszym podzadaniem (z limitami na wykładnik) a kolejnymi podzadaniami. Łatwo można było w tym zadaniu otrzymać „tunnel vision” spowodowany chęcią zdobycia większej liczby punktów. Aby zdobyć dodatnią liczbę punktów, należało jednak przełamać się i zaimplementować rozwiązanie wykładnicze, chociażby po to, by móc testować kolejne rozwiązania, znajdować błędy i weryfikować poprawność obserwacji. Odpowiednia strategia podczas zawodów (a szczególnie gdy są trudne zadania, tak jak to zadanie) jest kluczowa, choć często trudno jest ją dobrze zrealizować w praktyce.

Kluczowe pomysły

Zaczniemy od kilku definicji, obserwacji oraz przekształceń treści, które małymi krokami przybliżą nas do rozwiązania.

Fragmenty drogi pomiędzy dwoma kolejnymi sprawnymi (niezepsutymi) stacjami ładowania (w skrócie: stacjami) nazwiemy odcinkami. Brzegowe odcinki mogą mieć tylko jedną stację, zaś każdy inny odcinek jest otoczony dokładnie dwiema stacjami.

Ciąg stacji oraz fragmentów drogi, które Bajtazar przebywa, by odśnieżyć całą drogę, nazwiemy trasą.

Na początku musimy naładować odśnieżarkę, a najlepszymi opcjami są najbliższe stacje po lewej bądź prawej stronie (o ile istnieją) od pozycji początkowej, na którą zwiało odśnieżarkę. Dalej będziemy zakładać, że zaczynamy w pewnej stacji. Tym samym będziemy zakładać, że odśnieżarka jest naładowana, i od teraz będziemy pomijać czas potrzebny na przejście do tej pierwszej stacji. W implementacjach nie należy zapomnieć o sprawdzeniu obu najbliższych stacji, doliczeniu do wyniku czasu potrzebnego na przejście do nich, a na koniec wypisaniu mniejszego z tych dwóch wyników.

Całą trasę można przedstawić jako ciąg kursów, gdzie pojedynczy kurs definiujemy jako fragment trasy spełniający:

  1. zaczynamy z naładowaną odśnieżarką w jakiejś stacji,
  2. przechodzimy jakiś fragment drogi (bez zawracania),
  3. odśnieżamy jakiś spójny fragment drogi (bez zawracania),
  4. możemy (ale nie musimy) zawrócić i wracamy do tej samej lub do sąsiedniej stacji,
  5. ładujemy odśnieżarkę.

Czas spędzony podczas wykonywania jednego kursu to po prostu jednokrotność lub dwukrotność (zależnie od tego, czy zawracamy) odległości między stacją a kolejną stacją.

Kurs nie przechodzi nad żadnymi innymi stacjami, bo jeżeli byśmy podczas kursu przeszli do jakiejś innej stacji, to po prostu możemy zamiast tego naładować tam odśnieżarkę i rozpocząć nowy kurs.

Jeżeli spojrzymy na pojedynczy odcinek, to możemy (i często będziemy) przechodzić przez jakiś fragment tego odcinka wielokrotnie. Ale jeżeli już rozbijemy optymalną trasę na kursy, to będziemy przechodzić ze stacji do stacji w taki sposób, że (pomijając kursy, w których wracamy do tej samej stacji) przez każdą stację przejdziemy co najwyżej dwa razy (raz w obu kierunkach).

Intuicyjnie, podczas odśnieżania wszystkich odcinków, Bajtazar będzie się progresywnie poruszał aż spotka jeden z dwóch brzegów drogi, a następnie będzie się progresywnie poruszał w drugą stronę aż spotka drugi koniec.

Istnieje jednak przypadek, który jest kluczowy, ale bardzo łatwo go przeoczyć. Jeżeli spotkaliśmy już jeden z brzegów drogi i idziemy do drugiego brzegu, to być może opłaca się jakiś bardzo długi odcinek przejść w jedną stronę, po czym wyczyścić wszystkie kolejne odcinki (więc tym samym dotkniemy drugiego brzegu drogi), wrócić do tego długiego odcinka, załadować odśnieżarkę i w ramach ostatniego kursu odśnieżyć jakiś fragment tego długiego odcinka, kończąc odśnieżanie gdzieś w środku tego odcinka (bez powrotu do stacji). Idea jest taka, że być może opłaca się dłużej odśnieżać dalsze odcinki (bo przechodzimy przez nie dwustronnie zamiast jednostronnie), po to, aby zakończyć całą trasę pośrodku tego długiego odcinka, dzięki czemu nie trzeba spędzać czasu na powrót do stacji, która jest daleko.

Najlepszy czas dla odcinków

Docelowo chcemy wyznaczyć wzory na czas potrzebny do odśnieżania odcinka o długości \(s\), zależnie od tego, czy jest on brzegowy, czy przechodzimy po nim jednostronnie, dwustronnie, lub czy będziemy na nim kończyć trasę.

  1. Na początek łatwiejszy (i niezbędny) przypadek, gdzie mamy tylko jedną stację na brzegu odcinka długości \(s\), z której możemy korzystać. Taki przypadek występuje dla brzegowych odcinków.

    Jak już wybierzemy kursy odśnieżające ten odcinek, to można je dowolnie permutować bez zmiany wyniku. Możemy zacząć kursem odśnieżającym \(k\) ostatnich metrów odcinka (czas \(2s\)). Następnie odśnieżamy ostatnie nieodśnieżone \(k\) metrów (czas \(2(s-k)\)) i tak dalej, aż skończymy w punkcie startu. Dlaczego jest to optymalne odśnieżanie? Gdybyśmy na początku odśnieżyli mniej niż \(k\) metrów, to zajęłoby to tyle samo czasu (\(2s\)), ale każdy następny kurs musiałby się kończyć o tyle metrów dalej, o ile mniej odśnieżyliśmy na początku, przez co zajmowałby więcej czasu. Dodatkowo może się okazać, że będzie trzeba wykonać więcej kursów. Łącznie wykonamy \(\lceil \frac{s}{k} \rceil\) kursów.

    Oznaczmy przez \(c_{sta}(s)\) taki koszt dla odcinka długości \(s\), w którym mamy tylko jedną stację oraz rozpoczynamy i kończymy przy tej samej stacji. Skoro wykonujemy \(\lfloor \frac{s}{k} \rfloor\) pełnych kursów odśnieżających po \(k\) metrów oraz ostatni kurs odśnieżający \(s \bmod k\) metrów (co być może wynosi \(0\)), to korzystając z tożsamości \(k+2k+3k+\dots+xk=k(1+2+3+\dots+x)=k\frac{x(x+1)}{2}\) wychodzi koszt:

    \[ c_{sta}(s) = 2\left( k \frac{ \lfloor \frac{s}{k} \rfloor \left(\lfloor \frac{s}{k} \rfloor + 1\right) }{2} + \left(\lfloor\frac{s}{k}\rfloor + 1\right)\cdot(s \bmod k) \right) \]

  2. Zajmijmy się teraz przypadkiem, gdy mamy odcinek oraz jego dwie stacje i przechodzimy przez odcinek jednokrotnie (czyli chcemy w trasie dostać się z aktualnej stacji do następnej, chcemy odśnieżyć cały ten odcinek oraz wiemy, że już po tym nie będziemy w trasie wracać się do poprzedniej stacji). Oznaczmy taki koszt przez \(c_{one}(s)\).

    Można przedstawić taki fragment trasy między dwoma stacjami w trzech częściach:

    1. odśnieżamy fragment odcinka w pobliżu pierwszej stacji i kończymy kurs w tej samej stacji (być może wielokrotnie wracamy do tej stacji),
    2. przemieszczamy się z pierwszej stacji do drugiej, a ponieważ właśnie załadowaliśmy odśnieżarkę na pierwszej stacji, to możemy pomiędzy tymi stacjami odśnieżyć jeszcze \(k\) metrów,
    3. odśnieżamy fragment odcinka w pobliżu drugiej stacji i kończymy kurs w tej samej stacji (być może wielokrotnie wracamy do tej stacji).

    Nietrudno udowodnić takie przedstawienie, wystarczy zauważyć, że cokolwiek innego nie ma sensu.

    Mając już wzór na \(c_{sta}(s)\) i taką interpretację, po prostu trzeba dobrze podzielić odcinek na te trzy części:

    \[ c_{one}(s) = \min_{0 \leq p, k,\; p+k+q=s} c_{sta}(p) + s + c_{sta}(q) \]

    Daje to już sposób obliczenia wzoru \(c_{one}(s)\) w \(O(s-k)\), ale oczywiście preferowalibyśmy coś szybszego.

    Trzeba więc zrozumieć strukturę \(c_{sta}(p) + c_{sta}(q)\), aby znaleźć jej minimum. Sporo intuicji dostarcza wyprowadzenie wzoru na \(c_{sta}(p + 1) - c_{sta}(p)\), dzięki czemu możemy rozważać, czy opłaca się zamienić \((p, q)\) (spełniające \(p + q = s - k\)) na inne \((p + x, q - x)\), gdzie \(x\) jest liczbą całkowitą.

    Zastosujmy podejście, w którym mamy już wybrane kursy dla fragmentu odcinka o długości \(p\) i sprawdźmy, jak te kursy się zmieniają, gdy zwiększymy \(p\) o \(1\). Jeżeli zwiększamy \(p\) o \(1\) i \(p \bmod k \equiv 0\), to zwiększamy liczbę kursów o \(1\); nowym kursem odśnieżamy odcinek długości \(1\) (i wracamy), a każdy inny kurs, który już wcześniej istniał, zostaje przedłużony o jeden metr (zarówno w jedną, jak i w drugą stronę). W przeciwnym przypadku liczba kursów pozostaje taka sama i po prostu każdy kurs zostaje przedłużony o jeden metr (w obie strony). Ostatecznie, jeżeli zwiększamy \(p\) do \(p + 1\), to koszt zwiększa się o \(c_{sta}(p + 1) - c_{sta}(p) = 2 \lfloor \frac{p + 1}{k} \rfloor\), niezależnie od przypadku.

    Ciąg kolejnych różnic elementów \(c_{sta}\) okazuje się być bardzo regularny. Zaczynając od \(p = 1\), co \(k\) elementów różnica rośnie o \(2\). Z drobnej analizy własności tego ciągu można już bezpośrednio dojść do wniosku, że zawsze można wziąć \(p = \lceil \frac{s - k}{2} \rceil\) oraz \(q = \lfloor \frac{s - k}{2} \rfloor\), aby osiągnąć minimalną wartość \(c_{sta}(p) + c_{sta}(q)\) dla \(p + q = s - k\). Jest to całkiem prosty, choć nietrywialny do wyprowadzenia wniosek i wzór, który pozwala obliczyć wynik w czasie \(O(1)\)!

  3. Takie same wnioski można otrzymać, jeżeli zajmujemy się przypadkiem, w którym chcemy przejść przez odcinek dwukrotnie (czyli chcemy odśnieżyć cały odcinek, chcemy w całej trasie dostać się z aktualnej stacji do następnej i być może kontynuować trasę z następnej do jeszcze dalszych stacji, a później w pewnym momencie wrócić do tej aktualnej stacji).

    Wtedy przedstawiamy taki fragment trasy następująco:

    1. odśnieżamy fragment odcinka w pobliżu pierwszej stacji i kończymy kurs w tej samej stacji (być może wielokrotnie wracamy do tej stacji),
    2. przemieszczamy się z pierwszej stacji do drugiej, a ponieważ właśnie załadowaliśmy odśnieżarkę na pierwszej stacji, to możemy pomiędzy tymi stacjami odśnieżyć jeszcze \(k\) metrów,
    3. odśnieżamy fragment odcinka w pobliżu drugiej stacji i kończymy kurs w tej samej stacji (być może wielokrotnie wracamy do tej stacji),
    4. przemieszczamy się z drugiej stacji do pierwszej, a ponieważ właśnie załadowaliśmy odśnieżarkę na drugiej stacji, to możemy pomiędzy tymi stacjami odśnieżyć jeszcze \(k\) metrów.

    Dlatego:

    \[ c_{two}(s) = \min_{0 \leq p, k,\; p+2k+q=s} c_{sta}(p) + 2s + c_{sta}(q) = c_{sta}(\lceil\frac{s-2k}{2}\rceil) + 2s + c_{sta}(\lfloor\frac{s-2k}{2}\rfloor) \]

  4. Jeżeli wiemy, że chcemy zakończyć całą trasę na konkretnym odcinku, to fragment trasy odpowiadający za ten odcinek można przedstawić podobnie do dwustronnego przejścia odcinkiem (\(c_{two}\)), z tą różnicą, że przemieszczanie się z drugiej stacji do pierwszej można uciąć (po ostatnim odśnieżaniu już się nie ruszamy).

    W tej chwili nie wynika z dotychczasowych argumentów, że wystarczy wybrać \(p\) oraz \(q\) możliwie blisko siebie, bo teraz wybór \(q\) wpływa też na koszt przejścia, aby zakończyć trasę gdzieś w środku odcinka. Na przykład, jeżeli \(k=3\) oraz \(s=4\), to opłaca się z jednej stacji przejść do drugiej (i przy okazji odśnieżyć pierwsze trzy metry odcinka), a następnie zawrócić, odśnieżyć tylko jeden metr i zakończyć trasę, sumarycznym kosztem 5.

    Wciąż na pewno opłaca się dobrać takie \((p, q)\), które są sobie bliskie, to znaczy \(|p - q| < k\). Dowód: bez straty ogólności niech \(p \ge q + k\). Przekształcając lekko definicję, mamy \(c_{sta}(p) = c_{sta}(p - k) + 2p\) (oraz analogicznie dla \(q\)), z czego wynika, że zamiast \(c_{sta}(p) + c_{sta}(q)\) równie dobrze można wziąć \(c_{sta}(p - k) + c_{sta}(q + k)\).

    Jeżeli już mamy \(q \leq p < q + k\), to możemy zwiększać \(p\) o \(1\) oraz zmniejszać \(q\) o \(1\) bez pogarszania sumy \(c_{sta}(p) + c_{sta}(q)\), o ile liczba kursów (o dodatniej liczbie odśnieżanych fragmentów odcinka) wewnątrz \(c_{sta}(p)\) oraz \(c_{sta}(q)\) się nie zmieni.

    Dlatego optymalne jest, aby:

    • \(c_{sta}(p)\) oraz \(c_{sta}(q)\) miały tyle samo kursów lub liczba kursów różniła się o dokładnie \(1\),
    • \(p\) lub \(q\) było podzielne przez \(k\).

    Z tego wynika następujący wzór:

    • Jeżeli \(\lfloor\frac{s}{k}\rfloor\) jest parzyste, to wystarczy \(q = k \cdot \frac{\lfloor\frac{s}{k}\rfloor}{2}\).
    • Jeżeli \(\lfloor\frac{s}{k}\rfloor\) jest nieparzyste, to należy wziąć \(q = k \cdot \frac{\lfloor\frac{s}{k}\rfloor - 1}{2} + (s \bmod k)\).

Przechodząc z odśnieżania odcinków na odśnieżanie całej trasy

Wiedząc już, jaką formę przyjmuje optymalna trasa oraz jakie są optymalne czasy odśnieżania poszczególnych odcinków, możemy spróbować policzyć czas odśnieżania optymalnej trasy.

Niech:

  • \(o_i\) będzie czasem odśnieżenia \(i\)-tego odcinka, gdy przechodzimy przez niego jednostronnie,
  • \(t_i\) będzie czasem odśnieżenia \(i\)-tego odcinka, gdy przechodzimy przez niego dwustronnie,
  • \(f_i\) będzie czasem odśnieżenia \(i\)-tego odcinka, gdy na nim kończymy,
  • jeżeli jakiś z tych odcinków jest brzegowy, to trzeba pamiętać, by wtedy użyć wzoru na brzegowe odcinki \(c_{sta}(s)\).

Załóżmy, że zaczynamy ze stacji \(x\) (dla przypomnienia, zaczynamy z jednej z dwóch najbliższych stacji). Załóżmy też, że zaczynamy od odśnieżania w kierunku lewego brzegu drogi, a później odśnieżamy w kierunku prawego.

Wiemy już, że przez każdy odcinek na lewo od stacji \(x\) będziemy przechodzić dwustronnie, a odcinki na prawo od \(x\) będą kolejno najpierw jednostronnymi, później będzie jeden odcinek, na którym kończymy, a później kolejno dwustronnymi. Musimy więc jeszcze wybrać odcinek \(y\), w którym będziemy kończyć trasę.

Czas takiej trasy wynosi:

\[ t_1 + t_2 + \dots + t_{x-1} + o_x + o_{x+1} + \dots + o_{y-1} + f_y + t_{y+1} + t_{y+2} + \dots + t_n \]

Daje to już rozwiązanie brutalne, które sprawdza każde z \(O(n)\) wyborów \(y\) w czasie \(O(n)\) dla konkretnego dnia. Można to jeszcze przyspieszyć za pomocą sum prefiksowych, co daje złożoność \(O(nd)\).

Aktualizacje

Do tej pory staraliśmy się zignorować niedziałające stacje i po prostu zakładaliśmy, że mamy ciąg odcinków pomiędzy działającymi stacjami. Żeby sobie poradzić z niedziałającymi stacjami, możemy uznać, że niektóre odcinki będą wyłączone (będą miały wartości \(t_i\), \(o_i\), \(f_i\) równe \(0\)). Włączone będą tylko te odcinki, które sąsiadują lewym brzegiem z działającą stacją (lub jeżeli jest to brzegowy odcinek).

Dla takich odcinków, wartości \(t_i\), \(o_i\), \(f_i\) wyliczamy, wstawiając do \(c_{sta}\), \(c_{one}\), \(c_{two}\), \(c_{fin}\) różnicę pozycji działających stacji. Wtedy wzór na czas optymalnej trasy może pozostać taki sam.

Żeby w taki sposób aktualizować wartości odcinków, można utrzymywać zbiór działających stacji (na przykład w strukturze std::set w C++). Przy każdym pojedynczym dodaniu/usunięciu stacji ze zbioru działających stacji można w std::set znaleźć poprzednią/kolejną stację i wykonać stałą liczbę zmian wartości odcinków (jest to stała liczba zmian, ale samo znalezienie tych stacji trwa \(O(\log n)\)).

Sprowadziliśmy więc zadanie do postaci, w której wykonujemy operacje:

  • zmiany wartości pojedynczego odcinka,
  • znalezienia najlepszego \(y\) oraz wyliczenia kosztu trasy.

Z pomocą przychodzi drzewo przedziałowe, w którym modyfikujemy wartości w punkcie i zadajemy zapytanie o przedział. W wierzchołku takiego drzewa można utrzymywać:

  • sumę \(t_l + t_{l+1} + \dots + t_r\),
  • sumę \(o_l + o_{l+1} + \dots + o_r\),
  • najmniejszą sumę \(o_l + o_{l+1} + \dots + o_{y-1} + f_y + t_{y+1} + \dots + t_r\) (można tę sumę utrzymywać podczas łączenia dwóch wierzchołków, korzystając ze wszystkich trzech wartości w wierzchołku), zapiszmy to jako \(min\_oft\).

Wtedy, by wyliczyć optymalny czas trasy, wystarczy odczytać z przedziału \([1, x-1]\) sumę \(t_i\) i dodać ją do odczytanego \(min\_oft\) z przedziału \([x, n]\).

Całkowita złożoność rozwiązania to \(O((n + d + \sum z + \sum u) \log n)\).

Należy przy implementacji być ostrożnym z:

  • brzegowymi stacjami (co można częściowo rozwiązać za pomocą strażników),
  • policzeniem wyniku dla obu możliwych pierwszych stacji,
  • policzeniem wyniku dla obu możliwych kierunków trasy (co można rozwiązać, puszczając algorytm dwa razy, za drugim razem odwracając input).

Żeby w miarę sprawnie wyłapać wszelkie przypadki brzegowe, warto testować rozwiązanie, porównując jego wyniki do rozwiązania brutalnego.

 

Opis przygotowano w ramach projektu "Mistrzostwa w Algorytmice i Programowaniu - Uczniowie" - zadania finansowanego ze środków Ministerstwa Cyfryzacji.