Omówienie zadania Meteory (III etap XXIX OI)

Bajtazar stoi sobie na osi liczbowej w punkcie \(0\). Na oś tę upadają meteory: \(i\)-ty z nich na punkt \(x_i\) w momencie \(t_i\). Chcemy pomóc Bajtazarowi uniknąć zderzenia z meteorami, a najlepiej żeby znalazł się jak najdalej od każdego z nich w momencie spadania. W tym celu możemy mu podpowiadać jak biegać w lewo i w prawo, żeby był od meteorów jak najdalej (Bajtazar może biegać z maksymalną prędkością jednej jednostki odległości na jednostkę czasu).

Analiza zadania

Sytuację możemy reprezentować na dwuwymiarowej płaszczyźnie, gdzie \(i\)-ty meteor jest reprezentowany przez punkt o współrzędnych \((x_i,t_i)\). Początkowa pozycja Bajtazara to punkt \((0,0)\). Bajtazar albo może stać, albo biegać z maksymalną prędkością (wolniej się nie opłaca, bo można to zastąpić przez szybszy bieg plus chwila stania). Wobec tego na płaszczyźnie jego droga jest krzywą złożoną z odcinków pionowych oraz nachylonych pod kątem \(45^\circ\) w lewo lub w prawo. Co więcej, można pokazać, że punkty \((x,t)\), w których opłaca się być Bajtazarowi o całkowitych wartościach \(t\) mają liczby \(x\) całkowite lub będące ułamkiem o mianowniku 2.

Chcemy znaleźć taką krzywą, która maksymalizuje odległość (poziomą) od meteorów. Możemy w tym celu użyć wyszukiwania binarnego po wyniku. Załóżmy, że chcemy sprawdzić, czy odpowiedź jest większa lub równa od jakiegoś \(d\). Oznacza to, że nasza droga nie może przecinać poziomych odcinków długości \(2d\), których środkami są meteory, czyli otwartych odcinków o końcach \((x_i-d,x_i+d)\) na wysokości \(t_i\).

Intuicja podpowiada nam, że do takiego geometrycznego zadania przyda nam się zamiatanie. Idea jest taka, żeby iść w górę po czasie i pamiętać przedziały, na których może znajdować się Bajtazar.

W chwili \(T=0\) mamy tylko jeden jednopunktowy przedział: \([0,0]\). Jeżeli w pewnym momencie \(T_1\) Bajtazar może znajdować się w przedziale \([a, b]\), to w chwili \(T_2 > T_1\) (jeśli w międzyczasie nie spadł żaden meteor) ten przedział rozszerza się do \([a-\Delta, b+\Delta]\) dla \(\Delta = T_2-T_1\). Ogólniej: jeśli Bajtazar może znajdować się w chwili \(T_1\) w sumie rozłącznych przedziałów \(\bigcup_i [a_i,b_i]\), to w chwili \(T_2\) będzie to suma \(\bigcup_i [a_i-\Delta,b_i+\Delta]\), przy czym musimy wykonać tu ewentualne scalenie przedziałów, które zaczęły na siebie nachodzić (aby znowu były rozłączne).

W chwili \(t_i\), w której spadł meteor, z sumy przedziałów będziemy musieli wyrzucić kawałek zabroniony przez meteor, zatem wyrzucamy przedział \((x_i-d,x_i+d)\).

Jeżeli po przeanalizowaniu wszystkich meteorów, suma przedziałów, w których może znaleźć się Bajtazar, jest niepusta, to istnieje ścieżka o odległości co najwyżej \(d\).

Podzadanie 3

Ta analiza sugeruje następujące rozwiązanie. Na miotle będziemy trzymać listę rozłącznych domkniętych przedziałów; początkowo na tej liście znajduje się jedynie przedział \([0,0]\). Rozważamy meteory w kolejności spadania. Załóżmy, że rozważamy meteor, który spadł \(\Delta\) jednostek czasu po poprzednim (albo po chwili 0, jeśli nie było poprzedniego meteoru). Najpierw wszystkie przedziały na liście rozszerzamy w lewo i w prawo o \(\Delta\), a następnie przeglądamy tę listę, złączając nachodzące na siebie przedziały, tak żeby znowu uzyskać listę rozłącznych przedziałów. W końcu z listy tej wycinamy przedział zabroniony przez meteor, czyli otwarty przedział \((x-d, x+d)\).

Jeżeli w którymś momencie algorytmu lista zrobi się pusta, to do wyszukiwania binarnego zwracamy ,,nie”, a jeśli przeanalizowaliśmy wszystkie meteory, to zwracamy ,,tak”.

Po każdym wyrzuceniu otwartego przedziału z meteoru możemy co najwyżej jeden przedział podzielić na dwa, więc po \(n\) takich uaktualnieniach będziemy mieć co najwyżej \(n\) przedziałów na naszej liście. Zatem dla każdego meteoru analiza tej listy będzie działać w czasie \(O(n)\).

