15465. Zawody w szacowaniu [AL_11_05]

Zadanie:
https://pl.spoj.com/problems/AL_11_05
https://spoj.com/ALGOLIGA/problems/AL_11_05

Skrócony opis problemu:

Dana jest plansza o rozmiarze $n$ w kształcie piramidy złożonego z kwadratowych pól. Następnie danych jest $t$ mniejszych lub równych piramid będących częścią planszy. Należy obliczyć obszar planszy pokryty owymi piramidami (czyli podać ilość kwadratów, które zostały przykryte $t$ piramidami). Oto przykładowa plansza z 2 naniesionymi piramidami (wynik to 8, bo mamy 8 zamalowanych kwadratów):

Rozwiązanie naiwne:

Możemy oczywiście utworzyć sobie tablicę dwuwymiarową reprezentującą planszę (na początku pustą) i dla każdej z $t$ piramid zamalowywać odpowiednie pola planszy, a na końcu je zliczyć.

Złożoność: $O(n^2 \cdot t)$, bo pesymistycznie każda piramida do zamalowania może mieć rozmiar bliski $n$, a piramida o rozmiarze $n$ składa się z $\frac{n \cdot (n+1)}{2}$ kwadratów. Na końcu przejście całej planszy również zajmie nam $\frac{n \cdot (n+1)}{2}$ operacji.

Rozwiązanie sprytne:

Bardziej ambitnym czytelnikom polecam nieczytanie poniższego rozwiązania, a spróbowanie najpierw dojście do niego samemu po sprawdzeniu jego złożoności, która została podana poniżej. Wydaje mi się, że złożoność sporo podpowie.

A zatem, na pewno nie możemy dla każdej piramidy zaznaczać w jej wszystkich kwadratów na planszy. Nie powinniśmy również wykonywać nawet $O(n)$ operacji dla pojedynczej piramidy, gdyż wtedy złożoność wyniosłaby $O(n^2 + t \cdot n)$, a i to jest za wolne przy ograniczeniach z zadania. Dla każdej piramidy musimy wykonać zatem albo stałą, albo logarytmiczną ilość operacji. Możemy też wywnioskować z ograniczeń z zadania, że po przetworzeniu wszystkich macierzy możemy nawet przejść całą planszę, kwadrat po kwadracie (bo n=5000, a kilkadziesiąt milionów operacji nie jest problemem).

Na początku myślałem, że trzeba dla każdego wiersza tworzyć jakieś drzewo, ale okazuje się, że nie! Możemy utworzyć pustą planszę i dla każdej piramidy po prostu zaznaczać w danej komórce rozmiar piramidy, która się w niej zaczyna. Czyli dla piramidy z przykładu, której rysunek znajduje się powyżej w komórce $a_{2, 1}$ znajdzie się liczba 2, a w komórce $a_{2, 2}$ znajdzie się liczba 3.

Przy zliczaniu, kiedy dojdziemy do jakiejś zajętej komórki, po prostu dodamy do wyniku 1 licząc jedynie szczyt piramidy, a następnie dodamy 2 piramidy, o 1 rozmiar mniejsze. Tak więc dla $a_{2, 1}$ wpiszemy w komórki $a_{3, 1}$ i $a_{3, 2}$ wartość 2-1=1, a w komórki $a_{3, 2}$ i $a_{3, 3}$ liczbę 3-1=2. Czyli dzielimy piramidę na: szczyt (złożony z 1 kwadratu), lewą podpiramidę o rozmiarze o 1 mniejszym i prawą podpiramidę o rozmiarze o 1 mniejszym. Jak widzimy, 2 razy zaktualizowaliśmy komórkę $a_{3, 2}$. Musimy pamiętać, że możemy aktualizować komórkę TYLKO na wartość większą. Dotyczy to również wczytywania. Czyli jeśli mamy w jakiejś komórce wartość 5, to możemy ją zmienić na 7, ale odwrotnie już nie (bo interesuje nas maksymalny obszar pokryty przez piramidy).

Złożoność: $O(t + n^2)$, bo dla każdej piramidy wykonujemy stałą ilość operacji, a na końcu przechodzimy planszę, która ma $\frac{n \cdot (n+1)}{2}$ pól.

Optymalizacja:
Jeśli rozmiar jakiejś piramidy będzie wynosił $n$, to wiemy już, że jest to maksymalna piramida pokrywająca całą planszę. Możemy wtedy wypisać $\frac{n \cdot (n+1)}{2}$ i zakończyć program.