Informatyczny kącik olimpijski

Piramidy

Tym razem omówimy zadanie z XII OIG.

Zadanie. Dana jest prostokątna plansza $A$ o wymiarach $n | × m.$ Wiersze zostały ponumerowane od 1 do $n,$ zaś kolumny od 1 do $m.$ Pole $|(1,1)$ znajduje się w lewym górnym rogu planszy. Niektóre pola mają przypisaną wartość $1,$ pozostałe wartość 0 ( $A[x][y]$ oznacza wartość pola $|(x,y)$ ). Zerowym kwadratem nazywamy kwadrat, który pokrywa tylko zera. Dla każdej liczby całkowitej $r$ z przedziału $[1;min(n, m)]$ należy policzyć, ile jest zerowych kwadratów o boku $r.$

Wstęp

Naszym zadaniem jest obliczenie wartości $|w$ gdzie $|wi$ oznacza liczbę zerowych kwadratów o boku $i. |$ Załóżmy przez chwilę, że dla każdego pola $(x, | y)$ mamy obliczoną wartość $[x][y] |D$ - rozmiar największego zerowego kwadratu, którego prawym dolnym rogiem jest pole $|(x,y).$ Zauważmy, że pole $(x,y)$ jest również prawym dolnym rogiem zerowych kwadratów o boku: $[x][y]. 1,2,...,D$ Rozważmy teraz ciąg $|w1,$ gdzie $wi$ oznacza liczbę wystąpień wartości $|i$ w tablicy $. D$
Wówczas $|w$

Sumy prefiksowe

Niech $S[x][y]$ oznacza sumę wartości w prostokącie, którego lewe górne pole ma współrzędne $|(1,1),$ zaś prawe dolne $|(x,y).$ Formalnie: $|S[x][y] = Px Py A[i][j]. i 1 j 1$ Obliczenie tablicy sum prefiksowych można zrealizować w czasie liniowym względem rozmiaru prostokąta, korzystając z poniższych zależności:

$S[1][1] = A[1][1]$ ;
$S[x][1] = S[x − 1][1] +A[x][1]$ dla $x | > 1$ ;
$S[1][y] = S[1][y −1] +A[1][y]$ dla $y | > 1$ ;
$S[x][y] = A[x][y]$
$S[x][y]$ jest sumą: wartości pola $(x, y),$ prostokąta bez ostatniego wiersza, prostokąta bez ostatniej kolumny, pomniejszoną o sumę prostokąta bez ostatniego wiersza i ostatniej kolumny, który został dodany dwa razy.

Zastanówmy się teraz, jak za pomocą tablicy sum prefiksowych obliczyć sumę wartości w prostokącie w czasie stałym. Niech $A,$ będą prostokątami, których lewe górne pole ma współrzędne $|(1,1),$ zaś prawe dolne pole zostało wskazane na poniższym rysunku.

Załóżmy, że chcemy obliczyć sumę wartości w kolorowym prostokącie. Jest to $)+S(A), |S(C)$ gdzie $) S(X$ oznacza sumę wartości w prostokącie $. X$

Rozwiązanie $|O$
W tym podejściu wyznaczymy wartości tablicy $D$ przy wykorzystaniu metody wyszukiwania binarnego po wyniku. Załóżmy, że chcemy obliczyć wartość $[x][y] |D$ dla ustalonych $|x,y.$ Jeśli $|A[x][y]$ wtedy $[x][y]=0.D$ W przeciwnym przypadku $[x][y] D$ jest liczbą całkowitą z przedziału $|[1;min(x, y)].$ Tę wartość możemy wyszukać binarnie po wyniku, korzystając z faktu:

Fakt. Jeśli $(x,y)$ jest prawym dolnym rogiem zerowego kwadratu o boku $|r,$ to jest również prawym dolnym rogiem każdego mniejszego zerowego kwadratu.

Sprawdzenie, czy $(x,y)$ jest prawym dolnym rogiem zerowego kwadratu o boku $r,$ można wykonać za pomocą sum prefiksowych w czasie $|O(1).$ Algorytm wyszukiwania binarnego wykona $O(log(min(n, |$ takich faz. Wszystkich pól jest $|nm,$ zatem wyznaczenie tablicy $D |$ działa w czasie
$|O(nm$

Rozwiązanie dynamiczne $O$
W tym podejściu wyznaczymy wartości tablicy $D$ przy wykorzystaniu metody programowania dynamicznego. Załóżmy, że chcemy obliczyć wartość $[x][y] |D$ dla ustalonych $|x,y.$ Jeśli $|A[x][y]$ wtedy $[x][y]=0.D$ W przeciwnym przypadku rozpatrujemy następujące możliwości.

Jeśli $|x = 1$ lub $y = 1,$ wtedy $[x][y]=1. D$ Dla wszystkich pól w pierwszym wierszu oraz w pierwszej kolumnie największy kwadrat ma rozmiar $1.$
Jeśli $|x,y > 1$ oraz $[x−1][y]/=D[x][y−1], |D$ wtedy $[x][y]=1+min(D[x−1][y],D[x][y−1]). D$

Jeśli $|x,y > 1$ oraz $[x−1][y]=D[x][y−1], |D$ wtedy $[x][y]=k+l, D$ gdzie $[x−1][y], k = D$ zaś $l = 1,$ jeśli $A[i$ i $|l = 0$ w przeciwnym przypadku.

Obliczenie wartości $[x][y] D$ dla ustalonego $(x,y)$ odbywa się w czasie $|O(1).$ Plansza ma $nm |$ pól, zatem wyznaczenie tablicy $D |$ działa w czasie $|O(nm).$