Omówienie zadania Stacje benzynowe (III etap XXXI OI)

Przypadek \(k = 2\)

W tym przypadku zadziała następujący algorytm zachłanny – rozważamy elementy ciągu \(a_i\) od lewej do prawej i dokładamy do wynikowego ciągu dany element, jeżeli różni się od ostatniego wziętego.

Przypadek \(k > 2\)

Niestety w ogólnym przypadku nie wystarcza zachłannie brać elementy jeżeli różnią się od ostatnich \(k - 1\) wziętych elementów. Można się o tym przekonać rozważając ciąg \(1, 2, 1, 3, 2\) dla \(k=3\). Dla niego najdłuższy poprawny podciąg to \(2, 1, 3, 2\). Jednakże nie ma równie długiego podciągu, który zaczyna się od \(1\), a więc jeżeli weźmiemy pierwszy element ciągu, to nie damy rady potem uzyskać już najlepszego możliwego ciągu.

Jest natomiast inne uogólnienie wcześniejszego podejścia zachłannego z przypadku \(k = 2\), które pozwala nam rozwiązać ogólny przypadek. W celu rozwinięcia tego ogólnego podejścia przyjrzyjmy się bliżej przypadkowi \(k = 2\).

Głębsza analiza przypadku \(k = 2\)

Podczas naszego rozwiązania konstruujemy ciąg \(b_1, b_2, \dots, b_l\) indeksów ciągu \(a_i\) taki, że \( a_{b_i} \neq a_{b_{i+1}}\) dla \(1 \leq i < l\). Kiedy rozważamy dołożenie do niego kolejnego indeksu \(j\), patrzymy, czy \(a_j \neq a_{b_l}\) i jeżeli tak jest, to jako \(b_{l+1}\) bierzemy \(j\). Zauważmy, że podczas rozszerzania ciągu \(b_i\) jedyne, co było dla nas istotne, to jego ostatni element. Jako że na koniec musimy podać długość uzyskanego ciągu \(b_i\), to musimy trzymać także długość ciągu. Możemy więc zamiast całego ciągu \(b_i\) utrzymywać tylko parę \((d, e)\), przy czym \(d\) to obecna długość ciągu \(b_i\), a \(e\) to indeks jego ostatniego elementu. Wtedy po dostawieniu \(a_j\) przechodzimy do stanu \((d + 1, j)\). Natomiast na koniec wystarczy odczytać uzyskaną długość ciągu z tej pary.

Nic nie stoi na przeszkodzie, byśmy utrzymywali więcej niż jeden stan. Spróbujmy dla każdego \(i \in \{1,\ldots,n\}\) wyznaczyć parę \((f(i), i)\), przy czym \(f(i)\) jest długością najdłuższego poprawnego podciągu ciągu \(a_1, \dots, a_n\) kończącego się na \(a_i\). Dla danego \(i\) możemy to zrobić rozważając każdy stan \((f(j), j)\) dla \(j < i\) oraz rozszerzyć z nich tę parę \((f(j), j)\), która ma największe \(f(j)\) wśród \(j\) takich, że \(a_i \neq a_j\). Zauważmy, że w takim podejściu możemy być pewni, że znajdziemy najlepszy podciąg, ponieważ rozpatrujemy wszystkie możliwe podciągi. W przypadku \(k = 2\) może to wydawać się nadmierne, ale okaże się to kluczowe podczas konstrukcji ogólnego rozwiązania.

Uogólnienie dla przypadku \(k > 2\)

Spróbujmy więc podobnie jak w przypadku \(k = 2\) utrzymywać stany postaci \((d, p_1, p_2, \dots, p_{k-1})\), przy czym \(d\) to długość danego ciągu \(b_i\), a \(p_1, \dots, p_{k-1}\) to jego \(k-1\) ostatnich elementów. Dostawienie elementu \(a_j\) jest analogiczne – patrzymy, czy \(a_j \neq a_{p_i}\) dla każdego \(i \in \{1,\ldots,k-1\}\). Jeżeli tak jest, to możemy przejść do stanu \((d + 1, p_2, \dots, p_{k-1}, j)\). Daje nam to wstępne rozwiązanie w złożoności \(O(n\cdot n^{k-1})\). Naszą główną bolączką jest rozważanie bardzo wielu potencjalnych stanów. Na szczęście okazuje się, że większość z nich nie jest dla nas istotna. Właśnie na ograniczeniu liczby przeglądanych stanów będzie opierać się nasze kolejne usprawnienie algorytmu.

