Omówienie zadania Wyprzedzanie (I etap XXX OI)

Podzadanie 1. (wszystkie \(v_i\) są równe)

Skoro wszystkie prędkości ciężarówek są równe, to odległości pomiędzy kolejnymi ciężarówkami nie zmieniają się w czasie. Bajtazar będzie zmieniał pas na lewy, gdy zbliży się do kolejnej ciężarówki, a na prawy, gdy tylko wystarczy tam dla niego miejsca. To oznacza, że Bajtazar zmieni pas na lewy przed pierwszą ciężarówką oraz przed każdą kolejną taką, że odległość pomiędzy nią a poprzednią jest niemniejsza od długości auta Bajtazara \(D\). Skoro ciężarówki na wejściu są posortowane rosnąco po początkach i nie nachodzą na siebie, to możemy dla każdej z nich w czasie stałym obliczyć odległość od poprzedniej i stwierdzić, czy Bajtazar wykona przed nią manewr zmiany pasa na lewy. Rozwiązanie to działa więc w czasie \(O(n)\).

Podzadanie 2. (ciąg \(v_i\) jest niemalejący)

Skoro kolejne ciężarówki są coraz szybsze, to nigdy nie nastąpi sytuacja dogonienia jednej ciężarówki przez drugą i ich sklejenia. W szczególności ciężarówki nigdy nie zmienią swojej prędkości.

Możemy więc, dla każdej ciężarówki, obliczyć czas zrównania się jej tyłu z przodem auta Bajtazara używając odpowiednio wzoru na prędkość (na razie nie przejmując się, którym pasem jedzie Bajtazar): \(t_i = \frac{x_i-d_i}{V-v_i}\).

Przecież tylko w tych momentach Bajtazar może zmienić pas na lewy. Dokładniej, musi zajść jeszcze jeden warunek – w momencie \(t_i\) Bajtazar musiał być na prawym pasie, tzn. odległość między ciężarówką \(i-1\) a ciężarówką \(i\) musiała być niemniejsza od długości auta Bajtazara. Tę odległość również możemy obliczyć, stosując odpowiednio wzór na prędkość. W czasie \(t_i\) Bajtazar znajdzie się na pozycji \(V \cdot t_i\), a ciężarówka \(i-1\) na pozycji \(x_{i-1} + v_{i-1} \cdot t_i\). Wystarczy więc sprawdzić, czy różnica między tymi odległościami wynosi co najmniej \(D\).

W sposób opisany powyżej sprawdzamy dla każdej ciężarówki (poza pierwszą – przed nią na pewno zmienimy pas), czy Bajtazar zmieni przed nią pas na lewy i wypisujemy liczbę tych zmian pasa. Sprawdzenie każdej ciężarówki możemy wykonać w czasie stałym, więc rozwiązanie polegające na zliczeniu tych zmian działa w czasie \(O(n)\).

Podzadanie 3. (\(n \leq 1000\))

Zaczniemy od prostej obserwacji – Bajtazar zmieni pas na lewy dokładnie tyle samo razy, co na prawy (ponieważ zaczyna i kończy na tym samym pasie). Możemy więc liczyć zmiany pasa na prawy. Gdyby ciężarówki się nie sklejały, wystarczyłoby dla każdej ciężarówki \(i\) policzyć czas zrównania się jej przodu z tyłem auta Bajtazara i sprawdzić, czy wtedy Bajtazar zmieści się na prawym pasie (jeśli tak, to wiemy, że zmieni pas). Jeśli w tym momencie Bajtazar nie może wjechać przed ciężarówkę \(i\), ponieważ zahaczyłby swoim autem o kolejną, to później tym bardziej nie zmieści się między tymi ciężarówkami, ponieważ jest szybszy od każdej z nich. Wystarczyłoby więc podobnie jak w poprzednim podzadaniu policzyć czasy \(T_i\) zrównywania się przodu ciężarówki \(i\) z tyłem auta Bajtazara, a następnie dla każdego z nich obliczyć pozycje Bajtazara i ciężarówek \(i\), \(i+1\) oraz sprawdzić, czy Bajtazar zmieści się wtedy między nie.

