Katakanlah Anda memiliki dadu 20 sisi. Anda mulai menggulung dadu itu dan harus menggulungnya beberapa lusin kali sebelum akhirnya Anda menggulung semua 20 nilai. Anda bertanya-tanya, berapa banyak gulungan yang saya butuhkan sebelum mendapatkan peluang 50% untuk melihat semua 20 nilai? Dan berapa banyak gulungan n
dadu sisi yang harus saya roll sebelum menggulung semua n
sisi?
Setelah beberapa penelitian, Anda menemukan bahwa ada rumus untuk menghitung kemungkinan menggulirkan semua n
nilai setelah r
gulungan.
P(r, n) = n! * S(r, n) / n**r
di mana S(a, b)
menunjukkan angka Stirling dari jenis kedua , jumlah cara untuk mempartisi sekumpulan objek n (masing-masing gulungan) ke dalam himpunan bagian yang tidak kosong (setiap sisi).
Anda juga menemukan urutan OEIS , yang akan kami panggil R(n)
, yang sesuai dengan yang terkecil di r
mana P(r, n)
setidaknya 50%. Tantangannya adalah menghitung n
jangka waktu urutan ini secepat mungkin.
Tantangan
- Diberikan
n
, cari yang terkecil dir
manaP(r, n)
lebih besar atau sama dengan0.5
atau 50%. - Kode Anda secara teoritis harus menangani bilangan bulat non-negatif
n
sebagai input, tetapi kami hanya akan menguji kode Anda dalam kisaran1 <= n <= 1000000
. - Untuk mencetak gol, kami akan mengambil total waktu yang dibutuhkan untuk menjalankan
R(n)
pada input1
melalui10000
. - Kami akan memeriksa apakah solusi Anda sudah benar dengan menjalankan versi kami
R(n)
pada output Anda untuk melihat apakahP(your_output, n) >= 0.5
danP(your_output - 1, n) < 0.5
, yaitu bahwa output Anda sebenarnya yang terkecilr
untuk yang diberikann
. - Anda dapat menggunakan definisi apa pun untuk
S(a, b)
dalam solusi Anda. Wikipedia memiliki beberapa definisi yang mungkin bermanfaat di sini. - Anda dapat menggunakan built-in dalam solusi Anda, termasuk yang menghitung
S(a, b)
, atau bahkan yang menghitungP(r, n)
secara langsung. - Anda dapat melakukan hardcode hingga 1000 nilai
R(n)
dan sejuta angka Stirling, meskipun tidak satu pun dari ini adalah batas keras, dan dapat diubah jika Anda dapat membuat argumen yang meyakinkan untuk menaikkan atau menurunkannya. - Anda tidak perlu memeriksa setiap kemungkinan
r
antaran
dan yangr
kami cari, tetapi Anda perlu menemukan yang terkecilr
dan tidak sembarangr
tempatP(r, n) >= 0.5
. - Program Anda harus menggunakan bahasa yang dapat dijalankan secara bebas di Windows 10.
Spesifikasi komputer yang akan menguji solusi Anda i7 4790k, 8 GB RAM
. Terima kasih kepada @DJMcMayhem karena menyediakan komputernya untuk pengujian. Jangan ragu untuk menambahkan waktu tidak resmi Anda sendiri untuk referensi, tetapi waktu resmi akan diberikan nanti setelah DJ dapat mengujinya.
Uji kasus
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
Beri tahu saya jika Anda memiliki pertanyaan atau saran. Semoga berhasil dan optimisasi yang baik!
sumber
Jawaban:
Python + NumPy, 3,95 Detik
Cobalah online!
Bagaimana itu bekerja
Ini menggunakan seri bentuk-tertutup untuk P ( r , n ), dan turunannya sehubungan dengan r , disusun ulang untuk stabilitas numerik dan vektorisasi, untuk melakukan pencarian metode Newton untuk r sehingga P ( r , n ) = 0,5, pembulatan r ke integer sebelum setiap langkah, sampai langkah bergerak r kurang dari 3/4. Dengan tebakan awal yang baik, ini biasanya hanya membutuhkan satu atau dua iterasi.
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 )
sumber
0.366512
itu adalahlog
sesuatu yang sudah lama ada. Akan digunakan-log(log(2)
dalam iterasi berikutnya. Kedua, gagasan untuk menggunakan metode Newton juga sangat pintar dan saya senang melihat bahwa ini bekerja dengan sangat baik. Ketiga, saya hampir pasti akan mencuriexp(log(binom(n, i+1)) + r * log((n-i-1)/n))
: P Kudos pada jawaban yang bagus! : Dnumpy
impor kefrom numpy import *
dan untuk beberapa alasan waktu pada dasarnya turun ke 0 ... Coba online ?r
, karena perkiraan awal Anda sudah cukup baik. Berharap dapat melihat Anda di PPCG sekali lagi, dan maaf untuk semuanya.