Usprawnienie algorytmu

Rozważmy pewien ciąg indeksów \(b_1, \dots, b_l\) oraz jego dwa sąsiednie elementy \(b_i, b_{i+1}\). Zastanówmy się, jak duża może być przerwa między nimi. Wydaje się, że jeżeli byłaby ona dosyć duża, to powinien znaleźć się w niej taki element \(a_j\), że można by jego indeks wstawić do rozważanego ciągu, otrzymując poprawny ciąg \(b_1, \dots, b_i, j, b_{i+1}, \dots, b_l\). Ta intuicja jest dobra, o ile tylko zamiast dużej przerwy rozważymy przerwę dostatecznie różnorodną. Okazuje się, że jeżeli w ciągu \(a_{b_i + 1}, a_{b_i+2}, \dots, a_{b_{i+1} - 1}\) jest co najmniej \(2(k-1)+1\) różnych elementów, to da się w ten sposób powiększyć ciąg \(b\). Wynika to z faktu, że wystarczy by taki element \(a_j\) był różny od elementów \(a_{b_{i - k + 2}}, a_{b_{i-k+3}},\dots a_{b_i}, a_{b_{i+1}}, a_{b_{i+2}}, \dots, a_{b_{i+k-1}}\), a ponieważ tych elementów jest co najwyżej \(2(k-1)\), to w zbiorze \(2(k-1)+1\) różnych elementów na pewno znajdzie się co najmniej jeden różny od każdego z nich. W celu użycia powyższej obserwacji zmodyfikujemy nasz algorytm tak, że będziemy rozszerzali stan \((d, p_1, \dots, p_{k-1})\) o element \(a_j\) tylko jeżeli wśród kolejnych elementów \(a_{p_{k-1} + 1}, a_{p_{k-1}+2}, \dots, a_{j - 1}\) jest co najwyżej \(2(k-1)\) różnych elementów.

Druga optymalizacja polega na zauważeniu, że jeżeli dla dwóch różnych stanów \((d, p_1, \dots, p_{k-1})\) oraz \((d', p_1', \dots, p_{k-1}')\) zachodzi \(a_{p_i} = a_{p_i'}\) dla każdego \(i \in \{1,\ldots,k-1\}\), to wystarczy zachować tylko ten z nich, który ma większą wartość \(d\) lub \(d'\) (w przypadku remisu dowolny z nich).

Okazuje się, że jeżeli zastosujemy obydwie te optymalizacje, to złożoność naszego algorytmu zredukuje się do \(O(n \cdot \left( 2k-1 \right)^{k-1})\). Wynika to z tego, że dla ustalonego nowego elementu \(a_j\), którym chcemy przedłużyć stan \((d, p_1, \dots, p_{k-1})\), mamy co najwyżej \(2k-1\) możliwych wartości jakie może mieć \(a_{p_{k-1}}\), co najwyżej \(2k-1\) możliwych wartości jakie może mieć \(a_{p_{k-2}}\) i tak dalej, aż do \(a_{p_1}\). Natomiast ponieważ każda krotka \(p_1, \dots, p_{k-1}\), którą utrzymujemy, ma różny ciąg wartości \(a_{p_i}\), to dla danego elementu \(a_j\) rozpatrzymy co najwyżej \(\left(2k-1\right)^{k-1}\) stanów jako poprzednie.

Inne rozwiązania

Można także próbować implementować rozwiązania heurystyczne, które w inny sposób ograniczają liczbę stanów w programowaniu dynamicznym. Przy limitach z zadania niektóre z takich rozwiązań mogły uzyskiwać nawet maksymalną punktację.