Algorytm do tego wymyśliłem jeżdżąc takimi autostradami w praktyce. Najważniejsze to jechać środkiem! Jeśli trafimy na samochody przed nami, to patrzymy czy szybciej się je ominie z lewej, czy z prawej.

Ja chciałem powiedzieć, że rozwiązując to zadanie najbardziej dumny byłem z siebie w momencie, gdy wpadłem na pomysł jak je testować lokalnie. Mianowicie logika do jeżdżenia górą była zupełnie inna niż do jeżdżenia dołem, więc pomyślałem, że zrobię dwie wersje kodu - jedna, w której zabronię jeździć górą i jedna, w której zabronię jeździć dołem i będę porównywać ich outy na odpowiednio przesuniętych testach :P

Ale jest też trochę trikowa interakcja między lewym pasem a prawym. Czasem może być tak, że przerwa po prawej stronie jest zbyt krótka, żeby się w niej zmieścić, ale jak szybko ominiemy lewą stroną, to jeszcze wykorzystamy tą samą przerwę po prawej dalej.

Ja miałem 3 samochody, które pędziły sobie 3 liniami. Następnie sprawdzałem w czasie stałym, które zdarzenie nastąpi jako pierwsze: któryś z samochodów będzie musiał zwolnić; któryś z samochodów będzie mógł zjechać na inny pas. Następnie przechodziłem do tego wydarzenia i obsługiwałem. Jeśli jakiś samochód mógł zjechać na pas obok, to sprawdzał najpierw czy w ten sposób wyprzedzi samochód który już tam się znajduje i jeśli tak to zastępuje go, jednocześnie zostając na swojej linii (zostaje skopiowany).

Rozwiązanie choć wydawało mi się proste w koncepcji było bardzo brzydkie do implementacji. Nie udało mi się go zdebugować i nie wiem czy w algorytmie był błąd czy w implementacji.

@Tomek: nie wiem jakie dokładnie masz rozwiązanie (o dziwo nie domyśliłem się całego po Twoim opisie ;)), ale w moim kodzie nie ma zupełnie żadnej bezpośredniej interakcji pomiędzy lewym a prawym pasem. W swoim kodzie liczyłem dp[i] - najkrótszy czas, po którym jestem w stanie dojechać na i-te pole na środkowym pasie. Do następnego wolnego pola j na tym środkowym pasie albo dojeżdżam bezpośrednio (iff j=i+1) albo wymijam górą albo wymijam dołem. Na wymijanie górą i dołem mam dwa kompletnie różne kody z prawie zerową częścią wspólną logiki i oba to niezłe syfy. Aczkolwiek góra prostsza - w szczególności górę robię w O(n), a dół w O(n log n).

Ja robię całość w O(n).

Wyprzedzanie lewą stroną jest prostsze do ogarnięcia. Patrzymy na pierwszą kolumnę samochodów na lewym pasie:
1. Jeśli jeszcze nie wyprzedziliśmy tej kolumny, to jedyna opcja to jechać za nią.
2. Jeśli już wyprzedziliśmy całą tą kolumnę, to możemy o niej zapomnieć na zawsze, bo ona już nas nigdy nie dogoni. Kasujemy tą kolumnę, patrzymy na kolejną i wracamy do punktu 1.

Po prawej stronie patrzymy na pierwszą przerwę. Załóżmy na chwilę, że możemy taranować samochody za tą przerwą, i policzmy czas wyprzedzania:
3. Jeśli mamy gorszy czas niż lewą stroną, to już wiadomo, że wyprzedzamy lewą.
4. Jeśli mamy lepszy czas niż lewą stroną, i nikogo nie musimy taranować, to wyprzedzamy prawą.
5. Jeśli mamy lepszy czas niż lewą stroną, ale jednak kogoś musimy staranować, to znaczy że ta przerwa już nam się nigdy nie przyda, bo niezależnie którą stroną wyprzedzimy, ta przerwa już będzie za nami. Więc kasujemy tą przerwę na zawsze, patrzymy na kolejną, i wracamy do punktu 3.

"to znaczy że ta przerwa już nam się nigdy nie przyda," - łoooo, racja! To by mi wiele uprościło!

To ja mam chyba nk^2 log nk^2, z możliwym (chyba) syfnym zbiciem do nk log nk, ale zobaczymy czy poprawne :) (k to liczba pasów).

Tak w skrócie to chyba mam podobnie do tego co Krzysztof, tylko myślę o tym tak, że mam graf/dpka w którym stanem jest krotka (numer pola, numer pasa, mój numer pasa). No i teraz taki stan mi mówi, że jestem na pasie "mój numer pasa" w pozycji równoległej (po czasie t) do pola (numer pola, numer pasa), bo zauważam, że jak jadę jakimś pasem, to albo zmieniam pas od razu (czas zero), albo chcę trochę podjechać, a skoro chcę trochę podjechać to muszę jakieś nowe pole spotkać. Jak chcę trochę podjechać to znajduję pierwsze pole, które spotkam i tam przechodzę. No i Dijkstra po tym (stąd ten czas t). Podjechać tzn. albo jadę prędkością pasa, jeśli jest przede mną bezpośrednio samochodzik, albo z moją jeśli nie ma - to jest "do przodu, albo z prędkością pasa jeśli jest za mną, albo z prędkością zero jeśli nie ma - to jest "do tyłu".

Chyba się jednak tego nie da zbić :(