Lisek chytrusek

Po długiej przerwie wracam z zapasem świeżych pomysłów i na początek proponuję zadanie za 1100 punktów z Single Round Match 651. Zadanie to może wydawać się standardowym ćwiczeniem na programowanie dynamiczne, jednak szybki rzut oka na limity pozwala od razu przekonać się, że to ćwiczenie raczej nie jest standardowe, a być może nawet ma niewiele wspólnego z programowaniem dynamicznym.

W zadaniu dostajemy tablicę T[1..n][1..m] wypełnioną liczbami naturalnymi, gdzie n,m\leq 50. Dostajemy także dużo pytań postaci: na ile sposób można przedstawić dane r jako sumę (być może tylko niektórych) niezerowych liczb w danym prostokącie [x_1,x_2]\times [y_1,y_2]? Istotne jest to, że suma liczb w całej tablicy nie przekracza 2500. Także pytań jest co najwyżej 2500 (oraz interesuje nas liczba sposób modulo 10^9+9, które pewnie jest liczbą pierwszą). Oryginalną treść można znaleźć tutaj.

Zacznijmy od rozwiązania naiwnego. Aby odpowiedzieć na jedno pytanie, wystarczy skorzystać z programowania dynamicznego: pytamy bowiem o liczbę podzbiorów danego zbioru co najwyżej nm liczb, które sumują się do dokładnie r. Łatwo więc skonstruować rozwiązanie działające w czasie \mathcal{O}(nmr). Oznacza to jednak tylko tyle, że jesteśmy w stanie w miarę szybko odpowiedzieć na jedno pytanie. A jest ich przecież nawet 2500

To może spróbujmy rozwiązać uproszczoną wersję zadania, w której wszystkie prostokąty zaczynają się w lewymgórnym rogu całej planszy, czyli x_1=1 oraz y_1=1. Dla wygody oznaczmy sobie sumę wszystkich liczb na całej planszy przez N. W takiej sytuacji mamy tylko \mathcal{O}(nmN) możliwych różnych pytań. Co prawda wiemy, że interesuje nas odpowiedź na co najwyżej 2500 z nich, ale utrudnijmy sobie życie (skoro najpierw je sobie uprościliśmy…) i wyznaczmy odpowiedź dla każdego.

Chcemy więc wyznaczyć dla każdego i\in [1,n],j\in [1,m] oraz r\in[0,N] liczbę sposobów, na jakie da się zapisać r jako sumę niezerowych liczb z T[1..i][1..j]. Oznaczmy tę liczbę przez D[i][j][r]. Naturalne jest wyznaczenie wszystkich D[i][j][r] w dwóch krokach. Najpierw wyliczamy dla każdego i\in [1,n],j\in [1,m] oraz r\in [0,N] liczbę sposobów, na jakie da się zapisać r jako sumę niezerowych liczb z T[i..i][1..j], to jest korzystając z prefiksu i-tej kolumny długości j. Oznaczmy tę liczbę przez C[i][j][r]. Zauważmy, że:

D[i][j][r]=\sum_{r'=0}^{r} D[i-1][j][r'] \cdot C[i][j][r-r'].

Jeśli zaś chodzi o C[i][j][r], najbardziej naturalne jest pewnie wyliczenie tych wszystkich wartości z góry na dół korzystając z tego, że:

C[i][j][r]=\begin{cases} C[i][j-1][r-T[i][j]]+C[i][j-1][r] &\textrm{ gdy } r\geq T[i][j] \\ C[i][j][r]=C[i][j-1][r] &\textrm{ w przeciwnym przypadku.} \end{cases}

Lepiej jednak (za chwilę zobaczymy dlaczego) powiedzieć, że:

C[i][j][r]=\sum_{r'=0}^{r} C[i][j-1][r'] \cdot B[i][j][r-r'],

gdzie B[i][j][r]=\begin{cases} 1 &\textrm{ gdy } r=0 \textrm{ lub } r=T[i][j] \\ 0 &\textrm{ w przeciwnym przypadku.} \end{cases}
Powyższe wzorki mogą wydawać się wręcz bezużyteczne, wygląda bowiem na to, że ich wyliczenie wymaga czasu \mathcal{O}(nmN^2), czyli o rząd wielkości za dużo. Pozwalają jednak na kluczową obserwację: całe zadanie jest tak naprawdę o wielomianach.

Zdefiniujmy bowiem wielomiany:

\begin{aligned} b_{i,j}(x)&=&\sum_{r=0}^{N} B[i][j][r]\cdot x^r, \\  c_{i,j}(x)&=&\sum_{r=0}^{N} C[i][j][r] \cdot x^r,\\ d_{i,j}(x)&=&\sum_{r=0}^{N} D[i][j][r]\cdot x^r.\end{aligned}

Wtedy c_{i,j}(x)=c_{i,j-1}(x) \cdot b_{i,j}(x) oraz d_{i,j}(x)=d_{i-1,j}(x) \cdot c_{i,j}(x). Czyli tak naprawdę chcemy wykonać nm mnożeń wielomianów stopnia N. A przecież wiadomo, że dwa wielomiany stopnia N można przemnożyć w czasie \mathcal{O}(N\log N) korzystając z szybkiej transformaty Fouriera.

Nooo może i wiadomo, ale pojawiają się przynajmniej dwie wątpliwości: czy zadanie, w którym trzeba naklepać FFT, można uznać za fajne? Moim zdaniem nie można. Poza tym nie rozwiązaliśmy jeszcze jego ogólnej wersji: na razie umiemy tylko odpowiedzieć na pytania, w których x_1=1,y_1=1. Zacznijmy od tej drugiej wątpliwości.

Niech e_{x_1,x_2,y_1,y_2}(x) będzie wielomianem zliczającym sposoby zapisania r jako sumę liczb z T[x_1..x_2][y_1..y_2]. Teraz okazuje się, że

e_{x_1,x_2,y_1,y_2}(x)=d_{x_2,y_2}(x) / d_{x_1-1,y_2}(x) / d_{x_2,y_1-1}(x)\cdot d_{x_1-1,y_1-1}(x).

Aby w to uwierzyć, wykonajmy przekształcenie:

e_{x_1,x_2,y_1,y_2}(x)\cdot d(x_1-1,y_2)\cdot d(x_2,y_1-1)=d_{x_2,y_2}(x) \cdot d(x_1-1,y_1-1).

Teraz już widać, że lewa strona zlicza sposby zapisania r jako sumę liczb z T[1..x_2][1..y_2], przy czym liczb z T[1..(x_1-1)][1..(y_1-1)] możemy użyć nawet dwukrotnie. Prawa strona zlicza zaś dokładnie to samo!

Zostaje nam jednak pierwsza wątpliwość. Poza tym, wychodzi na to, że musimy nie tylko mnożyć, ale także i dzielić wielomiany. Przypomnijmy więc sobie na czym polega szybka transformata Fouriera.

Wyobraźmy sobie wielomian p(x)=\sum_{i=0}^{N} a_i x^i. Wybierzmy sobie N+1 różnych punktów x_0,x_1,\ldots,x_N i wyliczmy wartości p(x_0),p(x_1),\ldots,p(x_N). Teraz okazuje się, że mając dane te wartości można jednoznacznie odtworzyć współczynniki a_0,a_1,\ldots,a_N (jednych i drugich jest N+1, więc w sumie nie jest to super zaskakujące; do uzasadnienia wrócimy za chwilę). Jest to przydatne przy mnożeniu dwóch wielomianów p(x) i q(x), gdyż znając ich reprezentacje p(x_0),\ldots,p(x_N) oraz q(x_0),\ldots,q(x_N) łatwo wyznaczyć p(x_0)\cdot q(x_0),\ldots,p(x_N)\cdot q(x_N), czyli reprezentację wielomianu p(x)\cdot q(x), w czasie \mathcal{O}(N). Jeśli potrafilibyśmy tylko sprawnie przejść ze współczynników do wartości w punktach i na odwrót, moglibyśmy efektywnie mnożyć dwa wielomiany.

Teraz powiedzmy, że chcielibyśmy wyliczyć p(x)/q(x) (wiedząc, że jeden wielomian dzieli drugi bez reszty). Moglibyśmy skorzystać z tej samej sztuczki, to znaczy wyznaczyć ich reprezentacje p(x_0),\ldots,p(x_N) oraz q(x_0),\ldots,q(x_N), a następnie wyliczyć p(x_0)/q(x_0),\ldots,p(x_N)/q(x_N) no i wrócić do reprezentacji przez podanie współczynników. Jest jednak jeden drobny kłopot: być może q(x_i)=0. Konkretniej: wybrane przez nas x_i mogą być zerami q(x).

Jednak nie jest to istotna trudność. Przypomnijmy, że interesuje nas dzielenie przez ustalone wielomiany d_{i,j}(x). Każdy z nich ma co najwyżej N zer. Co prawda w FFT wybiera się konkretne punkty x_0,x_1,\ldots,x_N, ale my w gruncie rzeczy nie chcemy korzystać z FFT, powiedzmy więc, że wybierzemy te punkty losowo z [0,10^9+9). Wtedy szansa na to, że trafimy dokładnie w zero jakiegoś d_{i,j}, jest bardzo mała. Co więcej, taką sytuację można wykryć i powtórzyć losowanie (wrócimy do tego szczegółu za chwilę). Załóżmy więc, że mamy x_0,x_1,\ldots,x_N, które nie są zerami żadnego d_{i,j}.

Musimy wyznaczyć wszystkie b_{i,j}(x_i). Jeśli T[i,j]\neq 0, to b_{i,j}(x)=1+x^{T[i,j]}, czyli bez problemu można wyliczyć b_{i,j}(x_i) korzystając z szybkiego potęgowania w czasie \mathcal{O}(\log N). Tak naprawdę wiemy trochę więcej: suma wszystkich liczb na całej planszy nie przekracza N, co oznacza, że wszystkie szybkie potęgowania zajmą w sumie czas \mathcal{O}(N^2). Następnie wyliczamy wszystkie d_{i,j}(x_i) również w czasie \mathcal{O}(N^2), co umożliwia nam wyznaczenie dla danego pytania wartości e_{x_1,x_2,y_1,y_2}(x_i) w czasie \mathcal{O}(N). Pozostaje tylko odtworzyć współczynnik przy x^r w e_{x_1,x_2,y_1,y_2}(x). Ale właściwie jak, skoro nie chcemy korzystać z FFT?

Mając dane p(x_0),p(x_1),\ldots,p(x_N) chcemy odtworzyć współczynniki p(x)=\sum_{i=0}^{N} a_i\cdot x^i. W tym celu najprościej skorzystać ze wzoru Langrange’a, który przy okazji pokazuje, że takie odtworzenie jest zawsze możliwe. Jeśli jednak zastosujemy go wprost, odtworzymy wszystkie współczynniki w czasie \mathcal{O}(N^2). Co wydaje się trochę wolne, ale przecież interesuje nas tylko i wyłącznie współczynnik przy x^r. Ponadto i tak wykonujemy kwadratowy preprocessing, możemy więc stablicować sobie także wszystkie współczynniki wielomianów \ell_j(x), co umożliwi nam wyliczenie współczynnika przy x_r w czasie \mathcal{O}(N). Pozostaje tylko upewnić się, że wszystkie \ell_j(x) mogą zostać skonstruowane w czasie \mathcal{O}(N^2).

Nie jest to do końca trywialne, ale nie jest też trudne. Wystarczy bowiem najpierw skonstruować wielomian t(x)=(x-x_0)\cdot (x-x_1)\cdot \ldots \cdot (x-x_N) (naiwnie, w czasie \mathcal{O}(N^2)), a następnie zauważyć, że \ell_j(x) to po prostu przeskalowany wielomian t(x)/(x-x_j). Dzielenie wielomianu stopnia N przez jednomian może być wykonane w czasie \mathcal{O}(N), a współczynnik skalujący wyliczony naiwnie w czasie \mathcal{O}(N). (Z tym współczynnikiem trzeba trochę uważać: chcemy najpierw wymnożyć (x_j-x_0)\cdot \ldots (x_j-x_N), a następnie odwrócić wynik, a nie odwracać i domnażać kolejne (x_j-x_i).)

Wypada jeszcze wrócić do kwestii losowania punktów x_i. Po wylosowaniu kolejnego punktu wystarczy tylko sprawdzić, czy b_{i,j}(x_i)\neq 0 dla wszystkich i,j. Jeśli tak nie jest, ponawiamy losowanie. Można też wybrać wszystkie x_i deterministycznie korzystając z tego, że nasze b_{i,j}(x) mają bardzo prostą postać.

Podsumowując, po kwadratowym preprocessingu jesteśmy w stanie odpowiedzieć na każde pytanie w czasie liniowym. Całe rozwiązanie działa więc w czasie kwadratowym.

Reklamy

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