Omówienie zadania Hanoj (I etap XXXIII OI, tura zdalna)

Treść zadania

W zadaniu dane mamy \(m\) stosów, na których rozłożone jest \(n\) parami różnych klocków (\(1 \le m \le n \le 10^6\)). Początkowo na każdym stosie numery klocków się na nim znajdujących są posortowane w kolejności rosnącej od wierzchołka stosu do jego podstawy – tą własność nazwiemy własnością \((\heartsuit)\). W każdej operacji możemy zdjąć klocek z wierzchu dowolnego stosu i położyć go na spodzie dowolnego stosu. Celem zadania jest ustalenie, czy istnieje ciąg operacji, zachowujących własność \((\heartsuit)\) w każdym momencie gry, który doprowadzi do sytuacji, w której wszystkie klocki znajdą się na jednym stosie. Jeśli tak, to należy znaleźć minimalną liczbę operacji potrzebnych do osiągnięcia tego celu.

Pierwsze podzadanie – \(n \le 6\)

Ze względu na małą wartość \(n\) możemy rozważyć wszystkie możliwe stany gry i przeprowadzić na nich przeszukiwanie wszerz (BFS). Stan gry możemy zakodować jako ciąg \(m\) stosów, z których każdy jest reprezentowany jako lista klocków na nim się znajdujących. W każdej iteracji algorytmu generujemy wszystkie możliwe stany osiągalne z aktualnego stanu poprzez wykonanie jednej dozwolonej operacji (zdjęcie klocka z wierzchu jednego stosu i położenie go na spodzie innego stosu). Jeśli któryś z wygenerowanych stanów odpowiada sytuacji, w której wszystkie klocki znajdują się na jednym stosie, to zwracamy liczbę operacji potrzebnych do osiągnięcia tego stanu.

Wszystkich stanów jest tyle, co możliwości rozłożenia \(n\) klocków na \(m\) stosach, czyli \(m^n\). Dla \(n = 6\) i \(m \le n\) jest to co najwyżej \(6^6 = 46656\) możliwości, zatem spamiętywanie odwiedzonych stanów mieści się w limitach podanych w zadaniu.

Analiza zadania

Spróbujmy się przyjrzeć stosowi, na którym znajduje się klocek o numerze \(1\). Oznaczmy ten stos przez \(S\). Ponieważ na początku gry wszystkie klocki są ułożone rosnąco od wierzchołka do podstawy, to klocek \(1\) musi znajdować się na wierzchołku swojego stosu. Niech liczba klocków na tym stosie wynosi \(k\).

Gdyby się szczęśliwie okazało, że stos zawierający klocek \(1\) zawiera wszystkie klocki o numerach \(1, 2, \dots, k\), to zauważmy, że to jest dobry kandydat na stos, na który możemy układać wszystkie klocki! Możemy wtedy przenosić wszystkie pozostałe klocki (kolejno o numerach od \(k+1\) do \(n\)) na ten stos, zachowując własność \((\heartsuit)\). Uważny czytelnik dostrzeże analogię do sortowania przez scalanie w tym pomyśle. Wystarczy zatem zapamiętać, na jakim stosie początkowo znajduje się klocek o numerze \(i\) dla \(i = 1, 2, \dots, n\). Przenoszenie realizujemy poprzez zdjęcie klocka z wierzchu stosu, na którym się on znajduje, i położenie go na spodzie stosu zawierającego klocki \(1, 2, \dots, k\) (zauważmy, że nie musimy tego symulować wprost, wystarczy tylko pamiętać, skąd i dokąd będą przenoszone klocki). W ten sposób potrzebujemy dokładnie \(n - k\) operacji.

Niestety, nie zawsze mamy taką gwarancję, że stos \(S\) zawierający klocek \(1\) zawiera spójny prefiks numerów klocków. Co w takiej sytuacji? Musi istnieć klocek o numerze \(2 \le j\), który nie znajduje się na stosie \(S\), ale wszystkie klocki o numerach \(1, 2, \dots, j-1\) znajdują się na stosie \(S\). Ponadto istnieje klocek o numerze \(i\) większym niż \(j\), który również znajduje się na \(S\). Aby ułożyć końcową wieżę, będziemy musieli przenieść klocek o numerze \(j\) na spód stosu, na którym znajduje się już element \(j-1\). Ale nie może to być stos \(S\), ponieważ znajduje się tam klocek o numerze \(i > j\), a więc bezpośrednie przeniesienie klocka \(j\) na stos \(S\) złamałoby własność \((\heartsuit)\). Nie możemy też zabrać klocka o numerze \(i\) ze stosu \(S\) bez zdejmowania wszystkich klocków znajdujących się nad nim (czyli o mniejszych numerach). Stąd wniosek, że klocki o numerach \(1, 2, \dots, j-1\) muszą zostać przeniesione na inny stos – na którym będziemy mogli zasymulować układanie wieży, jak opisano wcześniej. Ponieważ \(1\) jest najmniejszym numerem klocka, to możemy go przenieść jedynie na pusty stos bez złamania własności \((\heartsuit)\). Zadanie sprowadza się zatem do znalezienia pustego stosu.

