Sebuah String biner adalah string yang hanya berisi karakter yang diambil dari 01 . Sebuah String biner seimbang adalah string biner yang berisi persis sebanyak 0 sebagai 1 s.
Anda diberi bilangan bulat positif n dan sejumlah topeng yang berubah-ubah, masing-masing panjangnya 2n karakter, dan hanya berisi karakter yang diambil dari 012 . String biner dan topeng cocok jika panjangnya sama dan menyetujui karakter di setiap posisi di mana topeng tidak memiliki 2 . Misalnya topeng 011022 cocok dengan string biner 011000 , 011001 , 011010 , 011011 .
Diberikan n dan topeng sebagai input (dipisahkan oleh baris baru), Anda harus menampilkan jumlah string biner seimbang berbeda yang cocok dengan satu atau lebih dari topeng.
Contohnya
Memasukkan
3
111222
000112
122020
122210
102120
Pemikiran
- Satu-satunya string biner seimbang yang cocok dengan 111222 adalah 111000 .
- Satu-satunya string biner seimbang yang cocok dengan 000112 adalah 000111 .
- String biner seimbang yang cocok dengan 122020 adalah 111000 (sudah dihitung), 110010 dan 101010 .
- String biner seimbang yang cocok dengan 122210 adalah 110010 (sudah dihitung), 101010 (sudah dihitung) dan 100110 .
- String biner seimbang cocok 102.120 adalah 101.100 dan 100.110 (sudah dihitung).
Jadi hasilnya seharusnya
6
Memasukkan
10
22222222222222222222
Pemikiran
- Ada 20 pilih 10 string biner seimbang dengan panjang 20.
Keluaran
184756
Pemenang
Pemenang akan menjadi orang yang menghitung input kompetisi tercepat, tentu memperlakukannya dengan cara yang sama seperti input lainnya. (Saya menggunakan kode yang ditentukan untuk memiliki pemenang yang jelas dan menghindari kasus di mana input yang berbeda akan memberikan pemenang yang berbeda. Jika Anda memikirkan cara yang lebih baik untuk menemukan kode tercepat, katakan demikian).
Masukan kompetisi
sumber
Jawaban:
C
Jika Anda tidak menggunakan Linux, atau mengalami kesulitan dalam kompilasi, Anda mungkin harus menghapus kode timing (
clock_gettime
).Contoh kasus:
(Kali ini untuk CPU i7-4770K pada 4,1 GHz.) Hati-hati,
testcase-hard
gunakan memori sekitar 3-4 GB.Ini hampir merupakan implementasi dari metode inklusi-eksklusi blutorange, tetapi dilakukan sehingga akan menangani persimpangan dengan kedalaman apa pun.
Kode seperti yang tertulis menghabiskan banyak waktu pada alokasi memori, dan akan menjadi lebih cepat setelah saya mengoptimalkan manajemen memori.Saya mencukur sekitar 25%
testcase-hard
, tetapi kinerja pada yang asli (testcase-long
) cukup banyak tidak berubah, karena tidak banyak alokasi memori yang terjadi di sana. Saya akan menyetel sedikit lagi sebelum saya menyebutnya: Saya pikir saya mungkin bisa mendapatkan peningkatan 25% -50%testcase-long
juga.Mathematica
Setelah saya perhatikan ini adalah masalah #SAT, saya menyadari saya bisa menggunakan built-in Mathematica
SatisfiabilityCount
:Keluaran:
Itu 298.208.861.472 topeng dalam 1,3 detik (i7-3517U @ 1.9 GHz), termasuk waktu yang dihabiskan untuk mengunduh test case dari pastebin.
sumber
testcase-hard
dapat diselesaikan dengan sangat cepat jika kode Anda mencari topeng yang dapat digabungkan. Jika kode Anda melakukan ini, maka hapuslah setiap baris lainnya (jadi/^2*02*$/
tinggal kasing saja). Saya tidak berpikir case bisa dioptimalkan.ruby, cukup cepat, tetapi itu tergantung pada input
Sekarang percepat dengan faktor 2 ~ 2.5 dengan beralih dari string ke integer.
Pemakaian:
Misalnya.
Jumlah kecocokan untuk masker tunggal mudah dihitung dengan koefisien binomial. Jadi misalnya
122020
kebutuhan 32
s diisi, 10
dan 21
. Jadi adanCr(3,2)=nCr(3,1)=3!/(2!*1!)=3
beberapa string biner yang cocok dengan topeng ini.Persimpangan antara n mask m_1, m_2, ... m_n adalah mask q, sehingga string biner s cocok dengan q hanya jika jika cocok dengan semua mask m_i.
Jika kita mengambil dua topeng m_1 dan m_2, persimpangannya mudah dihitung. Cukup atur m_1 [i] = m_2 [i] jika m_1 [i] == 2. Persimpangan antara
122020
dan111222
adalah111020
:Dua topeng individu dicocokkan oleh 3 + 1 = 4 string, topeng intereseksi dicocokkan oleh satu string, sehingga ada 3 + 1-1 = 3 string unik yang cocok dengan satu atau kedua topeng.
Saya akan menelepon N (m_1, m_2, ...) jumlah string yang cocok dengan semua m_i. Dengan menerapkan logika yang sama seperti di atas, kita dapat menghitung jumlah string unik yang cocok dengan setidaknya satu topeng, yang diberikan oleh prinsip pengecualian inklusi dan lihat di bawah juga, seperti ini:
Ada banyak, banyak, banyak kombinasi pengambilan, misalnya 30 topeng dari 200.
Jadi solusi ini membuat asumsi bahwa tidak banyak persimpangan tingkat tinggi dari masker input, yaitu. kebanyakan n-tupel dari n> 2 topeng tidak akan memiliki kecocokan umum.
Gunakan kode di sini, kode di ideone mungkin kedaluwarsa.
Saya menambahkan fungsi
remove_duplicates
yang dapat digunakan untuk pra-proses input dan menghapus topengm_i
sehingga semua string yang cocok juga cocok dengan topeng lainm_j
., Untuk input saat ini, ini sebenarnya membutuhkan waktu lebih lama karena tidak ada topeng seperti itu (atau tidak banyak) , jadi fungsinya belum diterapkan ke data dalam kode di bawah ini.Kode:
Ini disebut prinsip pengecualian inklusi, tetapi sebelum seseorang menunjuk saya ke sana, saya punya bukti sendiri, jadi begini saja. Melakukan sesuatu sendiri terasa hebat.
Mari kita perhatikan kasus 2 topeng, panggil dulu
0
dan1
, pertama. Kami mengambil setiap string biner seimbang dan mengklasifikasikannya sesuai dengan topeng yang cocok.c0
adalah jumlah orang-orang yang cocok hanya topeng0
,c1
nunber dari orang-orang yang cocok hanya1
,c01
orang-orang yang cocok masker0
dan1
.Membiarkan
s0
menjadi jumlah jumlah dari jumlah kecocokan untuk setiap topeng (mereka mungkin tumpang tindih). Membiarkans1
menjadi jumlah dari jumlah kecocokan untuk setiap pasangan (2-kombinasi) dari topeng. Biarkans_i
menjadi jumlah dari jumlah kecocokan untuk setiap (i +1) kombinasi topeng. Jumlah kecocokan n-mask adalah jumlah string biner yang cocok dengan semua mask.Jika ada n mask, output yang diinginkan adalah jumlah dari semua
c
, yaitu.c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1)
. Apa yang dihitung program adalah jumlah bolak - balik dari semuas
, yaitu.s = s_0-s_1+s_2-+...+-s_(n-1)
. Kami ingin membuktikannyas==c
.n = 1 jelas. Pertimbangkan n = 2. Menghitung semua pertandingan topeng
0
memberikanc0+c01
(jumlah string yang cocok hanya 0 + mereka cocok baik0
dan1
), menghitung semua pertandingan1
memberikanc1+c02
. Kita dapat menggambarkan ini sebagai berikut:Menurut definisi
s0 = c0 + c1 + c12
,.s1
adalah jumlah jumlah kecocokan dari setiap 2 kombinasi[0,1]
, yaitu. semua uniqyec_ij
s. Ingat ituc01=c10
.Jadi
s=c
untuk n = 2.Sekarang pertimbangkan n = 3.
Jadi
s=c
untuk n = 3.c__i
mewakili semua daric
s dengan indeks (i +1), misalnyac__1 = c01
untuk n = 2 danc__1 = c01 + c02 + c12
untuk n == 3.Untuk n = 4, sebuah pola mulai muncul:
Jadi
s==c
untuk n = 4.Secara umum, kita mendapatkan koefisien binomial seperti ini (↓ is i, → is j):
Untuk melihat ini, pertimbangkan itu untuk beberapa
i
danj
, ada:Karena itu mungkin terdengar membingungkan, inilah definisi yang diterapkan pada contoh. Untuk i = 1, j = 2, n = 4, terlihat seperti ini (lih. Di atas):
Jadi di sini x = 6 (01, 02, 03, 12, 13, 23), y = 2 (dua c dengan tiga indeks untuk setiap kombinasi), z = 4 (c012, c013, c023, c023, c123).
Secara total, ada
x*y
koefisienc
dengan indeks (j + 1), dan ada yangz
berbeda, sehingga masing-masing terjadix*y/z
kali, yang kita sebut koefisienk_ij
. Dengan aljabar sederhana, kita dapatkank_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1)
.Jadi indeks diberikan oleh
k_ij = nCr(j+1,i+1)
Jika Anda mengingat semua definisi, yang perlu kita tunjukkan adalah bahwa jumlah bolak-balik dari setiap kolom menghasilkan 1.Dengan
s0 - s1 + s2 - s3 +- ... +- s(n-1)
demikian jumlah alternatif dapat dinyatakan sebagai:Jadi
s=c
untuk semua n = 1,2,3, ...sumber
0011 < 2211
,0022 < 0222
. Saya pikir ini membuat kelompok tidak lebih besar dari2*n
, meskipun masih terlalu besar dalam kasus terburuk.unifying two masks
istilah iniunion
masuk akal bagi saya dan saya dapat mendefinisikan seperti itu, tetapi Anda benar, demi kepentingan saling pengertian yang saya raih. @ Agawa001 Bisakah Anda lebih spesifik? Juga, jika Anda punya ide bagus untuk membuatnya lebih cepat, silakan gunakan ide apa pun dari jawaban ini untuk program / jawaban Anda. Untuk saat ini, ini cukup cepat untuk test case yang besar, dan jika dibuat multi-threaded harus mengambil <0,1s, yang di bawah pengukuran / perbandingan yang berarti, sehingga untuk test case yang lebih keras diperlukan.C
Semoga berhasil mendapatkan input besar untuk dijalankan - ini mungkin akan memakan waktu sepanjang malam untuk mendapatkan sekitar. 60 ^ 30 permutasi! Mungkin dataset berukuran menengah mungkin merupakan ide yang bagus?
sumber