Omówienie zadania Kasyno (I etap XXXII OI)

Intuicja

Zastanówmy się, co się dzieje, gdy maszyna wylosuje dużą liczbę pierwszą? Jeśli $x$ jest pierwsze, to wynik naszego zapytania będzie różny od $1$ tylko, gdy zapytamy o jakąś wielokrotność $x$ . Wśród liczb od $1$ do $n$ liczb pierwszych jest rzędu $\frac{n}{\ln n}$ , więc w trakcie rozgrywki powinniśmy choć raz na jakąś natrafić. Co więcej, powinniśmy trafić na jakąś, która jest większa niż $\frac{n}{2}$ , co oznacza, że tylko pytanie o dokładnie tę liczbę pierwszą zwróci wynik różny od $1$ . Szanse na trafienie dokładnie tej liczby są nikłe, co oznacza, że w takiej sytuacji na pewno będziemy musieli szturchnąć maszynę, aby wylosowała ponownie.

Podsumowując, istnieje dosyć spory zbiór liczb, dla których jedynym rozwiązaniem jest wylosowanie ponownie. Stąd wnioskujemy, że musimy ograniczyć się do jakiegoś podzbioru liczb, które będziemy próbowali zgadnąć, a resztę porzucimy i wylosujemy ponownie.

Z perspektywy rozkładów na liczby pierwsze

Mając już pewną intuicję, postaramy się ją nieco sformalizować i uogólnić.

Popatrzmy na rozkład ukrytej liczby na liczby pierwsze. Oznaczmy jako $p_{1}, p_{2}, \dots, p_{k}$ kolejne liczby pierwsze od $1$ do $n$ . Zapiszmy $x$ jako następujący iloczyn: $x = p_{1}^{a_{1}} p_{2}^{a_{2}} . . . p_{k}^{a_{k}}$ . Każdą liczbę od $1$ do $n$ możemy jednoznacznie przedstawić jako właśnie taki ciąg wykładników $a_{i}$ . Jak wygląda zatem pojedyncze zapytanie w kontekście ciągów wykładników? Powiedzmy, że zadajemy pytanie o $y = p_{1}^{b_{1}} p_{2}^{b_{2}} \dots p_{k}^{b_{k}}$ . W odpowiedzi otrzymujemy $nwd (x, y) = p_{1}^{c_{1}} p_{2}^{c_{2}} \dots p_{k}^{c_{k}}$ . Nietrudno sprawdzić, że $c_{i} = min (a_{i}, b_{i})$ !

Wśród liczb do $10^{18}$ , liczbą o największej liczbie dzielników pierwszych jest $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47 = 614 889 782 588 491 410$ . Ma ona $15$ dzielników pierwszych. Stąd widzimy, że ciąg $a_{i}$ na wszystkich poza co najwyżej $15$ pozycjami jest równy $0$ . Za to, patrząc z innej strony, nasze pytanie wskazuje mały podzbiór pozycji (co najwyżej $15$ ) i pyta dla każdej, czy wartość na tej pozycji jest większa niż $0$ . Tak naprawdę dowiadujemy się trochę więcej, ale nie musimy na to zwracać większej uwagi. Faktycznie, mając w ręku wszystkie liczby pierwsze w rozkładzie $x$ , możemy już dojść do tego, ile wynosi dokładnie $x$ , w co najwyżej $15$ pytaniach, zwyczajnie pytając o $p^{w}$ , przy czym $p^{w + 1} > n$ dla każdej z tych liczb pierwszych. Od tej pory nie będziemy skupiać się za bardzo nad tym, jaki dokładnie jakaś liczba pierwsza ma wykładnik w rozkładzie $x$ , a na tym czy jest od większy od $0$ . Mając już takie spojrzenie na nasze zadanie łatwo nam zauważyć dlaczego nasza intuicja była trafna. Pojedyncza liczba $x$ ma ukryty co najwyżej kilkunastoelementowy podzbiór liczb pierwszych (a rozważanych liczb pierwszych jest więcej niż $10^{16}$ ) i naszym zadaniem jest odgadnięcie tego podzbioru za pomocą pytań o jego przecięcie z także co najwyżej kilkunastoelementowym podzbiorem liczb pierwszych. Z tej perspektywy problem wydaje się on nie do rozwiązania... Na szczęście liczby pierwsze pojawiają się w rozkładzie $x$ z różnym prawdopodobieństwem!

Liczby gładkie

