Tantangan ini sebagian merupakan tantangan algoritma, sebagian tantangan optimasi dan sebagian hanya tantangan kode tercepat.
Matriks siklik sepenuhnya ditentukan oleh baris pertama r
. Baris yang tersisa adalah setiap permutasi siklik dari baris r
dengan offset sama dengan indeks baris. Kami akan mengizinkan matriks siklik yang tidak persegi sehingga mereka hanya kehilangan beberapa baris terakhir mereka. Namun kami selalu menganggap bahwa jumlah baris tidak lebih dari jumlah kolom. Sebagai contoh, perhatikan 3 dari 5 matriks siklik berikut.
10111
11011
11101
Kami mengatakan sebuah matriks memiliki properti X jika berisi dua set kolom yang tidak kosong dengan indeks tidak identik yang memiliki jumlah (vektor) yang sama. Jumlah vektor dari dua kolom hanyalah penjumlahan elemen-bijaksana dari dua kolom. Itu adalah jumlah dari dua kolom yang mengandung x
elemen masing-masing adalah kolom lain yang mengandung x
elemen.
Matriks di atas sepele memiliki properti X karena kolom pertama dan terakhir adalah sama. Matriks identitas tidak pernah memiliki properti X.
Jika kita hanya menghapus kolom terakhir dari matriks di atas maka kita mendapatkan contoh yang tidak memiliki properti X dan akan memberikan skor 4/3.
1011
1101
1110
Tugas
Tugasnya adalah menulis kode untuk menemukan matriks siklik dengan skor tertinggi yang semua entri 0 atau 1 dan yang tidak memiliki properti X.
Skor
Skor Anda akan menjadi kolom jumlah dibagi dengan jumlah baris dalam matriks skor terbaik Anda.
Tie Breaker
Jika dua jawaban memiliki skor yang sama, jawaban yang pertama menang.
Dalam hal (sangat) tidak mungkin bahwa seseorang menemukan metode untuk mendapatkan skor tanpa batas, bukti valid pertama dari solusi semacam itu akan diterima. Dalam acara yang bahkan lebih tidak mungkin bahwa Anda dapat menemukan bukti optimalitas dari matriks yang terbatas saya tentu saja akan memberikan penghargaan juga.
Petunjuk
Mendapatkan skor 12/8 tidak terlalu sulit.
Bahasa dan perpustakaan
Anda dapat menggunakan bahasa apa pun yang memiliki kompiler / juru bahasa / dll yang tersedia secara bebas. untuk Linux dan semua perpustakaan yang juga tersedia secara bebas untuk Linux.
Entri terkemuka
- 36/19 oleh Peter Taylor (Jawa)
- 32/17 oleh Suboptimus Prime (C #)
- 21/12 oleh justhalf (Python 2)
sumber
01
memiliki properti X karena himpunan kolom pertama memiliki jumlah vektor yang sama dengan himpunan kosong. Mungkin maksud Anda adalah kumpulan kolom kosong? Saya pikir lebih bersih untuk tidak mengubahnya.01
memiliki properti X:(1) = (0) + (1)
. Jika Anda ingin mengecualikan itu maka Anda harus mengatakan bahwa dua set kolom harus dipisahkan.2^m
kombinasi kolom untuk memeriksa properti X. Jika kami dapat merancang skema "bertemu di tengah" (lihat masalah "jumlah penjumlahan"), ini mungkin dapat mengurangi itu menjadim * 2^(m/2)
...Jawaban:
16/9 20/11 22/12 28/15 30/16 32/17 34/1836/19 (Jawa)Ini menggunakan sejumlah ide untuk mengurangi ruang pencarian dan biaya. Lihat riwayat revisi untuk detail lebih lanjut tentang versi kode yang lebih lama.
0
dan1
) dan bekerja; Saya menggunakan algoritma yang dijelaskan dalam kode A Gray untuk kalung dengan kepadatan tetap dan kata-kata Lyndon dalam waktu diamortisasi konstan , Sawada dan Williams, Theoretical Computer Science 502 (2013): 46-54.BigInteger
untuk memberikan tes yang tepat. Saya mendapatkan peningkatan kecepatan yang signifikan, dengan risiko negatif palsu, dengan mengoperasikan modulo prima besar dan menjaga semuanya tetap primitif. Perdana yang saya pilih adalah yang terbesar lebih kecil dari 2 57 , karena memungkinkan mengalikan dengan basis representasi vektor nosional saya tanpa meluap.{-1,0,1}^m
memiliki negasi juga di{-1,0,1}^m
dalamnya hanya perlu untuk menyimpan salah satu dari keduanya.2n/(n+1)
, saya mempercepat dengan hanya menguji itu.Yang pertama ditemukan adalah
dan itu satu-satunya hit dalam 15 jam.
Pemenang yang lebih kecil:
sumber
n
daripadarows
, meskipun gagal-aman dalam arti bahwa itu akan membuang solusi yang valid daripada menerima yang tidak valid. Itu juga tidak mempengaruhi hasil.Python 2 - 21/12
Dalam proses membuktikan bahwa
2-(3/n)
selalu ada untuk apa punn
Terinspirasi oleh pertanyaan ini , saya menggunakan Sequence De Bruijn untuk secara paksa memaksa matriks yang mungkin. Dan setelah bruteforcing
n=6,7,8,9,10
, saya menemukan pola bahwa solusi tertinggi selalu dalam bentuk(n, 2n-3)
.Jadi saya membuat metode lain untuk memperkuat bentuk matriks itu, dan menggunakan multiprosesor untuk mempercepat, karena tugas ini sangat dapat didistribusikan. Di ubuntu 16-inti, ia dapat menemukan solusi
n=12
sekitar 4 menit:Sebagian besar perhitungan digunakan untuk memeriksa properti X, yang mengharuskan memeriksa semua himpunan bagian (ada
2^(2n-3)
himpunan bagian)Perhatikan bahwa saya memutar baris pertama ke kiri, bukan ke kanan seperti pada pertanyaan. Tapi ini setara karena Anda bisa membalikkan seluruh matriks. =)
Kode:
Jawaban lama, untuk referensi
Solusi optimal sejauh ini (
n=10
):Untuk
n=7
:Solusi dengan bentuk seperti yang dijelaskan oleh OP (
n=8
):Tapi yang lebih baik (
n=8
):Ini juga menemukan solusi optimal lain di
n=9
:Kode tersebut adalah sebagai berikut. Itu hanya kekerasan, tapi setidaknya itu bisa menemukan sesuatu yang lebih baik daripada klaim OP =)
sumber
n >= 31
, yang menyiratkan saya perlu memeriksa2^(2n-3) = 2^59
kombinasi vektor 31-dimensi. Tidak akan selesai dalam hidup kita = Dn*(2n-3)
24/13 26/14 28/15 30/1632/17 (C #)Sunting: Info lama yang dihapus dari jawaban saya. Saya menggunakan sebagian besar algoritma yang sama dengan Peter Taylor ( Edit: sepertinya dia menggunakan algoritma yang lebih baik sekarang), walaupun saya telah menambahkan beberapa optimasi saya sendiri:
HasPropertyXFast
fungsinya, yang dengan cepat memeriksa apakah ada set kecil dengan jumlah yang sama sebelum menggunakan pendekatan "bertemu di tengah".HasPropertyXFast
fungsi, saya mulai dari memeriksa set kolom dengan 1 kolom, kemudian dengan 2, 3 dan seterusnya. Fungsi kembali segera setelah tabrakan jumlah kolom pertama ditemukan. Dalam praktiknya itu berarti bahwa saya biasanya harus memeriksa hanya beberapa ratus atau ribuan set kolom daripada jutaan.long
variabel untuk menyimpan dan membandingkan seluruh kolom dan jumlah vektornya. Pendekatan ini setidaknya urutan besarnya lebih cepat daripada membandingkan kolom sebagai array.long
tipe data dan untuk pola penggunaan saya.Output program:
Kode:
File konfigurasi:
sumber
ulong
dan membiarkan shift shift alih-alih menggunakanBigInteger
.GetSumOfColumns
menambahkan loop tambahan yang saya harapkan harganya lebih dari faktor 2. Penyortiran topeng terdengar menarik: mungkin Anda bisa edit jawaban untuk berbicara sedikit tentangnya? (Dan pada titik tertentu saya akan bereksperimen dengan cara alternatif untuk melakukan aborsi awal: alasan saya tidak bisa melakukannya adalah bahwa HashSet tidak mendukung iterasi dan modifikasi bersamaan, tapi saya punya ide untuk menghindari kebutuhan akan iterator) .