Podciągi

Zgodnie z zasadą „release early, release often” (czy też „when it compiles, ship it”), proponuję krótką lecz mam nadzieję ciekawą dyskusję na temat zadania polecanego w tym tygodniu przez samego Petra. Zadanie z taką rekomendacją musi być fajne, prawda? Szczególnie jeśli dotyczy zliczania słów, i to jeszcze modulo liczba pierwsza.

Zadanie pochodzi z trzeciej rundy aktualnej edycji Snarknews Winter Series. Pojawiło się także na kanadyjskiej olimpiadzie informatycznej, i w związku z tym można je sobie tutaj wysyłać. Na wszelki wypadek jednak powtórzę tutaj skróconą wersję treści: dla danego napisu długości n\leq 10000 rozważamy wszystkie 2^n sposoby, na które można wybrać niektóre z jego liter. Każdy z takich wyborów powoduje powstanie nowego napisu, który jest podciągiem tego oryginalnego. Krotnością \mathrm{c}(s) napisu s nazywamy liczbę wyborów, w wyniku których otrzymamy s. Teraz interesuje nas wyznaczenie \sum_s \mathrm{c}^2(s) po wszystkich możliwych napisach s. Aby uniknąć konieczności operowania na dużych liczbach, autorzy proszą o podanie wyniku modulo liczba pierwsza.

Wyznaczając \sum_s \mathrm{c}^2(s) oczywiście nie ma sensu myśleć o wszystkich możliwych s, gdyż jest ich jakby nieskończenie dużo. Wystarczy ograniczyć się do takich, dla których \mathrm{c}(s)>0, czyli które są podciągami podanego s. Tych jest już skończenie wiele, lecz wciąż sporo, bo być może aż 2^{10000} (choć pewnie mniej; no właśnie, jak wygląda najgorszy przypadek?). Co dalej?

Najpierw popatrzmy na prosty przykład. Jeśli s=\texttt{aa}, należy rozważyć trzy możliwe podciągi: \epsilon, \texttt{a} i \texttt{aa}, gdzie \epsilon to ciąg pusty. Ten pierwsze i trzeci można uzyskać na dokładnie jeden sposób, natomiast drugi na dwa różne sposoby, czyli odpowiedź to 1^2+2^2+1^2=6.

Skoro nie bardzo widać, jak wyznaczyć \sum_s \mathrm{c}^2(s), może zacznijmy od czegoś prostszego i wyliczmy \sum_s \mathrm{c}(s). Jest to, oczywiście, trywialne, bo \sum_s \mathrm{c}(s)=2^n. Skoro interesuje nas suma \mathrm{c}^2(s), to może warto podnieść obydwie strony tej równości do kwadratu?

\begin{array}{cccccc}  \multicolumn{3}{c}{(\sum_s \mathrm{c}(s))^2} & = 2^{2n}& &\\  \sum_s \mathrm{c}^2(s) &+& 2\sum_{s<s'} \mathrm{c}(s)\mathrm{c}(s') &= 2^{2n}& & \\  \sum_s \mathrm{c}^2(s) & & &= 2^{2n}& - & 2\sum_{s<s'} \mathrm{c}(s)\mathrm{c}(s')  \end{array}