Jak wcześniej zauważyliśmy, mając naszą ograniczoną liczbę zapytań, nie jesteśmy w stanie zapytać o przeważającą większość liczb pierwszych, które mogą pojawić się w rozkładzie liczby $x$ . Z tego powodu musimy ograniczyć się do małego podzbioru liczb pierwszych i liczyć na to, że $x$ posiada tylko te liczby w swoim rozkładzie.

Naturalnym wyborem podzbioru liczb pierwszych będą wszystkie liczby pierwsze mniejsze niż jakaś ustalona przez nas stała $L$ . Intuicja za tym jest taka, że $2$ występuje w co drugiej liczbie, $3$ w co trzeciej, a $220 100 164 936 457 501$ występuje w rozkładzie naprawdę niewielu liczb w porównaniu do $2$ . W tym momencie możemy wykonać lokalny test i sprawdzić, ile jest mniej więcej liczb, które w swoim rozkładzie mają tylko liczby pierwsze mniejsze niż $L$ . W naszym teście wystarczy, że np. milion razy wylosujemy liczbę i sprawdzimy, czy po wydzieleniu z niej rozważanych czynników pierwszych otrzymamy $1$ . Zliczamy liczbę takich prób i patrzymy jaki odsetek nam wyszedł. Dla $L = 10 000$ około $0, 16 %$ liczb składało się tylko z dzielników pierwszych mniejszych niż $L$ . Takie liczby nazywają się liczbami $L$ -gładkimi.

Skąd mieć pewność?

No dobrze, wiemy już, że całkiem często (jak na nasze potrzeby) wylosowana liczba $x$ jest $L$ -gładka. Ale skąd mamy mieć pewność, że liczba, na którą aktualnie patrzymy, nie ma żadnego dzielnika pierwszego większego niż $L$ ? Teraz postaramy się odpowiedzieć na to pytanie.

Dla ustalenia uwagi powiedzmy, że nasz algorytm jest następujący:

Losujemy $x$ .
Iterujemy się po wszystkich liczbach pierwszych mniejszych niż $L$ .
Dla każdej liczby pierwszej $p$ zadajemy pytanie o $p^{w}$ , takie, że $p^{w + 1} > n$ .
Mnożymy wszystkie odpowiedzi.

Niech iloczyn wszystkich odpowiedzi wynosi

ans

. W tym momencie użyjemy kolejnej własności tego, że podzbiór liczb pierwszych, które wybraliśmy, to wszystkie mniejsze niż

L

. W naszym algorytmie spytaliśmy o wszystkie liczby pierwsze mniejsze niż

L

, więc wiemy, że jeżeli

x \neq ans

, to

x

musi mieć jakiś dzielnik pierwszy przynajmniej

L

. Ale jeśli zachodzi nierówność

ans \cdot L > n

, to mamy pewność, że taka dodatkowa liczba pierwsza w rozkładzie

x

nie istnieje i

ans

jest rzeczywiście równy

x

Możemy teraz podliczyć, ile rozgrywek spodziewamy się wygrać, stosując taką strategię z parametrem $L = 10 000$ . Rozpatrzenie pojedynczej liczby kosztuje nas $1229$ zapytań, ponieważ dokładnie tyle jest liczb pierwszych mniejszych niż $L$ . Będziemy więc w stanie przejrzeć około $8100$ ukrytych liczb $x$ i dla nich stwierdzić, czy jest ona $L$ -gładka. Z naszej empirycznej próby wynika, że takich liczb, nie większych niż $10^{18}$ , powinno być $8100 \cdot 0, 0016 \approx 12$ . Za takie rozwiązanie powinniśmy już otrzymać około $30$ punktów!

Wszystkie rozwiązania od teraz będą opierały się na wyżej przedstawionym algorytmie z modyfikacjami w celu optymalizacji liczby zapytań. Zamysł będzie zawsze taki sam, czyli będziemy sprawdzać liczby pierwsze, aż iloczyn $ans \cdot P$ będzie większy niż $n$ , przy czym $P$ oznacza najmniejszą niesprawdzoną jeszcze liczbę pierwszą.

Grupowanie zapytań

