czwartek, 26 marca 2015

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.

czwartek, 20 listopada 2014

19887. Trzy posągi króla [AL_16_04]

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

Skrócony opis problemu:
Mamy dane $t$ testów - każdy składa się z: $n$ i $m$ oraz 3 punktów: $P_1$, $P_2$, $P_3$. Zaczynając od punktu $(1, 1)$ i mogąc się poruszać tylko w prawo lub górę (czyli mogąc tylko zwiększać jedną ze współrzędnych) na ile sposobów można dojść do punktu $(n, m)$ tak, żeby przejść przez przynajmniej 1 punkt z 3 danych. Należy podać liczbę sposobów modulo $10^9+7$.

piątek, 14 listopada 2014

17137. DOMINO [AL_13_07]

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

Skrócony opis problemu:
Dany jest ciąg $n$ kostek domina, których obie wartości zawierają się w przedziale 0..6. Kostki mogą się powtarzać. Należy obliczyć dla niego długość najdłuższego spójnego podciągu kostek, takiego że obracając (bez zamiany miejsc) w nim dowolną ilość kostek możemy otrzymać poprawny ciąg gry Domino, tj. taki, że każde 2 sąsiadujące kostki stykają się bokami o tej samej wartości. Np. dla poniższego ciągu odpowiedź to 3, bo jeśli obrócimy 2 i 4 kostkę to otrzymamy poprawny podciąg od kostki 2 do 4.
2|1 1|3 1|4 5|4

środa, 12 listopada 2014

629. Skąpiec [MISER]

Zadanie:
https://pl.spoj.com/problems/MISER

Skrócony opis problemu:
Dla danego zbioru $n$ punktów w przestrzeni 2-wymiarowej należy wyznaczyć dowolne 2 punkty, takie że okrąg utworzony na nich oraz na pierwszym punkcie z wejścia (nazwijmy go $A$) nie zawiera w sobie żadnego innego punktu (mogą jednak się znaleźć punkty na samym okręgu). Żadne 3 punkty nie są współliniowe.