15203. Plansza [PLA]

Zadanie:
https://pl.spoj.com/problems/PLA

Skrócony opis problemu:

Dla danych $n$, $m$, $k$ ($n, m, k \le 8000$), należy wypisać liczbę możliwych przejść z lewego dolnego rogu macierzy o wymiarach $n$x$m$ do prawego górnego rogu, mogąc wykonać kroki o długości od 1 do $k$. Krok o długości 1 definiujemy przez poruszenie się w prawo, do góry lub w prawo do góry. Ruch o długości 2, to na przykład przesunięcie się z pola (0;0) do pola (2;2). Wynik należy podać modulo $10^9+103$.

Rozwiązanie naiwne:

Zaczynając od pól skrajnych możemy dla każdego pola $x$ obliczać ilość dróg bazując na ilości dróg ze wszystkich punktów, z których da się dojść do pola $x$. Tak więc powiedzmy, że do punktu (5;5) da się dojść na 10 sposobów przy $k=3$. A z punktu (5;5) do punktu (6;5) da się dojść na 1 sposób. Tak więc jeśli chcemy obliczyć na ile sposobów można się dostać do punktu (6;5), to możemy po prostu dodać pola oddalone o 1 krok (o długości 3) od pola (6;5). Tak więc $d(6;5) = d(5;5) + d(4;5) + d(3;5) + d(6;4) + d(6;3) + d(6;2) + d(5;4) + d(4;3) + d(3;2)$. Specjalnie dałem dłuższy przykład, żeby pokazać, ile jest tych składników. Do obliczenia każdego pola potrzebujemy zsumować maksymalnie $3k$ składników (bo dla każdej z 3 możliwych kierunków krok może mieś odległość z przedziału $\left<1;k\right>$).

Np. dla danych $n = 3, m = 4, k = 2$ nasza macierz będzie wyglądała tak:

2 7 22 55

1 3  7 15

1 1  2  3

Lewy dolny róg oznaczamy jako 1, aby mieć jakiś punkt zaczepienia. Może trochę to nieintuicyjne, ale tak nam będzie łatwiej. No i teraz idziemy albo wierszami, albo kolumnami. Zaraz zobaczymy dlaczego. No więc spójrzmy sobie na górną 7-mkę. Możemy do niej dojść w 1 kroku z punktów: (0;2), (0;1), (1;1) i (1;0). Sumujemy zatem wszystkie opcje i mamy naszą 7-mkę: 2+1+3+1=7. Teraz dlaczego musimy iść kolumnami albo wierszami. No bo dla ww. 7-mki potrzebujemy wszystkich pól na lewo od niej, a także poniżej jej. Musimy iść zatem albo najpierw w prawo, a gdy osiągniemy koniec to wiersz wyżej i znów od lewej strony. Albo najpierw do góry, a gdy osiągniemy szczyt, to od dołu następnej kolumny.

Przy obliczaniu każdej komórki, należy wykonywać operację modulo 1000000103, aby nie przekroczyć inta (na long longach trzeba by robić to samo, gdyż w końcu i long longa przekroczymy, a long longi są wolniejsze).

Małym przyspieszeniem jest zauważenie, że tablica ta jest symetryczna, więc wystarczy obliczyć jej połowę i przy każdym obliczeniu $tab[i][j]$ przypisywać $tab[j][i] = tab[i][j]$ (oczywiście jeśli $tab[j][i]$ nie wychodzi poza tablicę). Wykonujemy wtedy 2 razy mniej operacji, ale złożoność asymptotyczna jest taka sama.

Złożoność: $O(n^3)$, jako że dla każdego z $n^2$ (zakładamy, że $n=m$, dla maksymalnego testu) pól musimy zliczyć maksymalnie $3n$ innych pól. Tak więc ze stałymi nasza złożoność to: $O(\frac{3n^3}{2})$.

Rozwiązanie (naj)?sprytniejsze:

W tym rozwiązaniu nadal musimy przejść wszystkie $n \cdot m$ punktów, ale dla każdego z nich możemy obliczyć sumę punktów, z których można dojść do niego w czasie stałym! Jak to zrobić? Możemy zauważyć, że potrzebujemy tylko punktów na 3 "liniach" - poziomej, pionowej i ukośnej. Wykorzystajmy zatem sumy prefiksowe, do zapamiętania sumy wszystkich elementów do danego miejsca w linii poziomej, pionowej i ukośnej. Dla każdej z 3 linii potrzebujemy zatem nową macierz. Łącznie macierzy będzie więc 4.

Dla powyższego przykładu będą wyglądały one tak:

2 7 22 55    4 11 31 73    2 9 31 86    2 8 26 63

1 3  7 15    2  4  9 18    1 4 11 26    1 4  8 17

1 1  2  3    1  1  2  3    1 2  4  7    1 2  4  7

Pierwsza macierz to ta poprzednia, z drogami. Druga to sumy prefiksowe kolumn (czyli 11 pokazuje, że do punktów (1;2), (1;1), (1;0) można dojść łącznie na 11 sposobów). Trzecia to sumy prefiksowe wierszy. A czwarta to sumy prefiksowe ukośnych linii (czyli 63 pokazuje, że do punktów (3;2), (2;1), (1;0) można dojść łącznie na 63 sposoby).