Drugie podzadanie – istnieje pusty stos

W takiej sytuacji pusty stos dany mamy za darmo na wejściu. Wystarczy zasymulować opisany wcześniej proces. Jeśli stos \(S\) zawiera klocki o numerach \(1, 2, \dots, k\), to przenosimy wszystkie pozostałe klocki na stos \(S\), potrzebując \(n - k\) operacji. W przeciwnym razie znajdujemy pusty stos i w analogiczny sposób przenosimy kolejno klocki o numerach \(1, 2, \dots, n\) na ten pusty stos, wykorzystując \(n\) operacji.

Ostatni przypadek

Pozostaje nam do rozważenia przypadek, gdy klocki na wieży \(S\) nie stanowią spójnego prefiksu numerów klocków oraz początkowo na wejściu wszystkie stosy były niepuste. Musimy w takiej sytuacji uczynić pewien stos pustym. Kiedy jesteśmy w stanie opróżnić dany stos \(A\)? Oczywiście wtedy, gdy istnieje stos \(B\), na który możemy przenieść wszystkie klocki ze stosu \(A\), zachowując własność \((\heartsuit)\). Oznacza to, że maksymalny element na stosie \(B\) musi być mniejszy niż minimalny element na stosie \(A\). Jeśli taki stos \(B\) istnieje, to możemy opróżnić stos \(A\), przenosząc jego klocki na stos \(B\). Następnie możemy wykorzystać pusty już stos \(A\) do zbudowania wieży z klocków o numerach \(1, 2, \dots, n\), jak opisano wcześniej.

Jeśli nie znajdziemy takiej pary stosów \(A\) i \(B\), to nie jesteśmy w stanie wykonać żadnej operacji bez złamania własności \((\heartsuit)\), a więc również nie jesteśmy w stanie zbudować jednej wieży zawierającej wszystkie klocki. W takim przypadku odpowiedź to \(-1\). W przeciwnym razie, aby zminimalizować liczbę wykonanych przeniesień, musimy pamiętać, że wśród wszystkich kandydatów na stos \(A\), które możemy opróżnić, powinniśmy wybrać ten, na którym znajduje się jak najmniej klocków.

Trzecie podzadanie – \(n \le 1\ 000\), czwarte podzadanie – \(m = 3\)

W tych podzadaniach wystarczy sprawdzić wszystkie pary stosów jako kandydatów na parę stosów \(A\) i \(B\). Dla każdej pary sprawdzamy, czy maksymalny element na stosie \(B\) jest mniejszy niż minimalny element na stosie \(A\). Jeśli tak, to obliczamy liczbę operacji potrzebnych do opróżnienia stosu \(A\) i zbudowania wieży z klocków o numerach \(1, 2, \dots, n\) na pustym już stosie \(A\). Spośród wszystkich możliwych par wybieramy tę, która daje minimalną liczbę operacji. Złożoność czasowa to \(O(m^2 + n)\), co jest wystarczające do rozwiązania tej wersji z \(n \le 1000\), ponieważ \(m \le n\).

Pełne rozwiązanie

Do rozwiązania ogólnej wersji wystarczy, że będziemy efektywnie znajdować parę stosów \(A\) i \(B\). Zacznijmy od wybrania stosu \(B\). Zauważmy, że jeśli dla ustalonego stosu \(A\) mamy dwa stosy \(B_1\) i \(B_2\), na które możemy przenieść klocki ze stosu \(A\), to nie ma znaczenia, który z tych stosów wybierzemy jako docelowy i sumaryczna liczba operacji będzie taka sama. Wybierzmy zatem jako stos \(B\) ten, którego maksymalny element jest minimalny możliwy. Dobierzmy teraz do niego stos \(A\). Aby zminimalizować liczbę operacji, powinniśmy wybrać stos \(A\) z jak najmniejszą liczbą klocków, spełniający warunek, że jego minimalny element jest większy niż maksymalny element na stosie \(B\), co jesteśmy w stanie zrobić efektywnie jednym przejściem po wszystkich stosach (skoro zawierają one klocki posortowane po swoich numerach). Jeśli szukany stos \(A\) istnieje, to wykonujemy opisaną wcześniej symulację. Łączna liczba operacji to \(n\) powiększone o liczbę klocków na stosie \(A\). Otrzymujemy rozwiązanie o złożoności czasowej \(O(m + n)\), co jest wystarczające do rozwiązania zadania w pełnej wersji.