Wróćmy na chwilę do reprezentacji naszego problemu z sekcji Z perspektywy rozkładów na liczby pierwsze. Tam powiedzieliśmy, że mając informację o tym, które liczby pierwsze są w rozkładzie $x$ , wystarczy nam co najwyżej $15$ zapytań, aby "dokończyć" rozwiązanie. Pójdziemy tym tropem i zmodyfikujemy nasz algorytm. Od teraz będziemy pytać o wiele liczb pierwszych naraz, dobierając je w grupy. W jednej grupie iloczyn wszystkich liczb pierwszych będzie nie większy niż $n$ , aby można było zadać o niego pytanie. Liczby dobierzemy w grupy idąc od najmniejszej liczby pierwszej i dorzucając do grupy, jeśli warunek dla grupy będzie dalej spełniony po dodaniu. W przeciwnym przypadku będziemy tworzyć nową grupę. Teraz, w naszym algorytmie, będziemy iterować się po grupach i pytać o iloczyn wszystkich liczb w grupie. Następnie sprawdzimy, które liczby pierwsze z grupy występują z dodatnim wykładnikiem, i dla nich już zapytamy osobno o najwyższą potęgę mieszczącą się w $n$ . W ten sposób redukujemy liczbę pytań kilkukrotnie, co daje nam dużo dodatkowych punktów.

Wczesne przerwania

Kluczową optymalizacją pozwalającą na zdobycie maksymalnej liczby punktów są wczesne przerwania. Wyobraźmy sobie sytuację, w której po zapytaniu o wszystkie liczby pierwsze mniejsze niż $100$ iloczyn odpowiedzi wynosi $1$ (lub jakaś mała liczba). Czy warto kontynuować sprawdzanie tej liczby? Aby sprawdzić te liczby zadaliśmy kilka pytań (dzięki grupowaniu), a żeby dokończyć sprawdzanie będziemy musieli wydać jeszcze kilkaset. Nasz $x$ na razie nie rokuje dobrze, ponieważ na podstawie naszych informacji wiemy, że musi być iloczynem liczb pierwszych większych niż $100$ , a takich jest bardzo mało. W takiej sytuacji rozsądnym byłoby przedwczesne przerwanie naszych poszukiwań i wylosowanie $x$ na nowo.

Postarajmy się przekuć powyższą obserwację na optymalizacje w naszym algorytmie. Chcielibyśmy po każdym wykonanym przez nas zapytaniu podjąć decyzję, czy szturchnąć maszynę, czy kontynuować poszukiwania. Rozwiązanie tego problemu optymalnie przekracza nasze możliwości, więc postaramy się wycisnąć tyle, ile będziemy w stanie. Następne kilka sekcji będzie poświęcone opisowi rozwiązania wzorcowego i optymalizacji w nim zawartych.

Zarys modelu

W rozwiązaniu wzorcowym grupujemy liczby pierwsze jak wyżej opisano. Przeglądamy kolejno te grupy i dla każdej z nich najpierw wykonujemy zapytanie, a następnie dopytujemy o dokładne wykładniki liczb pierwszych. Dokładny sposób dopytywania zostanie opisany poniżej. Po wykonaniu pierwszego pytania w grupie będziemy podejmować decyzję czy przerwać; to samo zrobimy po odkryciu wszystkich wykładników. Pojedyncza decyzja będzie polegała na stwierdzeniu, czy nasz aktualny dzielnik $x$ jest większy niż przewidziany próg. Wszystkie takie progi będą parametrami naszego rozwiązania i niżej zostanie opisany sposób ich znalezienia. Jak wcześniej, jeśli w jakimkolwiek momencie będziemy mieli pewność, że znamy $x$ , to odpowiadamy i kończymy interakcję.

Obliczenie progów dla momentów decyzyjnych

W rozwiązaniu wzorcowym zastosowano podejście korzystające z metody wyżarzania (polecamy wersję angielską artykułu). Tylko czym jest funkcja, dla której obliczamy optimum? Argumentami funkcji są oczywiście wartości progów dla momentów decyzyjnych. W idealnym świecie wynikiem funkcji byłoby $\frac{correct}{coins}$ , przy czym $correct$ oznacza liczbę ukrytych wartości $x$ , które odgadliśmy, a $coins$ oznacza liczbę monet potrzebną do uzyskania takiego wyniku. Oczywiście wliczamy monety, które zostały wydane w próbach, które zakończyły się odgadnięciem ukrytej liczby, jak i tych próbach, które zakończyliśmy przelosowaniem ukrytej liczby. Te dwie wartości obliczylibyśmy uwzględniając wyniki dla każdej z $n$ możliwych ukrytych wartości $x$ . Niestety, nie posiadamy wystarczająco mocy obliczeniowej, żeby to zrobić. Z tego powodu będziemy musieli ograniczyć się do stałego podzbioru wartości $x$ , którego rozmiar jest dla nas akceptowalny. Bardzo ważnym jest aby ten zbiór był niezmienny, ponieważ wyniki funkcji dla tych samych argumentów i losowych podzbiorów $x$ mają dostatecznie duże wahania, aby nasz algorytm optymalizacji mógł się zaciąć na jakimś punkcie, ponieważ przy jego ewaluacji trafił mu się bardzo fartowny podzbiór wartości $x$ .

