Powiedzmy, że masz 20-stronną kostkę. Zaczynasz rzucać tą kością i musisz rzucić ją kilkadziesiąt razy, zanim w końcu rzucisz wszystkie 20 wartości. Zastanawiasz się, ile rzutów potrzebuję, zanim otrzymam 50% szansy na zobaczenie wszystkich 20 wartości? A ile rzutów n
kostką jednostronną muszę wykonać, zanim wykonam rzut ze wszystkich n
stron?
Po kilku badaniach okazało się, że istnieje wzór do obliczania szansy na wyrzucenie wszystkich n
wartości po r
rzutach.
P(r, n) = n! * S(r, n) / n**r
gdzie S(a, b)
oznacza liczby Stirlinga drugiego rodzaju , liczbę sposobów podziału zestawu n obiektów (każda rolka) na k niepustych podzbiorów (z każdej strony).
Znajdziesz również sekwencję OEIS , którą nazwiemy R(n)
, która odpowiada najmniejszemu, r
gdzie P(r, n)
wynosi co najmniej 50%. Wyzwanie polega na n
jak najszybszym obliczeniu th tej sekwencji.
Wyzwanie
- Biorąc pod uwagę an
n
, znajdź najmniejsze,r
gdzieP(r, n)
jest większe lub równe0.5
lub 50%. - Twój kod powinien teoretycznie obsługiwać nieujemną liczbę całkowitą
n
jako dane wejściowe, ale będziemy testować twój kod tylko w zakresie1 <= n <= 1000000
. - Do punktacji, będziemy brać całkowity czas potrzebny do uruchomienia
R(n)
na wejściach1
dzięki10000
. - Sprawdzimy, czy twoje rozwiązania są poprawne, uruchamiając naszą wersję
R(n)
na twoim wyjściu, aby sprawdzić, czyP(your_output, n) >= 0.5
iP(your_output - 1, n) < 0.5
, tj. Czy twoje wyjście jest w rzeczywistości najmniejszer
dla danegon
. - Możesz użyć dowolnej definicji
S(a, b)
w swoim rozwiązaniu. Wikipedia ma kilka definicji, które mogą być tutaj pomocne. - Możesz używać wbudowanych rozwiązań, w tym tych, które obliczają
S(a, b)
, a nawet tych, które obliczająP(r, n)
bezpośrednio. - Możesz zakodować na stałe do 1000 wartości
R(n)
i miliona liczb Stirlinga, chociaż żadna z nich nie jest twardym limitem, i można je zmienić, jeśli będziesz w stanie przekonująco argumentować za ich podniesieniem lub obniżeniem. - Nie musisz sprawdzać wszystkich możliwych
r
międzyn
tymr
, czego szukamy, ale musisz znaleźć najmniejsze,r
a nie tylkor
gdziekolwiekP(r, n) >= 0.5
. - Twój program musi używać języka, który można swobodnie uruchamiać w systemie Windows 10.
Specyfikacje komputera, który przetestuje twoje rozwiązania, są i7 4790k, 8 GB RAM
. Dzięki @DJMcMayhem za udostępnienie komputera do testowania. Możesz dodać własne nieoficjalne terminy w celach informacyjnych, ale oficjalny harmonogram zostanie podany później, gdy DJ będzie mógł go przetestować.
Przypadki testowe
n R(n)
1 1
2 2
3 5
4 7
5 10
6 13
20 67 # our 20-sided die
52 225 # how many cards from a huge uniformly random pile until we get a full deck
100 497
366 2294 # number of people for to get 366 distinct birthdays
1000 7274
2000 15934
5000 44418
10000 95768
100000 1187943
1000000 14182022
Daj mi znać, jeśli masz jakieś pytania lub sugestie. Powodzenia i dobrej optymalizacji!
źródło
Odpowiedzi:
Python + NumPy, 3,95 sekundy
Wypróbuj online!
Jak to działa
Korzysta z serii zamkniętej dla P ( r , n ) i jego pochodnej w odniesieniu do r , przestawionej pod względem stabilności numerycznej i wektoryzacji, aby przeprowadzić metodę Newtona w poszukiwaniu r tak, że P ( r , n ) = 0,5, zaokrąglenie r oznacza liczbę całkowitą przed każdym etapie, do momentu, aż etap r o mniej niż 3/4. Przy dobrym wstępnym przypuszczeniu zwykle zajmuje to tylko jedną lub dwie iteracje.
x i = log (1 - i / n ) = log (( n - i ) / n )
cx i = log ( n ! / (( n - i - 1)! ⋅ n i + 1 )
y i = cx i + cx n - i - 2 - cx n - 1 = log binom ( n , i + 1)
z i = (-1) i + 1 ⋅ binom ( n ,i + 1) ⋅ (( n - i - 1) / n ) r
1 + ∑ z i = n! ⋅ S ( r , n ) / n R = P ( R , n )
z i ⋅ x i + 1 = (1) i + 1 ⋅ Binom ( n , i + 1) ⋅ (( n - i - 1) / n ) r log (( n - i - 1) / n)
∑ z i ⋅ x i + 1 = d / d r P ( r , n )
źródło
0.366512
byłolog
coś sprzed wieków. Użyje-log(log(2)
w mojej następnej iteracji. Po drugie, pomysł użycia metody Newtona jest również bardzo sprytny i cieszę się, że to działa tak dobrze. Po trzecie, prawie na pewno zamierzam ukraśćexp(log(binom(n, i+1)) + r * log((n-i-1)/n))
: P Kudos na świetną odpowiedź! : Dnumpy
import nafrom numpy import *
i z jakiegoś powodu czas spadł do w zasadzie 0 ... Wypróbuj online ?r
, ponieważ początkowe przybliżenie jest już całkiem dobre. Mam nadzieję, że zobaczymy się jeszcze raz w PPCG i przepraszam za wszystko.