Można jednak zauważyć, że pomimo sklejania się ciężarówek, wciąż jedynymi momentami, kiedy Bajtazar potencjalnie będzie mógł zmienić pas na prawy po wyprzedzeniu ciężarówki \(i\) jest moment \(T_i\):

• Jeśli ciężarówka \(i\) do momentu \(T_i\) nie dogoniła ciężarówki \(i+1\), to nic się nie zmienia – wystarczy sprawdzić, czy Bajtazar zmieści się miedzy te ciężarówki.
• Jeśli ciężarówka \(i\) dogoniła ciężarówkę \(i+1\) przed momentem \(T_i\), to Bajtazar na pewno przegonił ciężarówkę \(i\) już po ich sklejeniu, bo przed sklejeniem jej prędkość się nie zmieniała, a czas \(T_i\) jest czasem przegonienia ciężarówki \(i\) przez Bajtazara przy założeniu niezmienionej, stałej prędkości ciężarówki. Zatem w takim wypadku Bajtazar nie zmieni pasa na prawy po wyprzedzaniu \(i\)-tej ciężarówki, bo ta będzie już wówczas złączona z ciężarówką \(i+1\).

O ile czasy \(T_i\) możemy obliczyć w czasie stałym, to pozycji ciężarówek już nie – nie wiemy bowiem, czy i kiedy (potencjalnie wielokrotnie) ciężarówki będą zmieniać swoją prędkość w związku ze sklejeniem. Możemy jednak to zrobić (obliczyć pozycje ciężarówki \(i\) w danym momencie) w czasie liniowym, obliczając po kolei pozycje ciężarówek \(n, n-1, n-2, \ldots\) Ostatnia ciężarówka w momencie \(T_i\) będzie na pozycji \(x_n + v_n T_i\). Przedostatnia na pozycji min\((x_{n-1} + v_{n-1} T_i, \text{pozycja \(n\)-tej ciężarówki}-d_n)\), ponieważ jeśli miałaby wyprzedzić \(n\)-tą ciężarówkę, to zamiast tego sklei się z nią i będzie jechać tuż za nią. Ogólnie, ciężarówka \(j\) będzie na pozycji min\((x_j + v_j T_i, \text{pozycja ciężarówki \(j+1\) pomniejszona o jej długość } d_{j+1})\).

Rozwiązanie więc polega na obliczeniu czasów \(T_i\) i dla każdego z nich znalezieniu (liniowo) pozycji ciężarówek \(i, i+1\) oraz na tej podstawie stwierdzeniu, czy Bajtazar zmieści się między tymi ciężarówkami i wykona zmianę pasa na prawy. Rozwiązanie działa więc w czasie \(O(n^2)\).

Rozwiązanie wzorcowe

W rozwiązaniu wzorcowym również wykorzystamy fakt, że wystarczy sprawdzić dla każdego \(i\), czy w momencie \(T_i\) Bajtazar jest w stanie wjechać między ciężarówki \(i, i+1\). Będziemy trzymać zbiór wydarzeń dwóch typów, posortowany chronologicznie:

• Typ 1.: moment \(T_i\), w którym sprawdzamy, czy Bajtazar zmieści się między ciężarówkami \(i,i+1\).
• Typ 2.: moment \(t_i\), w którym ciężarówka \(i\) dogania kolejną, w efekcie czego następuje scalenie.

Inicjalizacja zbioru
W czasie stałym dla każdego \(i\) obliczamy momenty \(T_i\) wydarzeń typu 1. (tak samo, jak w poprzednim podzadaniu) oraz momenty \(t_i\) wydarzeń typu 2., biorąc pod uwagę jedynie początkowe prędkości ciężarówek, przy czym, jeśli ciężarówka \(i+1\) jest początkowo szybsza od ciężarówki \(i\) to nie wrzucamy takiego wydarzenia (bo o jakim dogonieniu możemy tu mówić?) do naszego zbioru.

