Omówienie zadania Trzy wieże 2 (III etap XXV OI)

Już sam tytuł zadania sugeruje, że jest ono jakąś wariacją na temat zadania, które pojawiło się wcześniej. I rzeczywiście, na drugim etapie XXII Olimpiady Informatycznej zawodnicy rozwiązywali zadanie Trzy wieże. W obu tych zadaniach mamy rząd złożony z \(n\) klocków, z których każdy występuje w jednym z trzech kolorów. Chcemy wybrać jak największy spójny fragment tego rzędu, a następnie z wybranych klocków zbudować trzy różnokolorowe wieże. Ponadto wieże te muszą mieć różne wysokości.

Tutaj dochodzimy do różnicy pomiędzy tymi dwoma zadaniami. W aktualnym zadaniu budujemy dokładnie trzy wieże. Wobec tego, jeżeli jakiegoś koloru klocków nie ma w wybranym fragmencie, to traktujemy wieżę zbudowaną z tych klocków jako wieżę o wysokości \(0\). A ponieważ trzy wieże muszą mieć różne wysokości, wobec tego co najwyżej jedna z nich może mieć wysokość \(0\). Z kolei w oryginalnym zadaniu porównywaliśmy jedynie wieże o dodatnich wysokościach; wobec tego dopuszczaliśmy taką możliwość, że dwie wieże miały wysokość \(0\). Tak więc w naszym wariancie zadania mamy do sprawdzenia tylko jeden dodatkowy warunek: żeby nie wystąpiło rozwiązanie, w którym mamy dwie wieże o wysokości \(0\).

Analiza zadania

Zastanówmy się zatem, dla jakich testów rozwiązanie oryginalnego zadania byłoby zmuszone do tego, żeby wyprodukować tylko jedną niepustą wieżę. Najprostszym jest test, w którym wszystkie klocki mają ten sam kolor. W takim teście, niezależnie od tego, jaki byśmy wybrali fragment, będzie on składał się z klocków o takim samym kolorze, więc zbudujemy z nich tylko jedną wieżę. Oczywiste też jest, że rozwiązanie wzorcowe wybierze jako odpowiedź cały ciąg. Natomiast w zmodyfikowanej treści zadania dla takiego testu nie będzie istniało żadne poprawne rozwiązanie, wobec tego algorytm tutaj będzie musiał dać odpowiedź ,,nie”.

Popatrzmy teraz, kiedy rozwiązanie oryginalnego zadania zwróci wieżę jednego koloru, jeżeli w ciągu znajdują się co najmniej dwa kolory. Zauważmy, że w takim przypadku żaden jednokolorowy fragment o długości co najmniej \(2\) nie będzie poprawnym rozwiązaniem. Oczywiście, żeby zmaksymalizować wysokość tej jednej wieży, którą z tego fragmentu zbudujemy, taki fragment musiałby być maksymalny, to znaczy ani z lewej, ani z prawej strony nie można byłoby go powiększyć o klocek tego samego koloru. Natomiast ponieważ w całym ciągu mamy klocki co najmniej dwóch różnych kolorów, wiemy, że albo z lewej, albo z prawej strony będziemy mogli go poszerzyć o klocek jakiegoś innego koloru. Co oznacza, że możemy po prostu zbudować drugą wieżę o wysokości \(1\), i będzie to inna wysokość niż wysokość pierwszej wieży. Innymi słowy, znaleźliśmy dłuższe rozwiązanie. Wynika z tego, że jeżeli w ciągu mamy co najmniej dwa kolory i co najmniej dwa klocki takiego samego koloru obok siebie, to wtedy na pewno zbudujemy co najmniej dwie wieże.

Pozostaje zatem przypadek, w którym każdy klocek sąsiaduje z klockami o innych kolorach niż on sam. W takiej sytuacji każde rozwiązanie, w którym budujemy tylko jedną wieżę, będzie miało długość \(1\). Ale zauważmy, że jeżeli znajdziemy taki klocek koloru \(a\), który po lewej i prawej stronie ma ten sam kolor \(b\), to wtedy znajdujemy rozwiązanie o długości \(3\), w którym budujemy jedną wieżę o wysokości \(1\) i jedną wieżę o wysokości \(2\). Tak więc widać, że istnieje rozwiązanie co najmniej długości \(3\), więc nie zgłosimy w tej sytuacji rozwiązania jednokolorowego.

Pozostaje ostatni przypadek do rozpatrzenia, w którym każdy trójelementowy fragment zawiera klocki trzech różnych kolorów. Jak łatwo sprawdzić, wtedy ten ciąg musi być tak naprawdę prefiksem nieskończonego ciągu zawierającego na przemian \(3\) kolory. Do takiego ciągu nie istnieje rozwiązanie w naszej zmodyfikowanej wersji. Istotnie, żaden fragment jednoelementowy nie może być rozwiązaniem, bo wtedy dostajemy dwie wieże wielkości \(0\). Fragment dwuelementowy też nie może być rozwiązaniem, bo wtedy dostajemy dwie wieże jednego rozmiaru. Również trójelementowy zawiera trzy wieże jednego rozmiaru, więc też nie jest poprawny.

Każdy dłuższy fragment również będzie zawierał co najmniej dwie wieże o takiej samej wysokości. Tak więc również w tym przypadku odpowiedź brzmi ,,nie”.

Sprowadzenie do znanego problemu

Przedstawiliśmy właśnie dowód, że rozwiązania dla oryginalnej wersji i zmodyfikowanej wersji zadania różnią się jedynie dla dwóch przypadków: dla przypadków ciągu jednokolorowego oraz ciągu, w którym wszystkie trzy kolory występują cyklicznie. Łatwo jest w czasie liniowym sprawdzić, czy mamy do czynienia z którymkolwiek z tych przypadków i w takiej sytuacji wypisać odpowiedź ,,nie”.

Natomiast dla wszystkich pozostałych przypadków uruchamiamy algorytm dla oryginalnego zadania Trzy wieże i wypisujemy jego odpowiedź. Tamten algorytm również działa w czasie \(O(n)\) i został opisany w niebieskiej książeczce, nie ma więc powodu, żeby go tutaj powtarzać.