Jeśli więc potrafilibyśmy wyliczyć \sum_{s<s'} \mathrm{c}(s)\mathrm{c}(s'), moglibyśmy rozwiązać całe zadanie. Warto być może wyjaśnić co dokładnie oznacza \sum_{s<s'}. Konieczne jest ustalenie jakiegoś liniowego porządku na wszystkich możliwych słowach. Takich porządków jest pewnie całkiem sporo, ale najbardziej naturalny wydaje się porządek leksykograficzny, czyli s<s' oznacza, że albo s jest prefiksem s'=sx, albo s=xa.. i xb.. gdzie x to jakieś słowo, a a i b to literki, przy czym a<b.

Od tego momentu będziemy myśleć tylko i wyłącznie o wyznaczeniu \sum_{s<s'} \mathrm{c}(s)\mathrm{c}(s'). Wydaje się to bardziej skomplikowane niż wyznaczenie oryginalnej sumy, ale wcale takie nie jest! Powyższa definicja porządku leksykograficznego sugeruje, że być może należy rozbić całą sumę na dwie części.

\sum_{s<s'} \mathrm{c}(s)\mathrm{c}(s') = \sum_{s,x} \mathrm{c}(s)\mathrm{c}(sx) + \sum_{x,y,z}\sum_{a<b} \mathrm{c}(xay)\mathrm{c}(xbz)

Wygląda na niezłą masakrę, ale to tylko pozory. Pomyślmy bowiem o \sum_{s,x} \mathrm{c}(s)\mathrm{c}(sx). Tak naprawdę zliczamy dokładnie takie pary wyborów, dla których pierwszy z otrzymanych napisów jest prefiksem drugiego. To może najpierw zliczmy pary wyborów, dla których otrzymane napisy są takie same?

Po chwili zastanowienia można zobaczyć, że tak naprawdę interesuje nas następujący problem: dla danych dwóch napisów s_1 i s_2 chcemy policzyć sposoby, na które można wybrać niektóre (lub być może wszystkie) litery s_1 i niektóre (lub, znów, być może wszystkie) litery s_2 tak, aby otrzymać dwa identyczne słowa. Jest to dość proste jeśli satysfakcjonuje nas złożoność \mathcal{O}(|s_1||s_2|). Możemy bowiem wyznaczyć dla każdego i i j wartość T[i][j], która jest liczbą takich sposobów dla s_1[1..i] i s_2[1..j] używając programowania dynamicznego (prawie że identycznego jak to używane przy wyznaczaniu najdłuższego wspólnego podciągu). Tak naprawdę s_1=s_2=s, ale być może lepiej myśleć jest o nich jako o dwóch być może różnych słowach aby nie zapomnieć, że wybory w obydwu z nich są niezależne.

To może teraz spróbujmy policzyć pary wyborów, dla których pierwszy z opisanych napisów jest właściwym prefiksem drugiego. W takim wypadku niech j będzie pozycją w s pierwszej litery drugiego napisu, która leży poza poza tym prefiksem. Każda z liter na pozycjach j+1,j+2,\ldots,n może lecz nie musi być wybrana, aby utworzyć drugi napis. Daje nam to więc 2^{n-j-1} możliwości. Dodatkowo musimy wybrać niektóre litery całego s i (osobno) niektóre litery s[1..j] tak, aby utworzyć dwa identyczne słowa. Ale to przecież nic innego jak T[n][j], czyli wszystkie pary wyborów możemy policzyć wyznaczając \sum_j T[n][j] 2^{n-j-1}.

No i świetnie, poradziliśmy sobie z przypadkiem, gdy pierwszy z napisów jest prefiksem drugiego. Pozostaje w cwany sposób wyliczyć \sum_{x,y,z}\sum_{a<b} \mathrm{c}(xay)\mathrm{c}(xbz), czyli pary wyborów, dla których obydwa napisy mają pewien wspólny prefiks x, lecz następna litera a w pierwszym z nich jest mniejsza niż następna litera b w drugim. Niech i będzie pozycją a w s, a j pozycją b (też s). Nie jest dla nas istotne co dzieje się na prawo od i w pierwszym wyborze, ani co dzieje się na prawo od j w tym drugim, czyli przemnożymy wynik przez 2^{n-i} 2^{n-j}. Musimy jednak zagwarantować, że na lewo od i i na lewo od j wybierzemy litery tak, aby utworzyć dwa identyczne słowa. Liczba takich sposobów to jednak nic innego niż T[i][j], czyli szukany cwany sposób to po prostu wyliczenie \sum_{i,j : s[i]<s[j]} T[i][j] 2^{2n-i-j}.

Całe rozwiązanie sprowadza się więc do wyznaczenia wszystkich T[i][j] i następnie wyliczenia powyższych dwóch sum. Stablicowanie wszystkie potęgi dwójki pozwala na wyliczenie ich w czasie, odpowiednio, \mathcal{O}(n) i \mathcal{O}(n^2), co wydaje się być oczekiwaną złożonością dla n=10000. Pewnym kłopotem może być jednak złożoność pamięciowa, a konkretnie konieczność przechowywania tablicy n\times n. Można tego jednak uniknąć stosując standardowy trik z przechowywaniem tylko dwóch wierszy.

Reklamy

2 myśli nt. „Podciągi

  1. Hm, a ja myślałem nad czymś takim: suma c^2(i) to po prostu liczba kolizji, czyli liczba takich par podsłów (rozumianych jako zbiory pozycji), że są one równe (jako napisy). Teraz niech
    P[x][y] = liczba takich kolizji, że ostatnią pozycją w pierwszym podsłowie jest x, a w drugim y
    R[x][y] = j.w. tylko ostatnia pozycja w pierwszym podsłowie ma być ostro na lewo od x
    S[x][y] = analogicznie tylko dla y
    T[x][y] = liczba takich kolizji że zarówno ostatnia pozycja w pierwszym słowie jest na lewo od x jak i ostatnia w drugim jest na lewo od y.

    Czy nie jest czasem tak, że te tablice da się wyznaczyć w czasie O(n^2) ?

    Przykładowo jeśli chcę wyliczyć P[7][14] i wiem, że litery na pozycjach 7 i 14 są sobie równe, to wiem, że mogę wziąć P[7][14] = 2*T[7][14]++ R[7][14]+S[7][14], jeśli zaś litery te się różnią to nie mogę zmatchować x z y, więc przy T[7][14] dam 1* zamiast 2*.
    Z pozostałymi tablicami też chyba nie jest ciężko?
    R[7][14] = R[6][14]+S[6][14]
    S[7][14] = R[7][13]+S[7][13]
    T[7][14] = …ok tu mam jakiś zgryz..ale to pewnie jest S[7][14]+R[7][14]-T[6][13] czy coś w ten deseń

  2. Trochę nie chce mi się teraz tego rozkminiać, no ale puenta miała być taka, że warto najpierw trochę przekształcić to co chcemy wyznaczyć.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s