Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Wyprzedzanie”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie: jednym pasem jedzie n ciężarówek. Pasem równoległym ciężarówki wyprzedza Bitazar (zły brat bliźniak Bajtazara). Policja Bajtocka chce teraz ukarać Bitazara mandatem. Wysokość mandatu zależy od tego ile razy Bitozar mógł podczas wyprzedzania zjechać na swój pas (a tego nie zrobił). Policja dysponuje następującymi danymi: Pozycją ciężarówek w momencie w którym rozpoczęła się szarża Bitazara przeciwległym pasem, prędkościami poszczególnych ciężarówek, długością ciężarówek, prędkością Bitazara oraz odległością między ciężarówkami, która umożliwiłaby Bitazarowi bezpieczny powrót na właściwy pas. Ciężarówki nie wyprzedzają się nawzajem – jeśli dojadą do ciężarówki przed nią to zwalniają do takiej prędkości jaką ma ona.
Zadania tego typu rozwiązujemy za pomocą techniki, która kojarzy mi się z “miotłą po czasie”. Tworzymy następujące rodzaje zdarzeń:
- Ciężarówki i-ta dogania ciężarówkę i+1-szą
- Bitazar wyprzedza i-tą ciężarówkę
Z wszystkich tych zdarzeń wybieramy tę, która zdarzy się najwcześniej i ją obsługujemy. To znaczy jeśli ciężarówka i-ta dogoni ciężarówkę i+1-szą to zmniejszamy prędkość ciężarówki i-tej. Jeśli Bitazar wyprzedza i-tą ciężarówkę to sprawdzamy czy między nią a ciężarówką i+1-szą jest odpowiednio dużo miejsca aby Bitazar mógł wykonać manewr powrotu na właściwy pas. Zdarzenia obsługujemy dopóki są jeszcze jakieś zdarzenia (lub alternatywnie: gdy Bitazar wyprzedzi wszystkie ciężarówki). W dużym uproszczeniu jest to całe rozwiązanie.
Porozmawiajmy teraz o szczegółach implementacyjnych. Dla uproszczenia wyobraźmy sobie, że obsługujemy jedynie zdarzenia pierwszego typu (gdy ciężarówka dogania ciężarówkę). Czas takiego zdarzenia możemy obliczyć w następujący sposób. Liczymy różnicę odległości między ciężarówkami (pozycja ciężarówki i+1 – długość ciężarówki i+1 – pozycja ciężarówki i-tej) a następnie dzielimy ją przez różnicę prędkości tych ciężarówek. Tak otrzymany czas wrzucamy na kolejkę priorytetową wraz z indeksami ciężarówek (i oraz i+1). Oczywiście jeśli prędkość ciężarówki i+1-szej jest większa od prędkości ciężarówki i-tej to ta druga nigdy nie dogoni pierwszej i zdarzenie nie wrzucamy na kolejkę.
Jak obsłużyć zdarzenie pierwszego typu? Jeśli ciężarówka i-ta zwolniła, to ciężarówka i-1-sza dogoni ją wcześniej niż wcześniej policziyliśmy. Musimy obliczyć czas nowego zdarzenia i uaktualnić kolejkę priorytetową. Jeśli używamy kolejki priorytetowej z STLa to nie jesteśmy w stanie zrobić tego optymalnie. W takim wypadku zdarzenie po prostu dokładamy do kolejki z nowym czasem i ignorujemy przy ściąganiu zdarzenia starsze.
W jaki sposób liczyć czas zdarzenia po tym jak ciężarówka zwolniła? Jest kilka sposobów. Można na przykład dla każdej ciężarówki trzymać oprócz pozycji, czas w którym ciężarówka na tej pozycji była. W momencie gdy ciężarówka zwalnia, zapisujemy ten moment i pozycję na której w tej chwili ciężarówka się znajdowała.Następnie zmieniamy jej prędkość. Innym sposobem jest usunięcie ciężarówki i-tej oraz “wydłużenie” ciężarówki i+1-szej o długość ciężarówki i-tej. Inaczej mówiąc – będziemy ciężarówki i oraz i+1 traktowali jakby były jedną ciężarówką. Teraz zamiast sprawdzać “spotkanie” ciężarówki i-1-szej z i-tą, sprawdzamy moment spotkania ciężarówki i-1-szej z nową przedłużoną ciężarówką i+1-szą.
Czas zdarzenia dla Bitazara obliczamy analogicznie jak zdarzenia dla ciężarówek. Aby obsłużyć wyprzedzanie przez Bitazara, liczymy czas zdarzenia. Liczymy pozycję na której znajduje się w tym czasie ciężarówka i-ta oraz i+1-sza, a następnie liczymy odległość między nimi i sprawdzamy czy znajduje się pomiędzy nimi odpowiednia odległość.
Na koniec zostaje nam ostatni problem. Prędkości i czasy zdarzeń wyrażają się liczbami wymiernymi. Jeśli nie chcemy mieć problemy z niedokładnością zmiennych typu double, musimy zaimplementować własny typ danych typu ułamek. Licznik i mianownik ułamka powinien zmieścić się w long longu. Problemem może być w takiej sytuacji porównywanie dwóch ułamków ze sobą. Możemy to rozwiązać korzystając ze zmiennej typu __int128_t, implementując własne big numy albo korzystając z języka programowania Python.