Warto wspomnieć, że od tego momentu nasz algorytm powinien pracować na logarytmach wartości progów momentów decyzyjnych a nie na ich rzeczywistych wartościach. Powód tej, na pierwszy rzut oka dziwnej, reprezentacji jest następujący: Przemnożenie wartości aktualnie znanego dzielnika $x$ przez jakieś $c$ jest podobnie trudne, niezależnie od tego jaka jest wartość tego dzielnika. Taka reprezentacja jest dużo bardziej wiarygodna niż reprezentacja, w której przejście z $10$ do $20$ ma "trudność" $10$ , a przejście z $100 000 000$ do $200 000 000$ ma "trudność" $100 000 000$ . Algorytm wyżarzania będzie zmieniał wartości progów o wartości w tej samej skali i z tego powodu pojedynczy krok powinien zawsze reprezentować zmianę tego samego rzędu wielkości. Alternatywnie, można by było zmodyfikować algorytm wyżarzania, aby mnożył wartości przez ustalony współczynnik zamiast go dodawać, ale zmienienie skali na logarytmiczną jest bardziej ogólną metodą i warto ją znać, aby nie musieć zaglądać do wnętrzności samego algorytmu optymalizacyjnego.

Po krótkiej dygresji wracamy do naszego algorytmu. Po uruchomieniu optymalizacji dla dwóch momentów decyzyjnych na każdy blok, czyli około kilku tysięcy parametrów, możemy zauważyć, że na naszym zbiorze treningowym (stałym podzbiorze wartości $x$ definiującym optymalizowaną funkcję) osiągamy zaskakująco dobre rezultaty. Jednakże, gdy uruchomimy nasze rozwiązanie na losowych testach, to wyniki nie są już takie czarujące... Skąd to wynika? Zjawisko, które zaobserwowaliśmy, w ogólności nazywa się przeuczeniem, co oznacza, że nasz zbiór parametrów jest potencjalnie zbyt duży, bo podczas "treningu" był w stanie "zapamiętać" jakie przypadki testowe kończą się sukcesem, a jakie nie, i przy tych drugich nauczył się je odcinać zbyt wcześnie niż byłoby to w ogólności optymalne. Aby zaradzić temu problemowi możemy znacząco zmniejszyć liczbę parametrów. Teraz pytanie na które musimy sobie odpowiedzieć, to które parametry pozostawić? W tym zadaniu dużo rzeczy możemy zrobić eksperymentalnie – popróbować różne możliwości i wybrać te, które najlepiej działają na losowych testach. W tym momencie przedstawię pewne intuicje stojące za dobrym doborem podzbioru parametrów, przy którym unikamy przeuczenia, a jednak pozostawiamy naszemu algorytmowi wystarczającą siłę wyrazu pozwalającą na sprawne przerywanie słabo rokującej próby.

Intuicyjnie, największa wartość powinna być w przerywaniu prób po wykonaniu kilku zapytań niż po wykonaniu kilkuset, ponieważ zaoszczędzamy potencjalnie znacznie więcej. Stąd wnioskujemy, że powinniśmy przydzielić więcej momentów decyzyjnych wcześniejszym grupom niż późniejszym. W szczególności, na podstawie pierwszego pytania, w którym pytamy o to, które z wykładników $2, 3, 5, 7, . . .$ są niezerowe, będziemy przerywać wykonanie kilku lub nawet kilkunastu procent wszystkich prób! Rozumowanie za tym stojące jest takie, że jest aż kilka procent szans na to, że $x$ jest dużą liczbą pierwszą, a jak już wcześniej powiedzieliśmy, próba odgadnięcia takiej liczby skończy się źle. W rozwiązaniu wzorcowym przydzieliliśmy momenty decyzyjne dla około $5$ pierwszych grup na moment po pierwszym pytaniu w grupie, dla około $10$ pierwszych grup moment decyzyjny po poznaniu dokładnych wartości wykładników i około $10$ momentów decyzyjnych po poznaniu dokładnych wartości wykładników dla grup o wykładniczo rosnących numerach, czyli np. $15, 40, 100, 300, 700, . . .$

Bonus: Dopytywanie o wykładniki

