Ciągi i łańcuchy

Tym razem omówimy dwa zadania z IX International Autumn Tournament in Informatics, który odbył się w listopadzie 2017 roku w Szumem w Bułgarii.

Zadanie (Ciągi). Dane są trzy dodatnie liczby całkowite $n,m$ i $k. |$ Należy obliczyć liczbę niemalejących ciągów długości $n$ o wartościach będących liczbami całkowitymi z przedziału $[1;m],$ w których żadna wartość nie występuje więcej niż $k$ razy. Przykład: dla $n = 4,m$ i $k = 2$ poprawną odpowiedzią jest $6.$ Poprawnymi ciągami są: $|(1,1,2,2),(1,1,2,3),(1,1,3,3),(1,2,2,3),(1,2,3,3)$ oraz $(2,2,3,3).$

Rozwiązanie $|O$
W rozwiązaniu skorzystamy z techniki programowania dynamicznego. Niech $P[i][ j]D$ oznacza liczbę niemalejących ciągów długości $i,$ złożonych z liczb całkowitych z przedziału $[1; j],$ w których żadna wartość nie występuje więcej niż $k$ razy. Łatwo zauważyć, że:

$P[0][ j]=1 D$ dla $| j∈ [1;m],$ jest tylko jeden pusty ciąg;
$P[i][1]=1 D$ dla $i ∈[1;k]$ ;
$P[i][1]=0 D$ dla $|i∈ [k+ 1;n].$

Zastanówmy się teraz, jak obliczyć wartość $P[i][ j] D$ dla pozostałych par $| i, j.$ W ciągach niemalejących elementy o tych samych wartościach tworzą spójny przedział. W szczególności wartości $j$ tworzą spójny przedział długości $l∈ [0,min(i,k)].$ Zatem, otrzymujemy ogólny wzór:

mini,k P[i][ j]=QDP[i−l][ j−1]. D l0

Odpowiedzią w zadaniu jest wartość $P[n][m]. D$ Rozwiązanie działa w czasie $O(n$

Rozwiązanie $|O$
Powyższy wzór możemy zapisać równoważnie jako:

dla $|i⩽ k,$ $ii P[i][ j]=QDP[i−l][ j−1]=DP[i][ j−1]+QDP[i−l][ j−1]= D l0l1 i−1 P[i][ j−1]+QDP[i−1−l][ j−1]= = D l0 P[i][ j−1]+DP[i−1][ j] = D$
dla $|i > k,$ $kk P[i][ j]=QDP[i−l][ j−1]=DP[i][ j−1]+QDP[i−l][ j−1]= D l0l1 k−1 P[i][ j−1]+QDP[i−1−l][ j−1]= = D l0 P[i][ j−1]+DP[i−1][ j]−DP[i−1−k][ j−1] = D$

Zauważmy, że obliczenie wartości $[i][ j] D$ dla dowolnych $i, j$ zajmuje czas stały. Zatem całe rozwiązanie działa w czasie $O(n$

Zadanie (Łańcuchy). Dany jest ciąg liczb całkowitych $|a = a1,a2,...,an.$ Łańcuch rozpoczynający się na $|k$ -tej pozycji powstaje w niżej opisany sposób. Znajdujemy pierwszy większy element na prawo od $ak$ i oznaczamy go przez $|ak1.$ Następnie znajdujemy pierwszy większy element na prawo od $ak+1$ i oznaczmy go przez $ak2,$ itd. W ten sposób, dla ustalonego $k$ otrzymujemy łańcuch $|a ,a ,...,a . k1 k2 km$ W zadaniu należy dla każdego $|k∈ {1,2,...,n}$ znaleźć długość łańcucha rozpoczynającego się na $|k$ -tej pozycji. Przykład: dla $a = 3,5,4,5,6$ wynikiem jest $(2,1,2,1,0).$

Rozwiązanie $|O$
Najprostsze rozwiązanie polega na wygenerowaniu dla każdego $|k∈ {1,2,...,n}$ łańcucha rozpoczynającego się na $|k$ -tej pozycji (zgodnie z opisem w treści zadania) i wypisaniu jego długości. Wyznaczenie łańcucha dla każdej pozycji zajmuje $O(n)$ operacji (musimy przeiterować się po całym ciągu). Zatem całe rozwiązanie działa w czasie $O(n |$

Rozwiązanie $|O$
Niech $|F[k]$ oznacza długość łańcucha rozpoczynającego się na $k$ -tej pozycji. W tym rozwiązaniu będziemy wyznaczali $F[k]$ dla kolejnych $|k$ od $n$ do $|1$ (od prawej do lewej). Załóżmy, że obliczyliśmy już $|F[k +1],F[k + 2],...,F[n]$ i chcemy obliczyć $F[k].$ Jeśli pierwszym większym elementem na prawo od $|ak$ jest $al,$ wtedy $F[k] = F[l]+ 1$ (korzystamy z wcześniej obliczonego wyniku dla l). Jeśli zaś wszystkie elementy na prawo są nie większe niż $ak,$ wtedy $F[k] = 0.$

Zastanówmy się teraz, jak dla każdego $ak$ wyznaczyć pierwszy większy element na prawo od niego. Oczywiście, możemy to zrobić naiwnie (przeglądając kolejne elementy). Wówczas jednak otrzymamy rozwiązanie $|O(n$

Zauważmy, że dla pary indeksów $1 ⩽l < m$ jeśli $|a ⩾ a , l m$ to $a m$ nie będzie kolejnym elementem w łańcuchu dla żadnego elementu na pozycji $|[1;l]$ (możemy myśleć o tym w ten sposób, że $|al$ przysłania $am$ ). Zatem kandydaci na kolejny element w łańcuchu tworzą ciąg rosnący. Przeglądając ciąg $|a$ od prawej do lewej, przechowujemy kandydatów na stosie. Na szczycie stosu znajduje się najmniejszy element, na dole zaś największy. Kiedy chcemy znaleźć kolejny element w łańcuchu dla $ak,$ wówczas tak długo zdejmujemy elementy ze stosu, aż na szczycie stosu pojawi się element większy niż $|ak.$ Jeśli taki element nie pojawi się, oznacza to, że taki element nie istnieje. Po wyznaczeniu kolejnego elementu w łańcuchu odkładamy $ak$ na szczyt stosu.

Powyższy algorytm działa w zamortyzowanym czasie liniowym. Wynika to bezpośrednio z własności stosu (każdy z $|n$ elementów został dokładnie raz odłożony na stos i raz z niego zdjęty). Powyższe rozwiązanie działa w czasie $O(n).$