Od deski do deski

Dzisiaj zajmiemy się zadaniem z Potyczek Algorytmicznych 2021.

Blokiem nazywamy co najmniej dwuelementowy ciąg liczb naturalnych, rozpoczynający się i kończący tą samą liczbą. Mówimy że ciąg jest ciekawy jeśli jest pusty lub gdy powstaje przez sklejenie ciekawego ciągu z blokiem. Zadanie polegało na policzeniu ile jest wszystkich n-elementowych, ciekawych ciągów, w których elementy są mniejsze niż m.

Zacznijmy od rozwiązania innego problemu. Spróbujmy sprawdzić czy podany ciąg jest ciekawy. Zrobimy nawet więcej. Dla każdego prefiksu ciągu sprawdzimy czy jest on ciekawy. Aby to uczynić, posłużymy się Zbiorem. W Zbiorze będziemy trzymać te wartości, o których wiemy, że jeśli ciąg skończy się właśnie nimi, to ciąg będzie ciekawy.

Algorytm działa następująco. Zaczynamy od pustego ciągu i pustego Zbioru. Pusty ciąg oczywiście jest ciekawy. Teraz dla każdego kolejnego elementu wykonujemy:

  • Jeśli element znajduje się w Zbiorze, to dany podciąg jest ciekawy
  • Jeśli element nie znajduje się w Zbiorze, to dany podciąg nie jest ciekawy
  • Jeśli poprzedni podciąg (bez tego elementu) był ciekawy, to dodaj element do Zbioru.

Zwróćmy uwagę, że do Zbioru dodajemy element jeśli wystąpił on zaraz po ciekawym podciągu. Jeśli teraz nasz ciąg zakończy się tym elementem, to podciąg od tego miejsca do końca będzie tworzyć blok i całość będzie tworzyć ciekawy ciąg bo jest ciekawym ciągiem z doklejonym do niego blokiem.

Jeśli zrozumieliśmy już ten algorytm, to teraz łatwo rozwiązać zadanie. Zrobimy to przy użyciu programowania dynamicznego:

I[n, s, T/F] – ilość ciągów długości n o elementach mniejszych od m, dla których nasz algorytm zakończy się ze Zbiorem o rozmiarze s oraz wynikiem T/F (T jeśli ciąg jest ciekawy i F jeśli ciąg nie jest ciekawy).

Wiedząc dokładnie jak algorytm działa, jesteśmy w stanie policzyć ile dokładnie jest takich ciągów. Zacznijmy od I[n, s, T]. Jedyny sposób, aby nasz algorytm zwrócił wynik T to taki, że ostatni element był w Zbiorze. Po takim elemencie nie ma możliwości aby Zbiór się powiększył (nawet jeśli ten element wrzucimy do Zbioru, to ten się nie powiększy, gdyż element już w Zbiorze był). Nie mamy żadnego ograniczenia na to czy poprzedni ciąg był ciekawy czy nie. Zatem:

I[n, s, T] = ( I[n-1, s, T] + I[n-1, s, F] ) s

Ciąg poprzedni musiał mieć n-1 elementów i Zbiór rozmiaru s. Nie interesuje nas czy był ciekawy czy nie — dlatego dodajemy do siebie obie wartości. Na końcu mnożymy wszystko przez s, bo ostatni element musi należeć do Zbioru, a Zbiór ma dokładnie s wartości.

Aby policzyć I[n, s, F] musimy rozważyć dwie możliwości. Albo właśnie zwiększyliśmy Zbiór, albo…. nie. Jeżeli zwiększyliśmy to poprzedni podciąg musiał być ciekawy, a zbiór musiał mieć s-1 elementów. Jeśli nie zwiększamy, to podciąg musiał nie być ciekawy, a zbiór musiał mieć już s elementów:

I[n, s, F] = I[n-1, s, F] (m – s) + I[n-1, s-1, T] (m – s + 1)

W obu przypadkach nowy element musiał być spoza Zbioru. W pierwszym przypadku jest (m – s) takich elementów, a w drugim przypadku jest ich (m – s +1).

Jeśli chodzi o przypadki brzegowe, to I[0, 0, T] należy ustawić na 1 (to jest analog dla naszego ciągu pustego, zbioru pustego, który jest ciągiem ciekawym) i resztę zostawić ustawioną na 0.

Back To Top