Algorytm
Dopóki nie obsłużymy wszystkich wydarzeń typu 1., pobieramy następne (o najmniejszym czasie) wydarzenie ze zbioru i je obsługujemy w sposób zależny od jego typu (opisany poniżej).

Obsługa wydarzenia typu 2.
Musimy obsłużyć fakt dogonienia kolejnej ciężarówki przez ciężarówkę \(i\). Chcąc je scalić, możemy usunąć \(i\)-tą i sztucznie zwiększyć długość tej drugiej o długość \(i\)-tej. Tu pojawia się jednak problem – jaki jest numer kolejnej ciężarówki? Nie zawsze jest to \(i+1\), bo wcześniej mogły już nastąpić jakieś scalenia, w wyniku których usunęliśmy ciężarówkę \(i+1\) (scaliliśmy ją z kolejnymi). Możemy to rozwiązać, na przykład trzymając dwukierunkową listę wskaźnikową, która będzie dla każdej nieusuniętej ciężarówki trzymać numery poprzedniej i kolejnej nieusuniętej ciężarówki. W momencie usuwania jakiejś ciężarówki zmieniamy wskaźniki wyłącznie następnej i poprzedniej ciężarówki, więc czas pojedynczej operacji na naszej liście jest stały. Poprzedniej ciężarówki (o numerze powiedzmy \(j\)) potrzebujemy, aby zmienić czas \(t_j\) odpowiadającego jej wydarzenia typu 2. Zamiast zmieniać czas tego wydarzenia, możemy dodać nowe wydarzenie typu 2. ze zaktualizowanym czasem, który będzie niewiększy od poprzedniego, więc właśnie wrzucone wydarzenie obsłużymy wcześniej. Później, gdy będziemy je obsługiwać, zaznaczymy w tablicy wartości boolowskich, że dla ciężarówki \(j\) obsłużyliśmy już wydarzenie typu 2., dzięki czemu przy rozpatrywaniu kolejnego wydarzenia typu 2. dla ciężarówki \(j\) będziemy mogli je po prostu zignorować (traktować tak, jakby zostało ze zbioru usunięte). Zauważmy, że sklejenie \(i\)-tej ciężarówki z następną zmienia tylko ten jeden przewidywany czas sklejenia, więc łącznie takich zmian będzie maksymalnie \(n-1\) (tyle, co złączeń ciężarówek).

Obsługa wydarzenia typu 1.
Musimy odpowiedzieć na pytanie, czy w momencie \(T_i\) odległość między ciężarówką \(i\) a ciężarówką \(i+1\) wynosi co najmniej \(D\). Po pierwsze, sprawdzamy, czy ciężarówki \(i\) i \(i+1\) są sklejone. W tym celu wystarczy sprawdzić, czy obsłużyliśmy już wydarzenie typu 2. dla ciężarówki \(i\) (czyli odczytać wartość z tablicy aktualizowanej przy obsłudze wydarzeń typu 2.). Jeśli ciężarówki są sklejone, to Bajtazar oczywiście nie zmieści się między nimi. W przeciwnym wypadku zauważmy, że pomiędzy żadnymi dwoma kolejnymi wydarzeniami pobieranymi ze zbioru nie zmieni się prędkość żadnej z ciężarówek i nie będzie żadnych sklejeń. To pozwala w standardowy sposób policzyć, gdzie ciężarówki \(i, i+1\) będą w momencie \(T_i\) (tutaj traktujemy sklejone dotychczas ciężarówki jako jedną) i sprawdzić, czy Bajtazar zmieści się między nimi.

Złożoność czasowa
Wydarzeń typu 1. i 2. mamy liniowo wiele, a obsługa każdego z nich zajmuje czas logarytmiczny (operacje na zbiorze), więc złożoność całego rozwiązania wynosi \(O(n\log n)\).