Omówienie zadania Projekt planszy (II etap XXVIII OI)

Zliczanie ścieżek

Rozwiązanie zadania zaczniemy od opisu sposobu zliczania ścieżek na danej planszy. Jest to dość standardowy problem, który rozwiązujemy za pomocą programowania dynamicznego. Niech \(dp[i][j]\) oznacza liczbę ścieżek na planszy z pola o współrzędnych \((1,1)\) do pola o współrzędnych \((i,j)\). Jeśli pole \((i,j)\) jest zablokowane, to \(dp[i][j]=0\). Jeśli pole \((i,j)\) jest wolne, to możemy do niego dojść z pola \((i-1,j)\) lub z pola \((i,j-1)\) (o ile istnieją). Stąd otrzymujemy \[ dp[i][j]=dp[i-1][j]+dp[i][j-1], \] przy czym przyjmujemy \(dp[i][j]=0\) dla pól poza planszą.

Plansze w dalszej części rozwiązania będziemy przedstawiać na rysunkach, gdzie pola zablokowane będą oznaczone kolorem czarnym, a w polach niezablokowanych będą znajdować się wartości zdefiniowanego wyżej \(dp\) dla tych pól. Dla przykładu, poniżej znajduje się rysunek przedstawiający planszę będącą odpowiedzią w teście przykładowym z treści zadania.

Podzadanie 1 (\(K\leq 50\))

W tym podzadaniu możemy zauważyć, że konstruując planszę rozmiaru \(2\times m\) składającą się z samych niezablokowanych pól, możemy przejść z jej lewego górnego rogu do prawego dolnego na dokładnie \(m\) sposobów. Dlaczego? Zastanówmy się, jak wyglądają ścieżki idące z pola o współrzędnych \((1,1)\) do pola o współrzędnych \((2,m)\). Każda taka ścieżka rozpoczyna się w lewym górnym rogu, podąża w prawo pierwszym wierszem, a następnie w pewnej kolumnie przechodzi do drugiego wiersza i tym wierszem podąża do prawego dolnego rogu. Kolumnę, w której następuje ta zmiana, możemy wybrać na dokładnie \(m\) sposobów i stąd liczba ścieżek.

Rozwiązanie podzadania może więc wyglądać następująco: konstruujemy planszę rozmiaru \(2\times K\) składającą się z samych niezablokowanych pól. Następnie, aby uczynić planszę kwadratową, dodajemy do niej \(K-2\) wierszy, w których wszystkie kolumny, wyłączając ostatnią, są zablokowane. W ten sposób w ostatniej kolumnie stworzymy "korytarz", dzięki któremu do pola o współrzędnych \((K,K)\) będziemy mogli dojść na tyle samo sposobów co do pola o współrzędnych \((2, K)\).

Przykład opisanej tu konstrukcji dla \(K=5\) możemy zobaczyć poniżej.

Takie rozwiązanie pozwala nam skonstruować plansze dla \(K\leq 100\), co jest wystarczające dla tego podzadania.

Podzadanie 2 \(K\leq 2000\)

Zauważmy, że konstrukcja opisana powyżej wykorzystuje jedynie pierwsze dwa wiersze planszy, zaznaczając prawie wszystkie pozostałe pola jako zablokowane. Naturalnym pomysłem jest zatem zastanowienie się, jak wykorzystać pozostałe wiersze.

Postąpimy następująco: pierwszą oraz ostatnią kolumnę planszy wypełnimy niezablokowanymi polami. Następnie grupujemy wiersze w grupy po 3. Ostatni wiersz w każdej grupie będzie składał się z samych zablokowanych pól (poza pierwszą i ostatnią kolumną). Pozostałe dwa wiersze w grupie będą zawierać prostokąt wymiaru \(2\times k_i\), gdzie \(i\) to numer grupy, a \(k_i\geq 0\) to pewna wybrana przez nas liczba całkowita. Lewy górny róg takiego prostokąta będzie połączony z pierwszą kolumną planszy ścieżką składającą się z niezablokowanych pól, a prawy dolny róg będzie połączony podobną ścieżką z ostatnią kolumną.

Dzięki temu \(i\)-ta grupa doda nam \(k_i\) sposobów na dojście z pola \((1,1)\) do pola \((n, n)\). Pozostaje nam jedynie dobrać wartości \(k_i\) tak, aby sumowały się one do \(K\). Zauważmy, że ze względu na ograniczenie na rozmiar planszy mamy ograniczenie \(k_i\leq 96\), gdyż w każdym wierszu musimy zostawić miejsce na pierwszą oraz ostatnią kolumnę oraz poświęcić przynajmniej po jednej kolumnie na połączenie prostokąta z pierwszą oraz ostatnią kolumną. Rozkład liczby \(K\) na sumę \(k_i\) możemy wykonać więc zachłannie: dla każdej grupy po kolei wybieramy \(k_i\) jako minimum z \(K\) oraz 96, a następnie odejmujemy od \(K\) wartość \(k_i\).

