Untuk bilangan bulat positif yang diberikan n
, pertimbangkan semua panjang string biner 2n-1
. Untuk string tertentu S
, biarkan L
menjadi array panjang n
yang berisi hitungan jumlah 1
s di setiap substring panjang n
dari S
. Misalnya, jika n=3
dan S = 01010
kemudian L=[1,2,1]
. Kami menyebutnya L
array penghitungan S
.
Kami mengatakan bahwa dua string S1
dan S2
panjang yang sama cocok jika masing-masing array array L1
dan L2
memiliki properti itu L1[i] <= 2*L2[i]
dan L2[i] <= 2*L1[i]
untuk semua i
.
Tugas
Untuk meningkatkan n
mulai dari n=1
, tugasnya adalah untuk menemukan ukuran set string terbesar, masing-masing panjang 2n-1
sehingga tidak ada dua string yang cocok.
Kode Anda harus menampilkan satu nomor per nilai n
.
Skor
Skor Anda adalah yang tertinggi di n
mana tidak ada orang lain yang memposting jawaban yang benar lebih tinggi untuk semua jawaban Anda. Jelas jika Anda memiliki semua jawaban optimal maka Anda akan mendapatkan skor untuk tertinggi yang n
Anda posting. Namun, bahkan jika jawaban Anda tidak optimal, Anda masih bisa mendapatkan skor jika tidak ada orang lain yang bisa mengalahkannya.
Contoh jawaban
Karena n=1,2,3,4
aku mengerti 2,4,10,16
.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa dan perpustakaan yang tersedia yang Anda suka. Jika memungkinkan, alangkah baiknya untuk dapat menjalankan kode Anda jadi harap sertakan penjelasan lengkap tentang cara menjalankan / kompilasi kode Anda di linux jika memungkinkan.
Entri terkemuka
- 5 oleh Martin Büttner di Mathematica
- 6 oleh Reto Koradi di C ++ . Nilai adalah
2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086
. 5 pertama diketahui optimal. - 7 oleh Peter Taylor di Jawa . Nilai adalah
2, 4, 10, 16, 31, 47, 76, 111, 166, 235
. - 9 oleh joriki di Jawa . Nilai adalah
2, 4, 10, 16, 31, 47, 76, 112, 168
.
L1[i]/2 <= L2[i] <= 2*L1[i]
.match(A, B)
danmatch(B, C)
tidak menyiratkanmatch(A, C)
(sama untuk kebalikannya). Contoh: [1] dan [2] cocok, [2] dan [3] cocok, tetapi [1] dan [3] tidak. Demikian pula, [1,3] dan [3,1] tidak cocok, [3, 1] dan [2, 3] tidak cocok, tetapi [1, 3] dan [2, 3] cocok.Jawaban:
2, 4, 10, 16, 31, 47, 76, 112, 168
Untuk setiap n, kode Java ini menentukan array penghitungan yang mungkin dan kemudian menemukan set peningkatan ukuran yang tidak cocok, untuk setiap ukuran dimulai dengan set acak dan memperbaikinya dengan penurunan curam secara acak. Di setiap langkah, salah satu elemen dari himpunan dipilih secara acak seragam dan diganti dengan array penghitungan yang dipilih secara acak di antara yang tidak digunakan. Langkah ini diterima jika tidak menambah jumlah kecocokan. Resep yang terakhir ini tampaknya sangat penting; menerima langkah hanya jika mereka mengurangi jumlah kecocokan hampir tidak efektif. Langkah-langkah meninggalkan jumlah pertandingan yang invarian memungkinkan ruang pencarian untuk dieksplorasi, dan akhirnya beberapa ruang mungkin terbuka untuk menghindari salah satu pertandingan. Setelah 2 ^ 24 langkah tanpa peningkatan, ukuran sebelumnya adalah output untuk nilai sekarang dari n, dan n bertambah.
Hasil hingga n = 9 adalah
2, 4, 10, 16, 31, 47, 76, 112, 168
, meningkatkan hasil sebelumnya untuk n = 8 per satu dan untuk n = 9 oleh dua. Untuk nilai n yang lebih tinggi, batas 2 ^ 24 langkah mungkin harus ditingkatkan.Saya juga mencoba annealing yang disimulasikan (dengan jumlah kecocokan sebagai energi), tetapi tanpa peningkatan pada penurunan yang curam.
Kode
save as
Question54354.java
compile with
javac Question54354.java
run with
java Question54354
sumber
2, 4, 10, 16, 31, 47, 76, 111, 166, 235
Catatan
Jika kita mempertimbangkan grafik
G
dengan simpul0
ken
dan ujung-ujungnya bergabung dengan dua angka yang cocok, maka daya tensorG^n
memiliki simpul yang(x_0, ..., x_{n-1})
membentuk daya Cartesian{0, ..., n}^n
dan tepi antara tupel yang cocok. Grafik yang menarik adalah subgraf yangG^n
diinduksi oleh simpul-simpul yang sesuai dengan "array penghitungan" yang memungkinkan.Jadi subtugas pertama adalah untuk menghasilkan simpul tersebut. Pendekatan naif menyebutkan lebih dari
2^{2n-1}
string, atau pada urutan4^n
. Tetapi jika kita melihat array perbedaan pertama dari array penghitungan kita menemukan bahwa hanya ada3^n
kemungkinan, dan dari perbedaan pertama kita dapat menyimpulkan kisaran nilai awal yang mungkin dengan mensyaratkan bahwa tidak ada elemen dalam perbedaan nol yang kurang dari0
atau lebih besar darin
.Kami kemudian ingin menemukan set independen maksimum. Saya menggunakan satu teorema dan dua heuristik:
(n, n, ..., n)
akan berada dalam set independen maksimum. Ada sekelompok besar simpul di{m, m+1, ..., n}^n
manam
bilangan bulat terkecil yang cocokn
;(n, n, ..., n)
dijamin tidak memiliki kecocokan di luar klik itu.Di komputer saya temuan ini
111
untukn=8
di 16 detik,166
untukn=9
sekitar 8 menit, dan235
untukn=10
sekitar 2 jam.Kode
Simpan sebagai
PPCG54354.java
, kompilasi sebagaijavac PPCG54354.java
, dan jalankan sebagaijava PPCG54354
.sumber
Mathematica
n = 5
,, 31 stringSaya baru saja menulis solusi brute force menggunakan built-in Mathematica untuk memverifikasi jawaban contoh Lembik, tetapi dapat menangani
n = 5
juga:Sebagai bonus, kode ini menghasilkan visualisasi masalah sebagai grafik di mana setiap sisi menunjukkan dua string yang cocok.
Ini adalah grafik untuk
n = 3
:sumber
C ++ (heuristik): 2, 4, 10, 16, 31, 47, 75, 111, 164, 232, 328, 445, 606, 814, 1086
Ini sedikit di belakang hasil Peter Taylor, menjadi 1 sampai 3 lebih rendah untuk
n=7
,9
dan10
. Keuntungannya adalah lebih cepat, jadi saya bisa menjalankannya untuk nilai yang lebih tinggin
. Dan itu bisa dipahami tanpa matematika mewah. ;)Kode saat ini dibuat untuk menjalankan hingga
n=15
. Jalankan kali meningkat kira-kira dengan faktor 4 untuk setiap peningkatann
. Misalnya, 0,008 detik untukn=7
, 0,07 detik untukn=9
, 1,34 detik untukn=11
, 27 detik untukn=13
, dan 9 menit untukn=15
.Ada dua pengamatan utama yang saya gunakan:
c
tidak termasuk rentangc / 2
hingga2 * c
dari nilai lain. Untuk nilai yang lebih kecilc
, rentang ini lebih kecil, yang berarti bahwa nilai yang lebih sedikit dikecualikan dengan menggunakannya.Hasilkan Array Penghitungan Unik
Saya menggunakan brute force yang satu ini, mengulangi semua nilai, menghasilkan array jumlah untuk masing-masing, dan menyatukan daftar yang dihasilkan. Ini tentu saja dapat dilakukan dengan lebih efisien, tetapi cukup baik untuk jenis nilai yang kami operasikan.
Ini sangat cepat untuk nilai-nilai kecil. Untuk nilai yang lebih besar, biaya overhead menjadi substansial. Misalnya, untuk
n=15
, ia menggunakan sekitar 75% dari keseluruhan runtime. Ini pasti akan menjadi area untuk dilihat ketika mencoba untuk pergi jauh lebih tinggi daripadan=15
. Bahkan penggunaan memori untuk membangun daftar array penghitungan untuk semua nilai akan mulai menjadi masalah.Jumlah array penghitungan unik adalah sekitar 6% dari jumlah nilai untuk
n=15
. Jumlah relatif ini menjadi lebih kecil karenan
menjadi lebih besar.Pilihan Serakah Menghitung Nilai Array
Bagian utama dari algoritma memilih penghitungan nilai array dari daftar yang dihasilkan menggunakan pendekatan serakah sederhana.
Berdasarkan teori bahwa menggunakan array penghitungan dengan jumlah kecil bermanfaat, array penghitungan diurutkan berdasarkan jumlah penghitungannya.
Mereka kemudian diperiksa secara berurutan, dan nilai dipilih jika itu kompatibel dengan semua nilai yang digunakan sebelumnya. Jadi ini melibatkan satu lintasan linear tunggal melalui array penghitungan yang unik, di mana setiap kandidat dibandingkan dengan nilai-nilai yang sebelumnya dipilih.
Saya punya beberapa ide tentang bagaimana heuristik berpotensi ditingkatkan. Tapi ini sepertinya titik awal yang masuk akal, dan hasilnya terlihat cukup bagus.
Kode
Ini tidak sangat dioptimalkan. Saya memiliki struktur data yang lebih rumit di beberapa titik, tetapi akan membutuhkan lebih banyak pekerjaan untuk menggeneralisasikannya di luar
n=8
, dan perbedaan kinerja tampaknya tidak terlalu besar.sumber
n=4
sudah cukup lama. Mungkin selesain=5
dengan kesabaran. Anda harus menggunakan strategi backtracking yang lebih baik bahkan untuk membuatnyan=7
. Apakah Anda heuristik, atau apakah itu menjelajahi seluruh ruang solusi? Saya merenungkan beberapa ide tentang bagaimana membuat ini lebih baik, baik dengan menyesuaikan urutan penyortiran, atau dengan mungkin tidak murni rakus.3^n
dan dua heuristik yang dia gambarkan.n=7
cepat. Tapi mencobanyan=9
, masih macet di 164 ketika saya menghentikannya setelah 20 menit. Jadi memperpanjang ini dengan bentuk backtracking sederhana tidak terlihat menjanjikan secara umum.