Bot Mabuk yang Dekat dengan Penglihatan di Ladang Ranjau

11

Seperti judulnya mungkin sarankan, masalah ini semi-terinspirasi oleh Bot Mabuk Dekat Penglihatan oleh @NP

Bot kami yang buruk ditempatkan pada kisi cartesian di tempat asalnya, dan setelah setiap menit, bot bergerak 1 unit di salah satu dari empat arah (Atas, Bawah, Kiri, Kanan).

Setelah n menit, semua ranjau laten di grid diaktifkan, menewaskan bot miskin yang mungkin menemukan diri mereka sendiri di atasnya. Tambang terletak di semua koordinat bilangan bulat yang memenuhi persamaan | y | = | x |.

Tantangan

Anda akan diberikan n , jumlah menit sebelum ledakan tambang, sebagai input, dan sebagai output, Anda harus menemukan probabilitas bahwa bot sudah mati .

Input : Angka alami yang mewakili n .

Output : Biarkan probabilitas bot mati menjadi p / q, di mana p dan q adalah bilangan bulat yang relatif prima (q tidak bisa 0, tetapi p bisa). Output h.

Aturan

  • Algoritme Anda tidak boleh berjalan dalam waktu eksponensial atau lebih tinggi. Idealnya harus dijalankan dalam waktu polinomial atau kurang.
  • Algoritme Anda harus dapat menangani input n<20 (dapat disesuaikan jika terlalu sulit) dalam waktu yang wajar.
  • Ini adalah tantangan .
  • Iterasi semua kemungkinan untuk suatu n dan pasti tidak akan diterima sebagai jawaban.

Uji Kasus

1->0

2->3

4->39

6->135

8->7735

10->28287

Contoh Perhitungan untuk n = 6

Kami memiliki 4 kemungkinan pergerakan: U, D, R, dan L. Jumlah total jalur yang dapat diambil adalah 4 ^ 6, atau 4096. Ada 4 kemungkinan kasus yang mendarat di sepanjang garis y = x: x, y = ± 1; x, y = ± 2; x, y = ± 3; atau x = y = 0. Kami akan menghitung jumlah cara untuk berakhir pada (1,1), (2,2), dan (3,3), kalikan dengan 4 untuk memperhitungkan kuadran lain, dan tambahkan ini ke sejumlah cara untuk berakhir pada (0,0).

Kasus 1: Bot berakhir pada (3, 3). Agar bot berakhir di sini, ia harus memiliki 3 gerakan yang benar, dan 3 gerakan ke atas. Dengan kata lain, jumlah total cara untuk sampai ke sini adalah cara untuk mengatur ulang huruf dalam urutan RRRUUU, yaitu 6 pilih 3 = 20.

Kasus 2: Bot berakhir pada (2,2). Agar bot berakhir di sini, bisa saja ada 2 gerakan ke atas, 3 gerakan ke kanan, dan 1 gerakan ke kiri; atau 2 gerakan kanan, 3 gerakan ke atas, dan 1 gerakan ke bawah. Dengan demikian, jumlah total cara untuk sampai ke sini adalah jumlah cara untuk mengatur ulang huruf dalam urutan RRRLUU dan UUUDRR, yang keduanya (6 pilih 1) * (5 pilih 2) = 60, dengan total 120 kemungkinan .

Kasus 3: Bot berakhir pada (1,1). Agar bot berakhir di sini, bot bisa memiliki: 1 gerakan kanan, 3 gerakan ke atas, dan 2 gerakan ke bawah. Dalam hal ini, jumlah cara untuk mengatur ulang huruf dalam urutan RUUUDD adalah (6 pilih 1) * (5 pilih 2) = 60.

1 gerakan ke atas, 3 gerakan ke kanan, dan 2 gerakan ke kiri. Dalam hal ini, jumlah cara untuk mengatur ulang huruf-huruf dalam urutan URRRLL adalah (6 pilih 1) * (5 pilih 2) = 60.

2 gerakan kanan, 1 gerakan kiri, 2 gerakan ke atas, dan 1 gerakan ke bawah. Dalam hal ini, jumlah cara untuk mengatur ulang huruf dalam urutan UUDRRL adalah (6 pilih 1) * (5 pilih 1) * (4 pilih 2) = 180.

Dengan demikian, jumlah total cara untuk berakhir pada (1,1) adalah 300.

Kasus 4: Bot berakhir pada (0,0). Agar bot berakhir di sini, bot bisa memiliki:

3 gerakan kanan dan 3 gerakan kiri. Dalam hal ini, jumlah cara untuk mengatur ulang huruf dalam urutan RRRLLL adalah (6 pilih 3) = 20.

3 gerakan ke atas dan 3 gerakan ke bawah. Dalam hal ini, jumlah cara untuk mengatur ulang huruf-huruf dalam urutan UUUDDD adalah (6 pilih 3) = 20.

1 gerakan kanan, 1 gerakan kiri, 2 gerakan ke atas, dan 2 gerakan ke bawah. Dalam hal ini, jumlah cara untuk mengatur ulang huruf dalam urutan RLUUDD adalah (6 pilih 1) * (5 pilih 1) * (4 pilih 2) = 180.

1 gerakan naik, 1 gerakan turun, 2 gerakan kanan, dan 2 gerakan kiri. Dalam hal ini, jumlah cara untuk mengatur ulang huruf dalam urutan RRLLUD adalah (6 pilih 1) * (5 pilih 1) * (4 pilih 2) = 180.

Dengan demikian, jumlah total cara untuk berakhir pada (0,0) adalah 400.