Przykładowa (pomniejszona na potrzeby przykładu) konstrukcja dla \(K=12\) znajduje się poniżej. Mamy \(k_1=5,k_2=5\) oraz \(k_3=2\).

Zauważmy, że na planszy rozmiaru \(100\times 100\) zmieścimy 33 takie grupy. Ponadto możemy wybrać \(k_i\) jako dowolną liczbę między \(0\) a \(96\) dla każdej grupy niezależnie, a zatem jesteśmy w stanie skonstruować plansze dla \(K\leq 33\cdot 96\), co jest wystarczające dla tego podzadania.

Podzadanie 3 \(K\leq 10^9\)

W tym podzadaniu wykorzystamy następujący fakt: w kwadracie rozmiaru \(2\times 2\) z lewego górnego do prawego dolnego rogu możemy przejść na dokładnie 2 sposoby. Będziemy "sklejać" ze sobą takie kwadraty tak, aby lewy górny róg każdego kolejnego kwadratu stykał się z prawym dolnym rogiem poprzedniego.

Zauważmy, że przy takiej konstrukcji do prawego górnego rogu \(i\)-tego kwadratu możemy dojść na \(2^{i-1}\) sposobów. Dlaczego? Aby dojść do takiego pola, musimy wcześniej przejść przez \(i-1\) kwadratów, a każdy z nich daje nam dwie możliwości.

Postąpimy więc następująco: ostatnia kolumna planszy będzie składać się wyłącznie z niezablokowanych pól. Następnie popatrzymy na binarną reprezentację liczby \(K\). Jeśli \(i\)-ty bit w tej reprezentacji (licząc od najmniej znaczącego i indeksując od 1) jest równy 1, to na planszy prowadzimy poziomą ścieżkę niezablokowanych pól z prawego górnego rogu \(i\)-tego kwadratu do ostatniej kolumny planszy. W ten sposób dodajemy \(2^{i-1}\) sposobów na dojście z lewego górnego do prawego dolnego rogu planszy.

Przykład takiej konstrukcji dla \(K=11=1011_2\) możemy zobaczyć poniżej.

Zauważmy, że na planszy rozmiaru \(100\times 100\) bez problemu zmieścimy 30 takich kwadratów, a więc będziemy w stanie tworzyć plansze dla \(K\leq 2^{30}-1\), co jest wystarczające dla tego podzadania.

Podzadanie 4 (\(K\leq 10^{18}\))

W rozwiązaniu tego podzadania postąpimy podobnie jak w poprzednim, ale zamiast reprezentacji dwójkowej skorzystamy z reprezentacji dziesiętnej. Nietrudno przekonać się, że na planszy rozmiaru \(4\times 3\) liczba ścieżek z lewego górnego do prawego dolnego rogu wynosi 10. W związku z tym będziemy "sklejać" ze sobą prostokąty rozmiaru \(4\times 3\), podobnie jak sklejaliśmy kwadraty w poprzednim podzadaniu. Lewy górny róg każdego kolejnego prostokąta będzie stykał się z prawym dolnym rogiem poprzedniego.

W ten sposób do prawego górnego rogu \(i\)-tego prostokąta możemy dojść na \(10^{i-1}\) sposobów. Dlaczego? Aby dojść do takiego pola, musimy wcześniej przejść przez \(i-1\) prostokątów, a każdy z nich daje nam 10 możliwości.

Postąpimy więc następująco: ostatnia kolumna planszy będzie składać się wyłącznie z niezablokowanych pól. Następnie popatrzymy na dziesiętną reprezentację liczby \(K\). Jeśli \(i\)-ta cyfra w tej reprezentacji (licząc od najmniej znaczących cyfr oraz indeksując od 1) jest równa \(d\) (dla \(1\leq d\leq 9\)), to łączymy prawy górny róg \(i\)-tego prostokąta z ostatnią kolumną planszy poziomą ścieżką, w której środku wstawimy prostokąt rozmiaru \(2\times d\), aby pomnożyć liczbę sposobów na dojście przez \(d\). Jeśli \(d=0\), to nie prowadzimy żadnej ścieżki. W ten sposób dodajemy \(d\cdot 10^{i-1}\) sposobów na dojście z lewego górnego do prawego dolnego rogu planszy. Po szczegóły konstrukcji odsyłamy do przykładu poniżej.

Przykład takiej konstrukcji dla \(K=4754\) możemy zobaczyć poniżej.

Zauważmy, że na planszy rozmiaru \(100\times 100\) zmieścimy 19 takich prostokątów wraz ze ścieżkami łączącymi je z ostatnią kolumną. Będziemy więc w stanie tworzyć plansze dla \(K\leq 10^{18}\), co jest wystarczające dla tego podzadania.