Omówienie zadania Zamek cykliczny (I etap XXXII OI)
Treść zadania
W zadaniu mamy daną potencjalnie bardzo dużą dodatnią liczbę całkowitą \(n\). Możemy na niej wykonywać dwa typy operacji; operacja pierwszego typu zwiększa liczbę o 1, a operacja drugiego typu przenosi najbardziej znaczącą cyfrę na najmniej znaczącą pozycję, a następnie usuwa wszystkie zera wiodące. Operacje te nazwiemy, odpowiednio, inkrementacją i rotacją. Naszym celem jest wyznaczenie możliwie najmniejszej liczby operacji, po których liczba \(n\) stanie się równa 1.
Pomijając pierwsze podzadanie, liczba \(n\) nie zmieści się w żadnym standardowym typie całkowitym w C++, więc będziemy musieli ją przechowywać w jakiś inny sposób, np. w typie string.
Przeszukiwanie grafu
Nasze zadanie możemy zinterpretować jako problem znajdowania najkrótszej ścieżki w grafie skierowanym. Wierzchołkami grafu są wszystkie liczby całkowite dodatnie. Z wierzchołka odpowiadającego liczbie \(m>1\) prowadzą dwie krawędzie odpowiadające wykonaniu pojedynczej inkrementacji albo rotacji. Chcemy wyznaczyć długość najkrótszej ścieżki w grafie z zadanego wierzchołka \(n\) do wierzchołka \(1\).
Ewidentnym problemem z tym rozwiązaniem jest to, że opisany graf ma nieskończenie wiele wierzchołków. Niech \(k\) oznacza długość zapisu dziesiętnego liczby \(n\). Począwszy od liczby \(n\), na ścieżce do wierzchołka \(1\) możemy na pewno natrafić na wierzchołki o co najwyżej \(k\) cyfrach. A czy możemy natrafić na wierzchołek o więcej niż \(k\) cyfrach? Załóżmy, że tak się stanie, i zastanówmy się, jak będzie wyglądała operacja bezpośrednio prowadząca od liczby \(m'\) o co najwyżej \(k\) cyfrach do pierwszej liczby \(m\) o więcej niż \(k\) cyfrach. Operacja ta nie będzie rotacją, gdyż rotacja nie może zwiększyć liczby cyfr. Będzie to zatem inkrementacja liczby \(m'=\underbrace{99\dots 9}_{k\text{ cyfr}}\), a uzyskaną liczbą będzie \(m=10^k=1\underbrace{00\dots 0}_{k\text{ cyfr}}\). Zauważmy jednak, że w momencie dojścia do liczby \(m\) tej postaci, za pomocą pojedynczej rotacji natychmiast uzyskujemy żądaną liczbę 1.
Tak więc nie musimy konstruować części grafu odpowiadającej liczbom o więcej niż \(k\) cyfrach. W ten sposób uzyskujemy graf, który ma co najwyżej \(10^k \le 10n\) wierzchołków i \(20n\) krawędzi. Najkrótszą ścieżkę w grafie wyznaczamy za pomocą przeszukiwania wszerz (BFS). W ten sposób uzyskujemy rozwiązanie zadania w czasie \(O(n)\), co pozwalało zaliczyć pierwsze podzadanie.
Zauważmy na koniec, że grafu nie musimy konstruować w sposób jawny, jako że krawędzie grafu możemy łatwo wyznaczać na bieżąco. Wystarczą nam tablica rozmiaru co najwyżej \(10^k\) do przechowywania odległości w grafie i kolejka z algorytmu BFS.
Rozwiązanie zachłanne
Aby uzyskać jakiekolwiek szybsze rozwiązanie, warto zastanowić się, jakie operacje wykonamy na sam koniec rozwiązania. Liczbę 1 możemy osiągnąć jedynie za pomocą rotacji liczby postaci \(10^k\). Natomiast liczbę \(10^k\) możemy osiągnąć jedynie przez inkrementację liczby \(10^k-1\). Naszym prawdziwym celem będzie zatem uzyskanie z liczby \(n\) liczby złożonej z samych cyfr 9 w możliwie jak najmniejszej liczbie operacji, a następnie dodanie dwóch operacji potrzebnych do dojścia do jedynki. Wyjątkiem będą liczby \(n\), które od razu są postaci \(10^k\) – dla nich wystarczy tylko jedna operacja.
W tym momencie może nam się narzucać następujący algorytm zachłanny. Spójrzmy na ostatnią cyfrę liczby \(n\). Jeśli jest to cyfra 9, to nie musimy nic z nią robić. Zakładając, że \(n\) nie składa się jeszcze z samych dziewiątek, możemy więc wykonać rotację. Jeśli ostatnia cyfra to 0, również możemy od razu wykonać rotację. A to dlatego, że w wyniku kolejnych rotacji w końcu to zero stanie się zerem wiodącym i również zniknie. Jeśli natomiast ostatnia cyfra to \(c\), takie że \(0 \ne c \ne 9\), możemy wykonać \(9-c\) inkrementacji, po których \(c\) stanie się cyfrą \(9\).
Dla liczby \(n=301\) z przykładu z treści zadania opisany algorytm zadziała następująco:
- po 8 inkrementacjach uzyskujemy liczbę 309,
- wykonujemy rotację, uzyskując liczbę 93,
- po 6 inkrementacjach uzyskujemy liczbę 99,
- na koniec wykonujemy opisane powyżej operacje inkrementacji i rotacji prowadzące do liczby 1.
Okazuje się, że opisany algorytm dla dowolnej liczby \(n\) spełniającej warunek pierwszego podzadania, tj. \(n \le 100\,000\), zawsze wygeneruje najkrótszą sekwencję operacji. Niestety dla większych wartości \(n\) nie zawsze musi tak być. Zastanówmy się, jakiego typu operacje pomijamy w rozwiązaniu zachłannym. Są to mianowicie inkrementacje cyfry 0 i inkrementacje powodujące powstanie przeniesienia. Możemy faktycznie wskazać kilka przykładów, w których tego typu operacje są wymagane do uzyskania minimalnego wyniku:
- 99999999990 (10 dziewiątek i 0) – tutaj bardziej opłaca się 9 razy inkrementować 0 niż wykonać 10 rotacji, po których 0 zniknie;
- 999999999989 (10 dziewiątek i 89) – lepiej jest wykonać 10 inkrementacji, z których pierwsza powoduje przeniesienie, niż 11 rotacji i jedną inkrementację cyfry 8;
- jeszcze bardziej wymowny przykład drugiej sytuacji mamy dla liczby \(n=1234\underbrace{99\dots 9}_{500\,000\text{ cyfr}}5678\), w której na początku wykonujemy \(9999-5678=4321\) inkrementacji, żeby oszczędzić sobie wykonywania \(500\,000\) rotacji.
W powyższych liczbach-przykładach mamy dużo cyfr równych 9. Okazuje się, że jeśli liczba \(n\) spełnia warunki pierwszego podzadania, tj. składa się tylko z cyfr 0 i 1, to rozwiązanie zachłanne zawsze da dla niej optymalny wynik, a zatem w przypadku takich liczb nie opłaca się wykonywać inkrementacji zer ani przeniesień. Uzasadnienie tego spostrzeżenia powinno być dla Czytelnika nietrudne po zapoznaniu się z opisem rozwiązania wzorcowego poniżej; podobnie jak uzasadnienie, że dla wszystkich liczb do \(10^6\) rozwiązanie zachłanne jest poprawne.
Ostatecznie rozwiązanie zachłanne pozwalało zaliczyć pierwsze dwa podzadania.
Rozwiązanie zachłanne z iteracją
Rozwiązanie zachłanne stara się wykonywać możliwie jak najmniej inkrementacji. Byłoby ono optymalne, gdyby koszt wykonania rotacji był zerowy. Tak jednak nie jest i czasem opłaca się wykonać mniej rotacji kosztem zwiększonej liczby inkrementacji. Nie wiemy, ile dokładnie rotacji wykonamy. Spróbujmy więc rozważyć wszystkie możliwości i dla każdej z nich sprawdzić, ile wtedy potrzebujemy inkrementacji.
Niech \(r\) oznacza liczbę rotacji, na które decydujemy się w rozwiązaniu. Wtedy w trakcie całej sekwencji ruchów na miejscu jedności będziemy mieć najbardziej istotne \(r\) cyfr pomijając zera oraz cyfrę, która tam początkowo była. Jeśli którąś z pozostałych cyfr będziemy musieli zwiększyć, użyjemy przeniesienia.
Jeśli \(r\) jest nie mniejsze niż liczba niezerowych cyfr liczby \(n\), pomiędzy wykonywaniem \(r\) rotacji uda nam się inkrementować cyfry tak jak w rozwiązaniu zachłannym. W przeciwnym razie podzielmy zapis dziesiętny liczby \(n\) na prefiks \(P\) i sufiks \(S\), które oznaczają:
- \(P\) to prefiks zapisu zawierający \(r\) najbardziej znaczących niezerowych cyfr liczby \(n\) oraz wszystkie sąsiadujące z nimi zera;
- \(S\) to pozostały sufiks złożony z najmniej znaczących cyfr.
Po wykonaniu takiego podziału łatwo jest już ustalić, ile inkrementacji potrzeba:
- dla każdej niezerowej cyfry \(c\) w prefiksie \(P\) wykonujemy \(9-c\) inkrementacji, żeby zamienić ją w 9 – dokładnie w momencie, gdy ta cyfra stanie się najmniej znaczącą;
- sufiks \(S\) musimy doprowadzić do samych dziewiątek jedynie za pomocą inkrementacji (potencjalnie z użyciem przeniesień) jeszcze zanim rozpoczniemy wykonywać rotacje; tak więc w sufiksie \(S\) musimy wykonać \(\underbrace{99 \dots 9}_{s\text{ cyfr}} - S\) inkrementacji, przy czym \(s\) to długość sufiksu \(S\).
Zastanówmy się jeszcze nad złożonością tego rozwiązania. Niech \(k\) oznacza, jak poprzednio, długość zapisu dziesiętnego liczby \(n\). Dla danego wyboru liczby \(r\) w czasie \(O(k)\) wyznaczamy podział zapisu liczby \(n\) na prefiks \(P\) i sufiks \(S\), przy okazji zliczając inkrementacje potrzebne na prefiksie. Teraz musimy obliczyć "dopełnienie" sufiksu \(S\) do samych dziewiątek, co może wymagać odejmowania dużych liczb. Można jednak zauważyć, że jeśli wynik tego odejmowania będzie duży, np. większy niż \(10^7\), to i tak uzyskane rozwiązanie będzie gorsze niż wynik rozwiązania zachłannego, które zawsze wykonuje nie więcej niż \(8 \cdot k\) inkrementacji i \(k\) rotacji. A zatem jeśli sufiks \(S\) zawiera cyfrę różną od 9 dalej niż na siódmej pozycji od końca, możemy pominąć aktualnie rozważaną wartość \(r\). W przeciwnym razie odejmowanie \(\underbrace{99 \dots 9}_{s\text{ cyfr}} - S\) sprowadza się do odejmowania dwóch liczb 32-bitowych, co możemy wykonać w czasie stałym.
Ostatecznie dla danego wyboru liczby \(r\) wykonujemy \(O(k)\) operacji. Mamy co najwyżej \(k\) możliwych wyborów liczby \(r\). Otrzymujemy rozwiązanie o złożoności \(O(k^2)\), które zaliczało trzecie (oraz pierwsze) podzadanie.
Rozwiązanie wzorcowe
Aby uzyskać rozwiązanie wzorcowe, wystarczy przyspieszyć rozwiązanie iteracyjne. W tym celu zauważymy, że jest niewiele wartości parametru \(r\), które opłaca się rozważać. Niech \(m\) oznacza liczbę niezerowych cyfr liczby \(n\). Niech dalej \(S'\) oznacza maksymalny sufiks zapisu dziesiętnego liczby \(n\) postaci \(99\dots 9 ABCDEFG\), przy czym litery oznaczają odpowiednie cyfry w zapisie liczby; jeśli takiego sufiksu \(S'\) nie ma (np. gdy \(n\) jest małe), niech \(S'\) oznacza cały zapis liczby \(n\). Wówczas wystarczy rozważyć wartości \(r \in \{m,m-1,\ldots,m-7\}\) oraz liczbę \(r_0\) taką, że po wykonaniu \(r_0\) rotacji sufiks \(S'\) znajdzie się na początku liczby.
Faktycznie, jeśli wykonamy mniej niż \(r_0\) rotacji, to wynik odejmowania \(\underbrace{99 \dots 9}_{s\text{ cyfr}} - S\) jak w poprzednim rozwiązaniu będzie większy niż \(10^7\). Jeśli natomiast wykonamy \(r\) rotacji dla \(r_0 < r < m-7\), to równie dobrze możemy wykonać \(r_0\) rotacji, gdyż wszystkie kolejne będą tylko przenosiły dziewiątki z początku liczby na koniec.
Ostatecznie mamy tylko \(O(1)\) liczb \(r\) do rozważenia (i można je wyznaczyć w czasie \(O(k)\)). Otrzymujemy rozwiązanie działające w czasie \(O(k)\), które przechodziło wszystkie podzadania.