Informatyczny kącik olimpijski

Wykładzina

W zeszłym miesiącu zajmowaliśmy się uogólnieniem następującego zadania: dla danego kwadratu rozmiaru $n × n$ podzielonego na $|n2$ pól, z których niektóre były zabronione, należało znaleźć prostokąt o największym polu, który nie zawierał żadnego zabronionego pola. W tym numerze rozważymy jeszcze inną wariację tego zadania, a mianowicie będziemy szukać największych prostokątów, które zawierają co najwyżej $K$ zabronionych pól (nazwiemy je prostokątami prawie pustymi).

Na początek rozważymy przypadek $K = 1,$ który był treścią zadania Wykładzina z finału Potyczek Algorytmicznych 2014. Zakładamy, że Czytelnicy są zaznajomieni z algorytmem szukania największego pustego prostokąta opisanym w poprzednim numerze (a pomocna może być również znajomość technik opisanych w kąciku z numeru 12/2013). Przypomnijmy, że w tamtym algorytmie ustalaliśmy wiersz $i$ zawierający dolny bok szukanego pustego prostokąta i rozważaliśmy kolejne kolumny $| j,$ trzymając na stosie zbiór elementów opisujących obszar, w którym może znajdować się lewy górny róg pustego prostokąta o prawym dolnym rogu w polu $(i, j).$

Rys. 1 Prawie pusty prostokąt dla pola $|8,5$ zawiera zabronione pole $|7,5$ ale nie zawiera zabronionego pola $|3,5 ,$ więc ma wysokość od $|h1 2$ do $|h2 5.$ Kandydaci znajdowani przez algorytm mają rozmiary: $5 2,4 4,$ $3 5$ oraz $|2 8.$

Ustalmy teraz, że szukamy prawie pustego prostokąta o dolnym boku w wierszu $i$ i zawierającego jedno zabronione pole w kolumnie $| j.$ Zatem prostokąt taki będzie miał wysokość między $h1 = d[i, j]+ 1$ a $h2 = h1 +d[i − h1, j],$ gdzie $| d[i, j]$ to liczba niezabronionych pól leżących na i powyżej pola $|(i, j)$ do pierwszego zabronionego pola (Rys. 1). Załóżmy też, że obliczyliśmy stos dla obszaru obejmującego kolumny $|1,2,..., j− 1$ oraz symetryczny stos dla kolumn $|n,n −1,..., j+ 1,$ a także usunęliśmy z tych stosów elementy wyższe niż $| h2$ (zostawiając co najwyżej po jednym elemencie wyższym niż $h2$ ). Wszystkich kandydatów na prawie pusty prostokąt możemy znaleźć podczas usuwania z tych stosów elementów o wysokościach pomiędzy $h2$ a $h1.$

Aby uzyskać optymalną złożoność, wykonujemy jedynie dwa przebiegi oryginalnego algorytmu (jeden od lewej do prawej, a drugi od prawej do lewej), spamiętując dla każdej kolumny $| j$ listę prostokątów usuwanych ze stosu podczas przetwarzania tej kolumny. Następnie kandydatów na prawie puste prostokąty dla kolumny $| j$ uzyskujemy, przeglądając te listy. Dla ustalonego wiersza $i$ praca algorytmu jest ograniczona przez $|O(n)$ (tylko tyle elementów będzie na stosie), zatem cały algorytm działa w czasie $|O(n2).$

Zadanie to ma również ciekawe rozwiązanie randomizowane, w którym algorytm szukania największego pustego prostokąta wykorzystujemy bardziej bezpośrednio. Wykonujemy $f$ iteracji; w każdej z nich każde zabronione pole zamieniamy, niezależnie z prawdopodobieństwem $p,$ na pole niezabronione. Następnie szukamy największego pustego prostokąta. Zauważmy, że ustalony maksymalny prawie pusty prostokąt, zawiera jedno zabronione pole oraz opiera się na trzech zabronionych polach (nie na czterech, bo ustalamy również dolny bok tego prostokąta). Zatem jeśli zamienimy pole w środku oraz nie zamienimy pól na bokach (co wydarzy się z prawdopodobieństwem $|p(1− p)3$ ), to ten prawie pusty prostokąt zostanie znaleziony przez algorytm szukania największego pustego prostokąta. Prawdopodobieństwo znalezienia jest największe dla $p = 1 4$ i wynosi około $1 |10.$ Zatem po $| f = 40$ iteracjach prawdopodobieństwo znalezienia ustalonego (a zatem też tego o największym polu) prawie pustego prostokąta wynosi

9- f 1 −( 10 ) ≈0,98.

Zauważmy, że nasz algorytm może znajdować również prostokąty, które zawierają więcej niż jedno zabronione pole. Łatwo sobie z tym poradzimy, sprawdzając ile zabronionych pól zawiera każdy znaleziony kandydat (jak to zrobić w czasie stałym zostawimy jako nietrudne zadanie dla Czytelników, wymagające wykorzystania tzw. dwuwymiarowych sum prefiksowych). Ostateczna złożoność czasowa to $|O(f$ Dla pełności dodajmy, że rozwiązanie randomizowane łatwo uogólnić na przypadek $K > 1,$ ale nie będzie to zbyt praktyczne, gdyż $f$ rośnie wtedy wykładniczo względem $K.$

K | 2 — Rys. 2 Wysokości prostokątów dla $K 2$ i przedziału kolumn $i 4, j 7$ są następujące:

$----k-----0--1--2- r1 k,i, j 0 1 3 r2 k,i, j 2 4 4$

Aby rozwiązać ogólny przypadek $K | ⩾1,$ użyjemy metody "dziel i zwyciężaj". Podzielimy kwadrat poziomą prostą na dwie równe części, w których rekurencyjnie znajdziemy największe prawie puste prostokąty w całości zawarte w tych częściach. Pozostaną do rozważenia prawie puste prostokąty przecinające prostą (Rys. 2). Dla każdego $k ⩽ K$ oraz dla każdej pary kolumn $1⩽ i⩽ j ⩽n$ znajdźmy wysokość $r1[k,i, j]$ maksymalnego prostokąta znajdującego się w górnej części, ograniczonego prostą oraz kolumnami $|i, j$ i zawierającego $k$ zabronionych pól - nie jest trudno zrobić to w czasie $|O(kn2).$ Następnie zróbmy to samo dla dolnej części, dostając wartości $r2[k,i, j].$ Maksymalny prawie pusty prostokąt przecinający prostą ma rozmiar

maxi, j( j +1 −i) ⋅(maxk1+k2DK r1[k1,i, j]+ r2[k2,i, j]).

Jeśli oznaczymy przez $T (n)$ czas działania algorytmu dla kwadratu o boku $|n,$ to dostajemy następującą rekurencję: $T(n) = 4T (n/2) +3O(kn$ (najpierw dzielimy kwadrat na dwie prostokątne części, a potem każdą z nich pionową prostą na dwa kwadraty o bokach $|n/2$ ). Rozwiązanie tej rekurencji (a zatem złożoność czasowa całego algorytmu) to $T (n) = O(kn2$