No i jak teraz wykorzystać te tablice? Chcąc np. obliczyć (3;2) potrzebujemy z tablicy nr 1 punktów (3;1), (3;0), (2;2), (1;2), (2;1), (1;0). Jak się to przekłada na pozostałe tablice? Potrzebujemy tylko 3 punktów: punktu (3;1) z tablicy nr 2, puntku (2;2) z tablicy nr 3 i punktu (2;1) z tablicy nr 4. Sprawdźmy więc: $18+31+8 = 57 \neq 55$. Coś jest nie tak! Błąd leży w fakcie, że bierzemy całe rzędy, podczas gdy mamy wziąć tylko $k$ najbliższych elementów. Musimy więc odjąć 3 kolejne punkty: $tab[i-1-k][j]$ dla tablicy nr 2, $tab[i][j-1-k]$ dla tablicy nr 3 i $tab[i-1-k][j-1-k]$ dla tablicy nr 4. Są to po prostu punkty za tymi które nas interesują.

Na tym właśnie polegają sumy prefiksowe - że możemy dzięki nim w czasie stałym mieć sumę w dowolnym przedziale. Weźmy sobie np. ciąg: 3 5 2 9 7. Sumy prefiksowe to: 3 8 10 19 26. Powiedzmy, że chcemy mieć np. sumę od $a=3$ liczby do $b=4$ włącznie. Bierzemy więc 4-tą sumę prefiksową i odejmujemy od niej 2-gą: 19-8=11. Czyli bierzemy sumę wszystkich elementów od początku do $b$ i odejmujemy sumę liczb, które nas nie interesują. A są to pierwsze 2 elementy, więc sumę od początku do $a-1$.

Wracając do zadania, musimy pamiętać, żeby nie wychodzić za tablicę. Tylko bowiem dla tablicy nr 3 możemy coś odjąć - wszędzie indziej wszystko się zgadza. Tak więc końcowy wynik to: $18+31+8-0-2-0=55$. Specjalnie napisałem zera, żeby było widać, że dla tablic nr 2 i nr 4 nic nie odejmujemy.

Tutaj znów należy pamiętać, żeby po każdej operacji wykonywać działanie modulo 1000000103.

Uwaga: Warto zastanowić się nad typem zmiennych. Miałem bowiem ciekawy błąd. Jak pamiętamy, musimy wykonywać operację modulo. Znaczy to, że reszta z dzielenia elementów, które odejmujemy może nam dać liczbę ujemną. Musimy więc po każdym odejmowaniu sprawdzać czy liczba jest ujemna i jeśli tak, to dodawać do wyniku 1000000103, żeby nam później to modulo nadal wychodziło. Ja pomyślałem sobie na początku, że będę robił wszystko na unsigned incie, bo przecież nie będę miał nigdzie liczb ujemnych, a przy tym zmniejszę prawdopodobieństwo, że przekroczę inta. No i niestety później zrobiłem ten trick z odejmowaniem i niestety zamiast liczb ujemnych miałem wielkie liczby dodatnie (bo w unsigned incie gdy zrobimy -1 to nam przeskoczy o -1 od maksymalnej wartości), co skutkowało niedodaniem 1000000103 i wszystko ogólnie się psuło od momentu, w którym powinienem mieć liczbę ujemną. Tak więc int + operacja modulo przy każdej sumie 2 liczb (specjalnie $2 \cdot 1000000103$ mieszczą się w incie) + ifowanie ujemnych liczb.

Złożoność: $O(n^2)$.

Ostateczny algorytm:

int main()
{
        int n, m, k, i, j, x;
        int tab[n+1][m+1], tab2[n+1][m+1], tab3[n+1][m+1], tab4[n+1][m+1];
        const MOD = 1000000103;

        get(n, m, k);
        for(i = 1; i <= n; ++i)
                for(j = 1; j <= m; ++j)
                        if(i*j == 1) // inicjowanie pierwszych komórek macierzy
                                tab[i][j] = tab2[i][j] = tab3[i][j] = tab4[i][j] = 1;
                        else
                        {
                                tab[i][j] = 0;
                                if(i > 1)
                                {
                                        x = tab[i][j]+tab2[i-1][j]-(i-1-k > 0 ? tab2[i-1-k][j] : 0);
                                        if(x < 0)
                                                x += MOD;
                                        tab[i][j] = x%MOD;
                                }
                                if(j > 1)
                                {
                                        x = tab[i][j]+tab3[i][j-1]-(j-1-k > 0 ? tab3[i][j-1-k] : 0);
                                        if(x < 0)
                                                x += MOD;
                                        tab[i][j] = x%MOD;
                                }
                                if(i > 1 && j > 1)
                                {
                                        x = tab[i][j]+tab4[i-1][j-1]-(i-1-k > 0 && j-1-k > 0 ? tab4[i-1-k][j-1-k] : 0);
                                        if(x < 0)
                                                x += MOD;
                                        tab[i][j] = x%MOD;
                                }
                                tab2[i][j] = (tab[i][j]+(i > 1 ? tab2[i-1][j] : 0))%MOD;
                                tab3[i][j] = (tab[i][j]+(j > 1 ? tab3[i][j-1] : 0))%MOD;
                                tab4[i][j] = (tab[i][j]+(i > 1 && j > 1 ? tab4[i-1][j-1] : 0))%MOD;
                        }
        print(tab[n][m]);
}

Optymalizacja:

Autorem optymalizacji jest Mariusz Jakubowski.

Można zoptymalizować złożoność pamięciową z $4nm$ na $3nm$. Tablica nr 2 jest bowiem symetryczna względem przekątnej wychodzącej z punktu (0;0) do tablicy nr 3. Innymi słowy $tab2[i][j] = tab3[j][i]$. Asymptotycznie złożoność pamięciowa to nadal $O(n^2)$, ale pozbyliśmy się dużej macierzy, a dla $n=8000$ to sporo.