Omówienie zadania Gra w dzielniki (III etap XXVI OI)

Dostajemy licznik początkowo równy \(0\) oraz nieskończony ciąg liczb od \(1\) do \(k\), niezależnie wybranych z rozkładu jednostajnego. Możemy wykonać operację dostania kolejnej liczby z ciągu i jeśli dzieli ona \(x\) to zwiększenia o nią licznika. Należy doprowadzić do stanu \(x = n\), wykonując jak najmniej kroków.

Jednokrotne uruchomienie naszego programu da nam liczbę ruchów, które wykonaliśmy podczas jednej losowej gry, ale taka pojedyncza wartość niekoniecznie powie nam coś o tym, jak nasz program sobie radzi, ponieważ jest ona mocno zależna od tego, jakie liczby zostały wylosowane podczas gry. Aby uzyskać bardziej wiarygodne wyniki, należy tę symulację powtórzyć wielokrotnie. Poniższe rozwiązania zostały przetestowane na symulacji \(10\,000\) gier.

Rozwiązanie zachłanne: zwiększaj zawsze, jeśli możesz

Narzucające się rozwiązanie jest takie, żeby zwiększać zawsze, gdy \(y\) jest dzielnikiem \(x\). Prowadzi to do częstego przechodzenia przez liczby pierwsze oraz liczby mające mało dzielników, co prowadzi do częstych sytuacji, gdy trzeba wykonać długi ciąg wywołań funkcji nastepna(), zanim możliwe będzie powiększenie licznika (notabene: często o bardzo małą wartość).

Na teście \(n = 50\,000\), \(k = 200\) daje to średnio \(50\,000\) operacji na jedną rozgrywkę, przy czym dla niektórych gier wystarczyło \(37\,000\) operacji, a dla niektórych gier było potrzebne aż \(65\,000\) operacji.

Rozwiązanie zachłanne: próbuj zawsze zwiększać o dużo

Intuicyjnie czuć, że czasami warto poczekać na większą liczbę, bo daje ona większy skok oraz daje pewność, że skoro \(x\) był podzielny przez nią, to po powiększeniu nadal będzie. Można na sztywno ustalić jakiś limit, np. że akceptujemy tylko liczby większe od \(\frac{k}{2}\).

Na teście \(n = 50\,000\), \(k = 200\) daje to średnio \(35\,500\) operacji na jedną rozgrywkę, przy rozstrzale od \(24\,000\) do \(56\,000\) operacji.

Rozwiązanie zachłanne: próbuj zwiększać do liczb mających dużo dzielników

Można zauważyć, że lepiej unikać liczb pierwszych, z których potem trudno się wydostać, a także liczb mających same duże dzielniki, albo mało małych dzielników.

Najprostsza wersja takiego rozwiązania (przechodzenie do liczb mających co najmniej \(10\) dzielników) na teście \(n = 50\,000\), \(k = 200\) daje średnio \(28\,000\) operacji, przy rozstrzale od \(22\,000\) do \(36\,000\) operacji.

Rozwiązania wzorcowe

Zadanie można rozwiązać optymalnie, tzn. skonstruować program, dla którego wartość oczekiwana liczby wykonanych operacji jest optymalna.

Użyjemy metody programowania dynamicznego. Zauważamy najpierw, że decyzja zależy jedynie od bieżącego stanu licznika \(x\) oraz wylosowanej liczby \(y\). Niech więc wartość \(x\) jest stanem w naszej grze. Wartością stanu dla takiej liczby jest \(E(x)\), czyli wartość oczekiwana liczby ruchów pozostałych do końca gry przy założeniu, że dalsze decyzje będą podejmowane optymalnie.

Stany wyznaczamy w kolejności malejących wartości \(x\), zaczynając od \(E(n) = 0\).

Co możemy zrobić dla stanu \(x\)? Ustalić zbiór \(D_x\) dzielników \(y\) liczby \(x\), dla których podejmiemy decyzję zwieksz(). Spowoduje to, że będziemy oczekiwać średnio \(\frac{k}{|D_x|}\) ruchów, aż dostaniemy element z \(D_x\), a dalej w grze pozostanie nam do wykonania jeszcze średnia arytmetyczna liczby ruchów dla stanów \(E(x+y)\) dla \(y \in D_x\): \[E(x) = \frac{k + \sum_{y \in D_x} E(x+y)}{|D_x|}.\]

Takich zbiorów \(D_x\) niestety jest wykładniczo wiele względem liczby dzielników. Szczęśliwie, spośród podzbiorów dzielników \(x\) interesuje nas zawsze tylko po jednym o zadanej mocy (o najmniejszej sumie ze stanów \(E(x+y)\)). A zatem możemy posortować zbiór interesujących stanów \(E(x+y)\), z których moglibyśmy potencjalnie chcieć korzystać, i rozpatrywać jedynie prefiksy tak posortowanego ciągu. Oczywiście oprócz tego zapamiętujemy dla każdego \(x\) optymalny, wybrany zbiór dzielników \(D_x\), i potem gramy według tego zbioru.

To rozwiązanie wymaga złożoności czasowej \(O(nk\log k)\) na preprocessing. Po tym możemy już rozegrać dowolnie wiele gier dla tych samych wartości \(n\) i \(k\), po prostu czekając na któryś z akceptowalnych dzielników ze zbiorów \(D_x\). Taka symulacja wymaga czasu \(O(E(0))\).

Eksperyment pokazuje, że dla \(n = 50\,000\), \(k = 200\) daje nam to średnio tyle, ile obiecuje wartość oczekiwana, czyli około \(17\,000\) ruchów, przy rozstrzale od \(13\,000\) ruchów do \(21\,000\) ruchów.