Omówienie zadania Flappy bird (I etap XXIV OI)

Problem

W zadaniu rozważamy popularną grę Flappy Bird. Początkowo bohater gry (ptaszek), znajduje się w punkcie \((0, 0)\) i chce dotrzeć do jakiegokolwiek punktu o pierwszej współrzędnej równej \(X\). W każdym ruchu ptaszek porusza się o jedną jednostkę w prawo oraz o jedną jednostkę w górę lub w dół. Jeśli klikniemy w ekran, wtedy ptaszek porusza się o wektor \((+1, +1)\), w przeciwnym przypadku przesuwa się o wektor \((+1, -1)\). Na drodze stoi \(n\) przeszkód, \(i\)-ta z nich rozciąga się z jednej strony od podłoża do punktu \(a_i\), zaś z drugiej strony od punktu \(b_i\) do sufitu. Chcemy obliczyć, w jakiej minimalnej liczbie kliknięć, można przeprowadzić ptaszka przez \(X\) jednostek czasu, omijając przeszkody.

Początkowe obserwacje

Obserwacja 1: Z każdym ruchem w prawo ptaszek porusza się w górę lub w dół (nie może zostać na tym samym poziomie). Zatem parzystości składowych (poziomej i pionowej) zawsze są takie same. Innymi słowy – nie da się osiągnąć takiego punktu \((x, y)\), że \(x\) i \(y\) są różnej parzystości.

Obserwacja 2: Jeśli startujemy z punktu \((x, y)\) i wykonujemy \(d\) ruchów, to osiągalne są takie punkty \((x + d, y')\), że \(y' \in [h - d; h + d]\) (z dokładnością do odpowiednich parzystości).

Rozwiązanie wolne

Na bazie drugiej obserwacji możemy ograniczyć planszę do punktów potencjalnie osiągalnych przez ptaszka: \[\{(x,y) \mid (0 \le x \le X) \land (|y-x| \le x) \land (x - y \equiv 0 \pmod{2}) \}\] Poniżej przedstawiono potencjalnie osiągalne punkty dla \(X = 4\).

Spośród tych punktów wybierzmy te, które nie znajdują się na przeszkodach.

Jeśli na rysunku dorysujemy jeszcze potencjalne przejścia pomiędzy punktami, to otrzymamy strukturę przypominającą graf. Zatem zinterpretujmy problem postawiony w zadaniu jako problem grafowy. Wierzchołkami są potencjalnie osiągalne punkty, które nie leżą na żadnej przeszkodzie. Zaś z każdego punktu \((x,y)\) wychodzą co najwyżej dwie krawędzie:

o koszcie 0 do \((x + 1, y - 1)\),
o koszcie 1 do \((x + 1, y + 1)\).

Naszym celem jest znalezienie ścieżki o minimalnym koszcie z \((0,0)\) do dowolnego punktu o współrzędnej \(x\) równej \(X\). Możemy to zrobić na dwa sposoby. Pierwszym jest algorytm Dijkstry, który standardowo działa w czasie \(O(V \log V)\), gdzie \(V\) to liczba wierzchołków grafu. Jeśli zauważymy, że mamy tylko dwa możliwe koszty krawędzi, wtedy możemy zaimplementować algorytm w czasie \(O(V)\). Inną możliwością rozwiązania tego problemu jest zauważenie, że ten graf jest acykliczny, więc możemy liczyć odległości od \((0,0)\) dynamicznie, przeglądając wierzchołki warstwami od lewej do prawej. W naszym przypadku \(V\) jest rzędu \(O(X^2)\).

Rozwiązanie wzorcowe

Okazuje się, że ze współrzędnych punktu możemy wywnioskować odległość do niego. Załóżmy, że chcemy dojść z punktu \((0,0)\) do \((x,y)\) (zakładamy, że \((x,y)\) jest osiągalne, czyli na pewno \(y \ge -x\)). Wtedy, jeśli nie wzbijemy się ani razu, to wylądujemy w punkcie \((x, -x)\). Mamy \(x\) okazji na podniesienie naszej finalnej wysokości o \(2\). Zatem musimy skorzystać z niej dokładnie \(\frac{x+y}{2}\) razy. Tym samym, jest to nasz szukany koszt. W takim razie od teraz szukamy najniższego osiągalnego punktu na \(X\)-owej współrzędnej. Skoro nie interesuje nas minimalny koszt, lecz w zupełności wystarczy osiągalność, to możemy się zastanowić, jak dokładnie wygląda struktura tego, co jest osiągalne na danej \(x\)-owej współrzędnej.

Po pierwsze, można zauważyć, że wszystkie osiągalne wierzchołki na danej \(x\)-owej współrzędnej mają tę samą parzystość (na mocy pierwszej obserwacji). Po drugie, osiągalne wierzchołki na ustalonym \(x\) są spójnym przedziałem, jeśli pominąć by wierzchołki, które są nieosiągalne ze względu na parzystość. Pokazuje to prosty dowód indukcyjny.

Załóżmy, że na współrzędnej \(x_i\) (na której to znajduje się \(i\)-ta przeszkoda) osiągalne są punkty \((x_i, y_1), (x_i, y_1 + 2), \ldots, (x_i, y_2)\). Chcemy wyznaczyć punkty osiągalne na współrzędnej \(x_{i+1} = x_{i} + d\). Punkty, do których można doskoczyć na współrzędnej \(x_{i+1}\) to: \((x_{i+1}, y_1 - d), (x_{i+1}, y_1 - d + 2), \ldots, (x_{i+1}, y_2 + d)\). Jednak na \(x_{i+1}\) jest przeszkoda \((a_{i+1}, b_{i+1})\). Zatem współrzędne \(y\) osiągalnych punktów należą do przecięcia przedziałów \([y_{1}-d; y_{2}+d]\) i \([a_{i+1} + 1; b_{i+1}-1]\). Pamiętajmy, żeby zachować warunek parzystości. Można sobie z tym poradzić modyfikując nasze przeszkody. Jeśli \(a_{i+1}\) jest złej parzystości, to podnosimy dolną przeszkodę o \(1\). Podobnie robimy dla górnej przeszkody.

Pokazaliśmy, że punkty osiągalne na współrzędnych \(x\) tworzą spójne przedziały (z dokładnością do parzystości współrzędnych). Na początku (na współrzędnej \(x=0\)) osiągalny jest jeden punkt, w którym zaczynamy grę, zatem początkowy przedział osiągalnych wartości \(y\) to \([0; 0]\). Następnie przeglądamy kolejne współrzędne \(x\) (w rosnącej kolejności – od lewej do prawej), na których znajdują się przeszkody, utrzymując przedział osiągalnych punktów. Jeśli w którymś momencie uzyskamy pusty przedział, wtedy odpowiadamy NIE. Jeśli natomiast dojdziemy do końca, wtedy najmniej ruchów wykonamy wybierając jako końcowe położenie najniższy punkt. Jeśli ten punkt ma współrzędne \((X, y_k)\), to odpowiedzią jest \(\frac{X + y_k}{2}\) (jak wspominaliśmy wcześniej).

Przejście pomiędzy kolejnymi przeszkodami (obliczenie przedziału wartości osiągalnych) zajmuje czas stały. Wszystkich przeszkód na wejściu jest \(n\), zatem otrzymujemy rozwiązanie \(O(n)\). Przeszkody przeglądamy w kolejności rosnącej współrzędnej \(x\), czyli tak jak podano na wejściu.