W tej sekcji skupimy się na jak najlepszym dopytywaniu o dokładne wartości wykładników, jeśli wiemy, że są one dodatnie. Można by było zastanawiać się, po co nam taka optymalizacja, skoro już sobie wcześniej powiedzieliśmy, że przy udanej próbie dodatkowych pytań będzie co najwyżej $15$ . Jednakże przy nieudanych próbach, które często trwają kilka pytań, różnica między zadaniem $8$ pytań, a zadaniem $4$ pytań to oszczędność rzędu $50 %$ !

Dla ustalenia uwagi, powiedzmy, że rozwiązujemy ten problem dla pierwszej grupy zawierającej liczby $2, 3, 5, . . .$ . Dla pozostałych grup będzie to wyglądało analogicznie. Powiedzmy, że liczby $2, 5$ oraz $7$ występują z dodatnim wykładnikiem. Nasze pierwsze rozwiązanie najpierw by zapytało o $2^{59}$ , potem o $5^{25}$ , potem o $7^{21}$ , itd. Jednakże szansa na to, że $x$ będzie podzielne przez np. $2^{30}$ , to około $\frac{1}{2^{29}}$ . Zamysł jest teraz taki, że nie chcemy marnować "miejsca" w naszym pojedynczym zapytaniu na rzeczy, które mają bardzo małą szansę wystąpienia. Dużo lepszym pomysłem jest najpierw zapytanie o $2^{19} \cdot 5^{8} \cdot 7^{7}$ i następnie dopytanie o $2$ , $5$ i $7$ z osobna, jeśli ich wykładniki to odpowiednio przynajmniej $19$ , $8$ i $7$ , niż zapytanie o nie od razu. Zwyczajnie szansa na to, że po tym pierwszym pytaniu już nie będziemy musieli o nic dopytywać, jest znacznie większa niż szansa na to, że będziemy musieli dopytać o wszystkie trzy.

Mówiąc dokładniej, w pojedynczym kroku algorytmu wiemy, że dla liczb $p_{1}, p_{2}, \dots, p_{k}$ wykładniki $a_{1}, a_{2}, . . ., a_{k}$ spełniają nierówności $a_{1} \geq b_{1}, a_{2} \geq b_{2}, . . ., a_{k} \geq b_{k}$ . Zastanawiamy się, jakie pytanie powinniśmy skonstruować. Dla ustalonego $i$ , prawdopodobieństwo, że $a_{i} \geq b_{i} + 1$ , jest równe około $\frac{1}{p_{i}}$ . Patrząc ogólniej, prawdopodobieństwo, że $a_{i} \geq b_{i} + c$ , jest równe około $\frac{1}{p_{i}^{c}}$ . Pojedynczym pytaniem zawierającym w sobie $p_{i}^{b_{i} + c}$ dowiemy się, czy $a_{i} \geq b_{i} + c$ zachodzi, czy może $a_{i} \in {b_{i}, b_{i} + 1, . . ., b_{i} + c - 1}$ . Dla każdej sytuacji, w której otrzymujemy dokładną wartość wykładnika, możemy obliczyć nasz zysk jako $p_{i}^{d}$ , jeśli od teraz wiemy, że $a_{i} = b_{i} + d$ . Szansa na uzyskanie dokładnie takiego zysku to około $\frac{1}{p_{i}^{d}} \cdot (1 - \frac{1}{p_{i}})$ . Pierwszy czynnik wygląda znajomo, a drugi czynnik bierze się z tego, że ten wykładnik nie może być większy. Zysk z zapytania obliczamy jako suma po iloczynach zysku i prawdopodobieństw poszczególnych zdarzeń. Nasz algorytm będzie tworzyć następne zapytanie, zachłannie zwiększając odpowiedni wykładnik liczby pierwszej w zapytaniu do wartości, która zmaksymalizuje różnicę w zysku podzieloną przez koszt tej zmiany, gdzie kosztem jest mnożnik, przez który musieliśmy przemnożyć nasze zapytanie.

W praktyce ten algorytm działa szybko, ponieważ, poza pierwszymi kilkoma grupami, rozmiary grup są bardzo małe (rzędu kilku elementów). Po zastosowaniu tej optymalizacji przy bardzo dobrym, wczesnym przerywaniu osiągamy zauważalny wzrost w liczbie wygrywanych rozgrywek. To zadanie pozostaje jako pytanie otwarte, a autorzy nie wiedzą jak dobre rozwiązania tego problemu są możliwe, więc zachęcamy do własnych poszukiwań! Rozwiązanie wzorcowe osiąga stabilnie ponad $2100$ wygranych gier.

Opis przygotowano w ramach projektu "Mistrzostwa w Algorytmice i Programowaniu - Uczniowie" - zadania finansowanego ze środków Ministerstwa Cyfryzacji.