Omówienie zadania Tablica binarna (I etap XXVIII OI)

W zadaniu mamy tablicę binarną, na której wykonujemy operacje xorowania elementów w prostokącie, oraz zapytania: ile razy minimalnie należy wykonać operacji prostych (xorowanie prostokątami, których jednym z wierzchołków jest \((1,1)\)), aby uzyskać tablicę wypełnioną zerami.

Analiza zadania

Pokażemy najpierw, że rozwiązanie zawsze można otrzymać. Ustalmy porządek na polach: powiemy, że pole o współrzędnych \((x,y)\) jest mniejsze leksykograficznie od pola o współrzędnych \((x',y')\), jeśli \(x < x'\) albo (\(x=x'\) i \(y < y'\)).

Ustalmy pewien układ zer i jedynek w tablicy. Pytamy się, ile operacji prostych trzeba wykonać, żeby w tablicy zostały same zera.

Wybierzmy pole z jedynką, które jest największe leksykograficznie. Niech to pole ma współrzędne \((x_1, y_1)\). Wykonajmy operację prostą dla prostokąta o przeciwległych wierzchołkach \((1,1)\) i \((x_1,y_1)\). Zauważmy, że zamieniliśmy wartości wszystkich pól \((i, j)\), takich że \(i \leq x_1\) oraz \(j \leq y_1\). W szczególności zamieniliśmy wartość pola \((x_1,y_1)\) na zero oraz nie zmieniliśmy wartości żadnego pola większego leksykograficznie od \((x_1,y_1)\), czyli wszystkie one nadal mają zera.

Dalej wykonujemy takie same kroki: w \(i\)-tym kroku wybieramy pole \((x_i,y_i)\) jako największe leksykograficznie pole z jedynką w aktualnej tablicy i wykonujemy operację prostą na prostokącie o wierzchołkach \((1,1)\) i \((x_i,y_i)\).

Z wcześniejszych obserwacji wynika, że każde kolejne wybrane pole jest mniejsze leksykograficznie od poprzedniego. Zatem po co najwyżej \(nm\) krokach, cała tablica zostanie wyzerowana.

Minimalność rozwiązania

Pokażemy teraz, że rozwiązanie jest jednoznaczne. Załóżmy bowiem przeciwnie, że mamy dwa różne sposoby na wyzerowanie tablicy (sposób \(A\) i \(B\)). Wiadomo, że nie opłaca nam się wykonywać więcej niż jednej operacji prostej dla ustalonego pola \((x,y)\), bo dwukrotne wykonanie operacji prostej dla \((x,y)\) powoduje powrót do początkowej tablicy. Zatem możemy przyjąć, że \(A\) i \(B\) są to po prostu zbiory wybranych pól \(\{ (x_i,y_i) \}\).

Wyrzućmy z tych zbiorów elementy, które znajdują się zarówno w \(A\) jak i w \(B\), otrzymując zbiory \(A'\) i \(B'\). Teraz weźmy największe leksykograficznie pola z \(A'\) i \(B'\). Niech będą to odpowiednio pola \((x_A,y_A)\) i \((x_B,y_B)\). Załóżmy bez straty ogólności, że \((x_A,y_A)\) jest leksykograficznie większe od \((x_B,y_B)\). Wtedy liczba na polu \((x_A,y_A)\) będzie inna po zastosowaniu sposobu \(A\), a inna po zastosowaniu sposobu \(B\). Daje nam to sprzeczność z założeniem, że oba sposoby miały zerować tablicę, czyli rozwiązanie może być tylko jedno.

Wynika zatem, że liczba wykonanych operacji prostych w naszym rozwiązaniu jest minimalna.

Rozwiązania wolne

Dla pierwszego podzadania wystarczy implementacja rozwiązania wykładniczego, które rozważa każdy potencjalny ciąg operacji i sprawdza, czy doprowadza on do wyzerowania tablicy.

Rozwiązanie działające w czasie \(O(n^2 \cdot m^2 \cdot q)\) polega na naiwnym wykonywaniu procesu opisanego w dowodzie istnienia rozwiązania: dla każdego z \(q\) zapytań wykonujemy co najwyżej \(nm\) kroków, a w każdym z nich xorujemy prostokąt rozmiaru \(O(nm)\).

Zauważmy, że możemy przeglądać pola w malejącej kolejności leksykograficznej. Przeglądając pole \((x,y)\), interesuje nas, czy ma ono jedynkę. A to zależy od początkowej wartości tego pola oraz od tego, ile razy wykonaliśmy operację prostą na polach \((x',y')\), takich że \(x\leq x'\) i \(y\leq y'\) (oznaczmy tę liczbę przez \(\alpha(x,y)\)).

Załóżmy, że analizujemy wiersz \(x\) i mamy tablicę \(kol\), w której \(kol[y]\) oznacza liczbę operacji prostych dla pól \((x',y)\) dla \(x'>x\). Przechodząc po polach \((x,y')\) dla \(y'>y\), możemy uaktualniać \(kol[y']\), a także trzymać sumę sufiksową \(kol[y']+kol[y'+1]+\ldots+kol[m]\), która jest szukanym przez nas \(\alpha(x,y)\). Ta obserwacja pozwala nam zoptymalizować nasz kod do złożoności \(O(n \cdot m \cdot q)\), co rozwiąże podzadanie od 1 do 4.

Rozwiązanie wzorcowe \(O(n \cdot m + q)\)

Kluczową obserwacją jest to, że wykonanie operacji xor dla prostokąta o przeciwległych wierzchołkach \((x_1, y_1)\) i \((x_2, y_2)\) jest równoznaczne wykonaniu czterech operacji prostych, każda dla jednego z czterech pól: \((x_1 - 1, y_1 - 1)\), \((x_1 - 1, y_2)\), \((x_2, y_1 - 1)\) oraz \((x_2, y_2)\). Jeżeli któraś ze współrzędnych tych pól wynosi 0, to odpowiadającej mu operacji nie wykonujemy.

Zatem, jeżeli po \(i\) operacjach z wejścia, wykonamy \(4i\) powyższych operacji prostych, to wyzerujemy planszę. Oczywiście, dwukrotne wykonanie operacji prostej dla tego samego pola powoduje powrót do początkowej tablicy, więc interesuje nas, ile jest takich pól, dla których policzyliśmy operację prostą nieparzyście wiele razy (i wykonujemy ją tylko raz).

Tak więc będziemy utrzymywać zbiór pól \(S\). Po każdej operacji z wejścia, uaktualniamy zbiór \(S\) dla czterech pól (jeśli pola nie było w \(S\), to je dodajemy, a jeśli było, to je usuwamy). Rozwiązaniem (minimalną liczbą operacji prostych) jest liczność zbioru \(S\).

Zbiór \(S\) można trzymać w strukturze set, uzyskamy wtedy złożoność czasową \(O(q \log nm)\), lub w zwykłej tablicy dwuwymiarowej rozmiaru \(n\times m\), uzyskamy wtedy złożoność \(O(nm + q)\).