Informatyczny kącik olimpijski

Or

Tym razem omówimy zadanie Or, które pojawiło się w 2018 roku na Junior Balkan Olympiad in Informatics w Timisoarze (Rumunia).

Zadanie. Dana jest liczba całkowita $|p$ oraz kwadratowa macierz $A$ rozmiaru $|n ×n.$ W każdym polu macierzy znajduje się jedna liczba całkowita. Z ilu pól składa się najmniejsza prostokątna podmacierz macierzy $A,$ której $|or$ bitowy wszystkich elementów wynosi $p?$

Dla uproszczenia, wartością podmacierzy będziemy nazywali wartość równą $|or$ 'owi wszystkich liczb w tej podmacierzy.

Rozwiązanie $|O$
Zaczniemy od najbardziej intuicyjnego pomysłu. Rozwiązanie polega na niezależnym sprawdzeniu każdej podmacierzy i wybraniu tej, która ma wartość $p$ oraz jest najmniejsza. Wszystkich podmacierzy jest $4 |O(n )$ (lewy górny róg możemy wybrać na $2 O(n )$ sposobów, podobnie prawy dolny róg możemy wybrać na $O(n2)$ sposobów). Naiwne obliczenie wartości podmacierzy (iterowanie po wszystkich elementach) działa w czasie $|O(n2).$ Zatem całe rozwiązanie działa w czasie $6 |O(n ).$

Szybkie obliczanie wartości podmacierzy
Skonstruujemy strukturę danych, która będzie umożliwiała obliczanie wartości dowolnej podmacierzy.

W naiwnym rozwiązaniu iterujemy po każdym polu podmacierzy. Oczywiście takie rozwiązanie jest wolne, dlatego je przyspieszymy. Chcemy, w pewnym sensie, niektóre pola zliczać hurtowo. Zatem obliczymy wartość wszystkich podmacierzy o rozmiarze $a ×b,$ gdzie $a,b$ są liczbami postaci $|2k$ dla $|k∈ N.$ Zauważmy, że takich podmacierzy w całej macierzy $A$ będzie $2 |O(n2log (n)),$ ponieważ w każdym polu jest zaczepionych $2 |log (n)$ podmacierzy $|(1× 1,1× 2,1× 4,...,2 ×1,2 ×2,2 × 4,...,4× 1,4× 2,4 ×4,...).$

Wartości wyżej opisanych podmacierzy będziemy obliczali od tych, które mają najmniejszą liczbę pól, do tych, które mają największą liczbę pól. Wartość podmacierzy o wymiarach $|1× 1$ to liczba zapisana w tym polu. Wartość podmacierzy o wymiarach $|a× b$ to $or$ wartości dwóch mniejszych podmacierzy o wymiarach $|a× b2,$ jeśli $b > 1$ lub $or$ wartości dwóch mniejszych podmacierzy o wymiarach $|a× b 2$ w przeciwnym przypadku. Przykładowo: wartością podmacierzy o wymiarach $2 × 4$ jest $|or$ wartości dwóch mniejszych podmacierzy o wymiarach $2 × 2$ każda.

Konstrukcja struktury zajmuje $2 2 O(n log (n))$ pamięci i odbywa się w czasie $2 |O(n2log (n)).$

Pozostało nam jeszcze opisanie, w jaki sposób znaleźć wartość dowolnej podmacierzy. Nazwijmy ją $M$ i niech ma wymiary $a × b.$ Jej wartość obliczymy na podstawie znanych wartości innych podmacierzy. Ustalmy takie największe $c = 2i$ i największe $|d = 2 j,$ że $|i, j ∈N, c ⩽a$ oraz $|d⩽ b.$ Weźmy takie cztery podmacierze $M$ o wymiarach $c× d,$ że każde pole $M$ będzie należało do przynajmniej jednej z tych czterech podmacierzy. Wówczas wartością $M$ będzie $or$ wartości tych czterech podmacierzy.

Przykład: chcemy obliczyć wartość podmacierzy, której lewe górne pole to $|(2,2),$ a prawe dolne to $(4,6).$ Zauważmy, że tę podmacierz możemy pokryć czterema podmacierzami o wymiarach $2 × 4,$ dla których wyniki znamy. Zatem wartością tej podmacierzy jest $or$ wartości czterech mniejszych podmacierzy.

Rozwiązanie $|O$
Zauważmy, że dzięki powyższej strukturze danych potrafimy w czasie $|O(1)$ obliczyć wartość dowolnej podmacierzy. Zatem w naturalny sposób możemy przyspieszyć rozwiązanie z $6 |O(n )$ do $4 O(n ).$ Wystarczy przejrzeć wszystkie $|O(n4)$ podmacierzy macierzy $A$ i spośród tych o wartości $p$ wybrać najmniejszą.

Rozwiązanie $|O$
W tym rozwiązaniu iterujemy po każdym przedziale wierszy. W ustalonym przedziale wierszy szukamy najmniejszej podmacierzy o wartości $|p$ i wysokości równej liczbie wierszy w tym przedziale. Od teraz możemy o tym myśleć jak o problemie jednowymiarowym, ponieważ wysokość jest ustalona. Szukamy najkrótszego fragmentu, który będzie miał wartość $|p.$ Ten problem możemy rozwiązać za pomocą techniki o nazwie "gąsienica". Na początku ustawiamy dwa wskaźniki (początek i koniec gąsienicy) w pierwszej kolumnie. Następnie symulujemy ruch gąsienicy. Jeśli aktualna wartość jest mniejsza od $p$ i może jeszcze osiągnąć $p,$ wtedy rozszerzamy gąsienicę o kolejną kolumnę. W przeciwnym przypadku skracamy gąsienicę. W każdym stanie, za pomocą powyżej opisanej struktury, w czasie $O(1)$ obliczamy wartość aktualnie rozpatrywanej podmacierzy. Dla każdego rozpatrywanego przedziału wierszy gąsienica wykona liniowo wiele ruchów. Wszystkich przedziałów wierszy do rozpatrzenia jest $O(n2),$ zatem całe rozwiązanie działa w czasie $|O(n3).$