Omówienie zadania Impreza krasnali 2 (III etap XXIX OI)

Zadanie jest modyfikacją zadania Impreza krasnali z I etapu Olimpiady. W oryginalnej wersji \(i\)-ta liczba z wejścia mogła opisywać wysokość czapki na pozycji albo \(i-1\), albo \(i+1\); w tej wersji może opisywać pozycje \(i-1\), \(i\) lub \(i+1\). Rozwiązanie wzorcowe oryginalnego zadania (które opierało się na podziale ciągu na dwie części w zależności od parzystości indeksów) tu nie zadziała. Potrzebujemy trochę ogólniejszego rozwiązania.

Analiza zadania

Na początek sprawdzamy globalny warunek, że żeby rozwiązanie mogło istnieć, to dla każdej wartości w ciągu musi istnieć przedział pozycji o długości 3 poza którym ta wartość nie występuje.

Ponadto, jeśli wartość pojawia się więcej niż raz, to wymusza pewne sytuacje:

• \(h_i = h_{i+1} = h_{i+2}\) powoduje, że krasnale \(i\), \(i+1\) i \(i+2\) widzą czapkę \(i+1\);

• \(h_i = h_{i+2}\) powoduje, że krasnale \(i\) i \(i+2\) widzą czapkę \(i+1\);

• \(h_i = h_{i+1}\) powoduje, że krasnale \(i\) i \(i+1\) albo widzą czapkę \(i\), albo widzą czapkę \(i+1\).

Zauważamy też, że jeśli w ciągu pojawiło się \(k\) różnych wartości, to możemy zliczyć, ile jest możliwości ustawienia tych wartości w permutacji, a pozostałe \(n-k\) wolnych miejsc zawsze uzupełnimy na \((n-k)!\) sposobów wartościami niewystępującymi w ciągu.

Programowanie dynamiczne

Teraz możemy zrobić programowanie dynamiczne, w którym wypełniamy tabelkę \(dp[i,a,b] =\) liczba możliwości ustawienia wartości z ciągu, na pozycjach od \(i+1\) do \(n\), jeśli krasnal na \(i\)-tej pozycji widzi czapkę \(i+b\) oraz krasnal na \((i-1)\)-szej pozycji widzi czapkę \(i+a\) (dla \(-1 \leq a, b \leq 1\)).

Wartość \(dp[i,a,b]\) obliczamy, iterując po możliwościach \(c\) (\(-1 \leq c \leq 1\)) dla krasnala \(i+1\), który może widzieć czapkę \(i+c\). Dla każdej możliwości testujemy kompatybilność zmiennych \(a, b, c\) (np. jeśli wynika z nich, że pewne dwa krasnale widzą tę samą czapkę, to ich wartości w ciągu muszą być równe), jak również kompatybilność z sytuacjami wymuszonymi. W przypadku kompatybilności do wyniku dodajemy \(dp[i+1,b,c]\).

Każdy z \(9n\) stanów wyliczamy w czasie stałym, zatem programowanie dynamiczne, jak i całe zadanie rozwiązujemy w czasie \(O(n)\).

Na marginesie warto dodać, że pierwotną wersję zadania również możemy rozwiązać przy pomocy programowania dynamicznego. W opisanym tutaj algorytmie wystarczy zmienić, że wybór wartości \(c\) jest ograniczony do liczb \(-1\) i \(1\).