[Ini adalah pertanyaan mitra untuk Menghitung probabilitas dengan tepat ]
Tugas ini adalah tentang menulis kode untuk menghitung probabilitas secara tepat dan cepat . Outputnya harus berupa probabilitas tepat yang ditulis sebagai pecahan dalam bentuk yang paling dikurangi. Itu seharusnya tidak pernah output 4/8
melainkan 1/2
.
Untuk beberapa bilangan bulat positif n
, pertimbangkan string acak seragam panjang 1s dan -1s n
dan menyebutnya A. Sekarang digabungkan A
dengan nilai pertama. Itu A[1] = A[n+1]
jika pengindeksan dari 1. A
sekarang memiliki panjang n+1
. Sekarang juga pertimbangkan string acak kedua panjang n
dengan n
nilai pertama -1, 0, atau 1 dengan probabilitas 1 / 4,1 / 2, masing-masing 1/4 dan menyebutnya B.
Sekarang perhatikan produk dalam A[1,...,n]
dan B
dan produk dalam A[2,...,n+1]
dan B
.
Sebagai contoh, pertimbangkan n=3
. Nilai yang mungkin untuk A
dan B
bisa A = [-1,1,1,-1]
dan B=[0,1,-1]
. Dalam hal ini dua produk dalam adalah 0
dan 2
.
Kode Anda harus menampilkan probabilitas bahwa kedua produk dalam adalah nol.
Menyalin tabel yang diproduksi oleh Martin Büttner kami memiliki hasil sampel berikut.
n P(n)
1 1/2
2 3/8
3 7/32
4 89/512
5 269/2048
6 903/8192
7 3035/32768
8 169801/2097152
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa dan perpustakaan yang tersedia secara bebas yang Anda suka. Saya harus dapat menjalankan kode Anda jadi tolong sertakan penjelasan lengkap tentang cara menjalankan / kompilasi kode Anda di linux jika memungkinkan.
Tugas
Kode Anda harus mulai dengan n=1
dan memberikan output yang benar untuk setiap peningkatan n pada baris terpisah. Seharusnya berhenti setelah 10 detik.
Nilai
Skor ini hanyalah yang tertinggi yang n
dicapai sebelum kode Anda berhenti setelah 10 detik saat dijalankan di komputer saya. Jika ada seri, pemenanglah yang mendapatkan skor tertinggi tercepat.
Daftar entri
n = 64
dalam Python . Versi 1 oleh Mitch Schwartzn = 106
dalam Python . Versi 11 Juni 2015 oleh Mitch Schwartzn = 151
dalam C ++ . Jawaban Port of Mitch Schwartz oleh kirbyfan64sosn = 165
dalam Python . Versi 11 Juni 2015 versi "pemangkasan" oleh Mitch Schwartz denganN_MAX = 165
.n = 945
dalam Python oleh Min_25 menggunakan rumus yang tepat. Luar biasa!n = 1228
dalam Python oleh Mitch Schwartz menggunakan rumus lain yang tepat (berdasarkan jawaban Min_25 sebelumnya).n = 2761
dalam Python oleh Mitch Schwartz menggunakan implementasi yang lebih cepat dari formula yang persis sama.n = 3250
di Python menggunakan Pypy oleh Mitch Schwartz menggunakan implementasi yang sama. Skor ini perlupypy MitchSchwartz-faster.py |tail
menghindari overhead konsol bergulir.
sumber
Jawaban:
Python
Formula bentuk tertutup
p(n)
adalahFungsi menghasilkan eksponensial
p(n)
adalahdi mana
I_0(x)
fungsi Bessel yang dimodifikasi dari jenis pertama.Edit pada 2015-06-11:
- memperbarui kode Python.
Edit pada 2015-06-13:
- menambahkan bukti rumus di atas.
- memperbaiki
time_limit
.- menambahkan kode PARI / GP.
Python
PARI / GP
Bukti:
Masalah ini mirip dengan masalah jalan acak 2 dimensi (terbatas).
Jika
A[i] = A[i+1]
, kita dapat beralih dari(x, y)
ke(x+1, y+1)
[1 arah],(x, y)
[2 arah] atau(x-1, y-1)
[1 arah].Jika
A[i] != A[i+1]
, kita dapat beralih dari(x, y)
ke(x-1, y+1)
[1 arah],(x, y)
[2 arah] atau(x+1, y-1)
[1 arah].Mari
a(n, m) = [x^m]((x+1)^n + (x-1)^n)
,b(n) = [x^n](1+x)^{2n}
danc(n)
menjadi sejumlah cara untuk bergerak dari(0, 0)
ke(0, 0)
dengann
langkah-langkah.Kemudian,
c(n) = \sum_{i=0}^n a(n, i) * b(i) * b(n-i).
Karena
p(n) = c(n) / 8^n
, kita bisa mendapatkan formula bentuk tertutup di atas.sumber
Python
Catatan: Selamat kepada Min_25 karena menemukan solusi bentuk tertutup!
Terima kasih atas masalah yang menarik! Ini dapat diselesaikan dengan menggunakan DP, meskipun saat ini saya tidak merasa sangat termotivasi untuk mengoptimalkan kecepatan untuk mendapatkan skor yang lebih tinggi. Itu bisa bagus untuk golf.
Kode dicapai
N=39
dalam 10 detik pada laptop lama ini yang menjalankan Python 2.7.5.Untuk tuple
(a,b,s,t)
:a
adalah elemen pertamaA
,b
adalah elemen terakhirB
,s
adalah produk dalamA[:-1]
danB
, dant
merupakan produk dalamA[1:-1]
danB[:-1]
, menggunakan notasi irisan Python. Kode saya tidak menyimpan arrayA
atau diB
mana pun, jadi saya menggunakan surat-surat itu untuk merujuk ke elemen berikutnya yang akan ditambahkan keA
danB
, masing-masing. Pilihan penamaan variabel ini membuat penjelasan sedikit canggung, tetapi memungkinkan untuk terlihat bagusA*b+a*B
di kode itu sendiri. Perhatikan bahwa elemen yang ditambahkanA
adalah elemen kedua dari belakang, karena elemen terakhir selalu sama dengan yang pertama. Saya telah menggunakan trik Martin Büttner untuk memasukkan0
dua kaliB
kandidat untuk mendapatkan distribusi probabilitas yang tepat. KamusX
(yang diberi namaY
untukN+1
) melacak jumlah semua kemungkinan array sesuai dengan nilai tuple. Variabeln
dand
singkatan dari pembilang dan penyebut, itulah sebabnya saya menamai ulangn
pernyataan masalah sebagaiN
.Bagian utama dari logika adalah bahwa Anda dapat memperbarui dari
N
keN+1
hanya menggunakan nilai-nilai dalam tupel. Dua produk dalam yang ditentukan dalam pertanyaan diberikan olehs+A*B
dant+A*b+a*B
. Ini jelas jika Anda memeriksa definisi sedikit; perhatikan bahwa[A,a]
dan[b,B]
adalah dua elemen terakhir dari arrayA
danB
masing - masing.Perhatikan bahwa
s
dant
kecil dan dibatasi menurutN
, dan untuk implementasi cepat dalam bahasa cepat kita dapat menghindari kamus yang mendukung array.Dimungkinkan untuk mengambil keuntungan dari simetri mengingat nilai yang berbeda hanya dalam tanda; Saya belum melihat itu.
Catatan 1 : Ukuran kamus tumbuh dalam kuadratik
N
, di mana ukuran berarti jumlah pasangan nilai kunci.Catatan 2 : Jika kita menetapkan batas atas
N
, maka kita dapat memangkas tuple untuk yangN_MAX - N <= |s|
dan juga untukt
. Ini dapat dilakukan dengan menentukan kondisi penyerap, atau secara implisit dengan variabel untuk menahan jumlah kondisi prun (yang perlu dikalikan dengan 8 pada setiap iterasi).Pembaruan : Versi ini lebih cepat:
Optimasi diterapkan:
main()
- akses variabel lokal lebih cepat daripada globalN=1
secara eksplisit untuk menghindari tanda centang(1,-1) if N else [a]
(yang menegaskan bahwa elemen pertama dalam tuple konsisten, ketika menambahkan elemen keA
mulai dari daftar kosong)c
untuk menambahkan0
keB
alih-alih melakukan operasi itu dua kali8^N
jadi kita tidak perlu melacaknyaA
as1
dan membagi penyebut dengan2
, karena pasangan yang valid(A,B)
denganA[1]=1
dan mereka denganA[1]=-1
dapat dimasukkan ke dalam korespondensi satu-ke-satu dengan meniadakanA
. Demikian pula, kita dapat memperbaiki elemen pertamaB
sebagai non-negatif.N_MAX
untuk melihat skor apa yang bisa didapat di mesin Anda. Bisa ditulis ulang untuk menemukan yang sesuaiN_MAX
secara otomatis dengan pencarian biner, tetapi sepertinya tidak perlu? Catatan: Kita tidak perlu memeriksa kondisi pemangkasan sampai mencapai sekitarN_MAX / 2
, jadi kita bisa mendapatkan sedikit percepatan dengan mengulangi dalam dua fase, tapi saya memutuskan untuk tidak kesederhanaan dan kebersihan kode.sumber
N=57
dapat versi pertama danN=75
kedua.Python
Dengan menggunakan gagasan Min_25 tentang jalan acak, saya dapat sampai pada rumus berbeda:
Berikut ini adalah implementasi Python berdasarkan Min_25:
Penjelasan / bukti:
Pertama kita memecahkan masalah penghitungan terkait, di mana kita mengizinkan
A[n+1] = -A[1]
; yaitu, elemen tambahan yang disatukanA
dapat berupa1
atau-1
terlepas dari elemen pertama. Jadi kita tidak perlu melacak berapa kaliA[i] = A[i+1]
terjadi. Kami memiliki jalan acak berikut:Dari
(x,y)
kita dapat pindah ke(x+1,y+1)
[1 arah],(x+1,y-1)
[1 arah],(x-1,y+1)
[1 arah],(x-1,y-1)
[1 arah],(x,y)
[4 cara]di mana
x
dany
berdiri untuk produk dua titik, dan kami menghitung jumlah cara untuk beralih dari(0,0)
ke(0,0)
dalamn
langkah-langkah. Hitungan itu kemudian akan dikalikan dengan2
memperhitungkan fakta yangA
dapat dimulai dengan1
atau-1
.Kami menyebut tinggal di
(x,y)
sebagai langkah nol .Kami beralih pada jumlah gerakan non-nol
i
, yang harus genap untuk kembali(0,0)
. Gerakan horisontal dan vertikal membentuk dua jalan acak satu dimensi yang independen, yang dapat dihitung denganC(i,i/2)^2
, di manaC(n,k)
koefisien binomial. (Untuk jalan dengank
langkah ke kiri dank
langkah ke kanan, adaC(2k,k)
cara untuk memilih urutan langkah.) Selain itu adaC(n,i)
cara untuk menempatkan gerakan, dan4^(n-i)
cara untuk memilih gerakan nol. Jadi kita dapatkan:Sekarang, kita perlu kembali ke masalah semula. Tetapkan pasangan yang diizinkan
(A,B)
untuk dapat dikonversi jikaB
mengandung nol. Tentukan pasangan(A,B)
menjadi hampir diijinkan jikaA[n+1] = -A[1]
dan dua produk dot keduanya nol.Lemma: Untuk yang diberikan
n
, pasangan yang hampir diijinkan berada dalam korespondensi satu-ke-satu dengan pasangan yang dapat dikonversi.Kami dapat (secara reversibel) mengubah pasangan yang dapat dikonversi
(A,B)
menjadi pasangan yang hampir diijinkan(A',B')
dengan meniadakanA[m+1:]
danB[m+1:]
, di manam
indeks dari nol terakhir diB
. Pemeriksaan untuk ini mudah: Jika elemen terakhirB
adalah nol, kita tidak perlu melakukan apa pun. Kalau tidak, ketika kita meniadakan elemen terakhirA
, kita bisa meniadakan elemen terakhirB
untuk mempertahankan suku terakhir dari produk titik bergeser. Tapi ini meniadakan nilai terakhir dari produk titik yang tidak bergeser, jadi kami memperbaikinya dengan meniadakan elemen kedua hingga terakhirA
. Tapi kemudian ini membuang nilai kedua-ke-terakhir dari produk yang dipindahkan, jadi kami meniadakan elemen kedua-ke-terakhir dariB
. Demikian seterusnya, hingga mencapai nol elemen dalamB
.Sekarang, kita hanya perlu menunjukkan bahwa tidak ada pasangan yang hampir diijinkan yang
B
tidak mengandung nol. Agar produk titik sama dengan nol, kita harus memiliki jumlah1
dan-1
syarat yang sama untuk dibatalkan. Setiap-1
istilah terdiri dari(1,-1)
atau(-1,1)
. Jadi paritas jumlah-1
yang terjadi tetap sesuai dengann
. Jika elemen pertama dan terakhirA
memiliki tanda yang berbeda, kami mengubah paritas, jadi ini tidak mungkin.Jadi kita dapatkan
yang memberikan rumus di atas (pengindeksan ulang dengan
i' = i/2
).Pembaruan: Ini adalah versi yang lebih cepat menggunakan rumus yang sama:
Optimasi diterapkan:
p(n)
C(n,k)
dengank <= n/2
sumber
p(n)
tidak perlu menjadi fungsi piecewise. Secara umum, jikaf(n) == {g(n) : n is odd; h(n) : n is even}
maka Anda dapat menulisf(n) == (n-2*floor(n/2))*g(n) + ((n+1)-2*(floor((n+1)/2)))*h(n)
atau menggunakann mod 2
bukan(n-2*floor(n/2))
. Lihat di siniPenjelasan rumus Min_25
Min_25 memposting bukti yang bagus tetapi butuh beberapa saat untuk mengikuti. Ini adalah sedikit penjelasan yang harus diisi.
a (n, m) mewakili sejumlah cara untuk memilih A sedemikian rupa sehingga A [i] = A [i + 1] m kali. Rumus untuk (n, m) setara dengan a (n, m) = {2 * (n pilih m) untuk nm genap; 0 untuk nm aneh.} Hanya satu paritas yang diizinkan karena A [i]! = A [i + 1] harus terjadi beberapa kali genap sehingga A [0] = A [n]. Faktor 2 adalah karena pilihan awal A [0] = 1 atau A [0] = -1.
Setelah jumlah (A [i]! = A [i + 1]) ditetapkan menjadi q (dinamai i dalam rumus c (n)), ia berpisah menjadi dua jalan acak 1D panjang q dan nq. b (m) adalah sejumlah cara untuk mengambil langkah acak satu dimensi dari langkah-langkah m yang berakhir di tempat yang sama dengan yang dimulainya, dan memiliki peluang 25% untuk bergerak ke kiri, 50% peluang untuk tetap diam, dan peluang 25% untuk bergerak ke kanan. Cara yang lebih jelas untuk menyatakan fungsi pembangkit adalah [x ^ m] (1 + 2x + x ^ 2) ^ n, di mana 1, 2x dan x ^ 2 masing-masing mewakili kiri, tidak bergerak, dan kanan. Tapi kemudian 1 + 2x + x ^ 2 = (x + 1) ^ 2.
sumber
C ++
Hanya port jawaban Python (luar biasa) oleh Mitch Schwartz. Perbedaan utama adalah bahwa saya dulu
2
mewakili-1
untuka
variabel dan melakukan sesuatu yang serupab
, yang memungkinkan saya untuk menggunakan array. Dengan menggunakan Intel C ++-O3
, saya dapatN=141
! Versi pertamaku didapatN=140
.Ini menggunakan Boost. Saya mencoba versi paralel tetapi mengalami beberapa masalah.
sumber
g++ -O3 kirbyfan64sos.cpp -o kirbyfan64sos -lboost_system -lboost_timer -lboost_chrono -lrt -lgmp
dikompilasi. (Terima kasih kepada aditsu.)