Menambahkan kasus-kasus ini bersama-sama, kita mendapatkan jumlah total cara untuk berakhir di | y | = | x | adalah 4 (20 + 120 + 300) + 400 = 2160. Dengan demikian, probabilitas kami adalah 2160/4096. Ketika fraksi ini berkurang sepenuhnya, itu 135/256, jadi jawaban kami adalah 135 .

Don Thousand
sumber
Saya suka tantangannya tetapi saya pikir itu akan bermanfaat dengan memasukkan contoh yang berhasil untuk salah satu kasus uji yang sangat kecil (2 atau 3) misalnya.
Tn. Xcoder
@ Mr.Xcoder Saya akan menambahkan satu ketika saya punya waktu.
Don Thousand
2
Tantangan yang menarik. Perhatikan bahwa menggunakan kata "idealnya" dalam aturan membuatnya bukan aturan. Akan bermanfaat untuk mengatakan dengan cara tertentu.
trichoplax
1
Tetapi tidak ada yang berbicara tentang Algoritma Pembelajaran Generasi Pertama?
Program Redwolf
1
@RedwolfPrograms ahaha ya tapi bot ini memiliki nama yang lebih keren
Don Thousand

Jawaban:

17

Python 2 , 65 byte

def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)

Cobalah online!

Probabilitas bot sudah mati dapat dinyatakan sebagai:

f(n)=2ss2, where s=12n(nn/2)

dan binomial dipahami sama dengan ketika tidak utuh.0n/2

Kita bisa bernalar seperti ini. Berapa probabilitas bot mendarat di garis ? Ini terjadi jika jumlah total gerakan ke atas dan kiri sama dengan jumlah total gerakan ke bawah dan ke kanan. Ini adalah probabilitas yang sama bahwa, katakanlah, Anda melempar koin kali dan mendapatkan ekor sebanyak kepala. Anda harus memilih membalik untuk menjadi kepala dari membalik, yang dapat dilakukan dalam cara, dari sekuens yang mungkin secara keseluruhan, memberikan probabilitasy=xnn/2n(nn/2)2n

s=12n(nn/2)

Probabilitas pendaratan garis juga . Jadi, probabilitas pendaratan di kedua baris adalah jumlah dari ini atau , kecuali kita menghitung dua kali kemungkinan pendaratan di kedua baris, dan harus mengurangi itu untuk mengkompensasi.y=xs2sx=y=0

Ternyata probabilitas pendaratan di hanya , produk dari probabilitas pendaratan di setiap baris. Kita dapat berargumen bahwa peristiwa itu independen sebagai berikut: jika kita memilih urutan acak dengan jumlah yang sama "Atas atau Kiri" dan "Bawah atau Kanan" untuk mendarat di dan juga dengan "Atas atau Kanan" dan "Bawah atau Kiri" "untuk , kita dapat menggabungkan mereka secara unik ke dalam urutan Atas, Bawah, Kiri, Kanan dengan mengambil persimpangan pasangan arah pada setiap posisi.x=y=0s2x=yx=y

Jadi, probabilitas mendarat di atau adalah .x=yx=y2ss2

Kode menghitung binomial menggunakan ekspresi ini sebagai basis . Untuk mengekstrak pembilang dari fraksi probabilitas, kami mencatat bahwa penyebutnya adalah kekuatan 2, jadi kami menggunakan ekspresi untuk membagi kekuatan maksimal 2 , yang dinyatakan sebagai trik bit klasik .(nn/2)(b+1)**n/b**(n/2)%bb=2**nr/(r&-r)rr&-r

Solusinya adalah golf dengan menuliskan sebagai sehingga hanya dirujuk satu kali, dan bekerja tanpa fraksi untuk tetap berada dalam bilangan bulat. Perhitungannya adalah polinomial-waktu dalam bahkan dengan cara komputasi binomial yang funky.2ss21(1s)2s1/2nn


Setelah menulis bukti probabilitas bot mati, saya menemukan cara yang lebih bersih untuk membuktikannya dan menyajikannya.

Mari kita melacak nilai-nilai dan setelah setiap gerakan bot. Masing-masing dari empat arah naik, turun, kiri, dan kanan baik kenaikan atau penurunan masing-masing dan , dengan empat arah sesuai dengan empat kombinasi.a=x+yb=xyab

Jadi, perpindahan acak sama dengan menambahkan secara acak ke dan secara independen ke . Ini sama dengan melakukan jalan acak terpisah pada dan .±1a±1bab

Sekarang, robot berakhir pada garis atau tepat ketika atau . Jadi, probabilitas berakhir dengan adalah dan juga untuk . Karena jalan-jalannya independen, probabilitas dan adalah , jadi probabilitas bahwa setidaknya satu adalah nol adalah komplemen .x=yx=ya=0b=0a=0s=12n(nn/2)b=0a0b0(1s)21(1s)2

Tidak
sumber
3
Fantastis! Saya sedang menunggu seseorang untuk menurunkan ini. Saya tidak membayangkan itu begitu cepat. Kelemahannya sekarang adalah bahwa sebagian besar jawaban lain tidak perlu terlalu banyak berpikir :(. Unggul +1
Don Thousand
nikmati hadiah kecil (tidak perlu banyak memberi maaf)
Don Thousand
1
@RushabhMehta Terima kasih, Anda baik sekali! Karunia Anda memotivasi saya untuk menulis bukti yang lebih bersih yang saya pikirkan sesudahnya.
xnor
Inspirasi nyata untuk masalah ini adalah AIME I 2014 masalah 11, jika Anda ingin memeriksanya.
Don Thousand