Zatem całkowita złożoność rozwiązania to jest \(O(n^2 \log W)\), ponieważ mamy \(n\) meteorów do przeanalizowania i w każdym z nich mamy \(O(n)\) operacji na liście przedziałów, zaś czynnik logarytmiczny pochodzi z wyszukiwania binarnego (przy czym \(W\) oznacza maksymalną współrzędną).

Rozwiązanie wzorcowe

Widać, że długi czas zajmuje aktualizacja miotły, spróbujmy ją zatem przyspieszyć. Pomysł jest taki, żeby przedziałów nie reprezentować w postaci \([a, b]\), ale niejawnie w postaci dolnych wierzchołków kwadratów, których te przedziały są przekątnymi. Dzięki czemu takiego punktu nie będziemy musieli aktualizować przy zwiększaniu wartości czasu.

Czyli jeśli mamy punkt \((x,t)\) oraz miotłę znajdującą się w momencie \(T\) (dla \(T > t\)), to ten punkt reprezentuje na miotle przedział \([x-(T-t), x+(T-t)]\).

Zakładamy, że w każdej chwili wszystkie przedziały generowane na miotle przez punkty są rozłączne. Jednak w pewnym momencie, gdy zwiększamy \(T\), niektóre przedziały mogą się ze sobą zetknąć. Pomysł jest więc taki, żeby wychwycić ten moment i zastąpić punkty generujące te przedziały jednym punktem, który generuje przedział będący ich sumą.

Będziemy utrzymywać kolejkę priorytetową, do której będziemy wrzucać dwa typy zdarzeń:

• upadek meteorytu,

• zetknięcie się przedziałów na miotle.

Ten drugi rodzaj zdarzenia może nastąpić tylko dla punktów, które sąsiadują ze sobą na miotle, i łatwo dla nich wyznaczyć wzór, który powie nam, w jakim czasie one się zetkną. Zatem zawsze, gdy będziemy uaktualniali przedziały na miotle, będziemy musieli również na kolejkę wrzucać wszystkie zdarzenia odpowiadające zetknięciom się przedziałów dla sąsiadujących punktów na miotle.

Aby obsłużyć zdarzenie meteoru, również możemy go zaprezentować w postaci punktu. Jeżeli punkty na miotle będziemy trzymać w strukturze danych set, to za pomocą operacji lower_bound będziemy mogli w czasie \(O(\log n)\) znaleźć poprzednik i następnik punktu, dzięki czemu szybko wyznaczymy potencjalne przedziały, które są przecinane przez meteor. Na podstawie ich punktów generujemy przedziały, przecinamy je przez meteor i z przedziałów powstałych po przecięciu znowu generujemy punkty i wrzucamy je na miotłę.

Tak więc każde zdarzenie będzie obsłużone w czasie \(O(\log n)\), zatem sumaryczny czas rozwiązania to \(O(n \log n \log W)\).

Można równie zaproponować alternatywne uaktualnianie miotły bez zdarzeń dla złączeń przedziałów, scalając przedziały leniwie w momencie pokrywania ich przez meteor. A jako trudniejszy problem proponujemy zastanowić się, jak rozwiązać zadanie meteory w czasie \(O(n \log n)\), czyli bez wyszukiwania binarnego po wyniku.

Podzadanie 2

Jeśli \(t_i=T\) dla wszystkich \(i\), to wszystkie meteory spadają w tym samym momencie. Bajtazar do tego momentu może znaleźć się w przedziale \([-T,T]\). Wystarczy zatem znaleźć w tym przedziale punkt leżący najdalej od wszystkich meteorów (rozważamy tutaj wszystkie punkty postaci \((x_i+x_{i+1})/2\) leżące w \([-T,T]\) oraz punkty \(-T\) i \(T\)).

Złożoność czasowa tego rozwiązania to \(O(n\log n)\).

Podzadanie 1

Jeśli wprowadzimy ograniczenie \(t_i \leq T\), to droga Bajtazara na płaszczyźnie będzie zawierać się w prostokącie \([-T,T] \times [0,T]\), przy czym rozważamy punkty postaci \((x/2,t)\) dla całkowitych \(x\), \(t\). Zatem mamy \(4T^2+O(T)\) punktów w prostokącie.

Dla każdego punktu możemy wyznaczyć poziomą odległość od najbliższego meteoru. Można to zrobić w czasie \(O(nT)\), jeśli każdy meteor rozważymy osobno, lub w czasie \(O(n\log n + T^2)\), jeśli meteory o tej samej wartości \(t_i\) posortujemy po \(x_i\) i przejrzymy je po kolei.

Mając odległości, prostym programowaniem dynamicznym w czasie \(O(T^2)\) wyznaczymy ścieżkę Bajtazara, która maksymalizuje odległość punktów, przez które przechodzi.