pengantar
Misalkan Anda dan teman Anda sedang bermain game. Teman Anda memikirkan beberapa urutan n
bit, dan tugas Anda adalah menyimpulkan urutan dengan mengajukan pertanyaan kepada mereka. Namun, satu-satunya jenis pertanyaan yang Anda boleh tanyakan adalah "Berapa lama urutan umum terpanjang dari urutan Anda dan S
", di mana S
ada urutan bit. Semakin sedikit pertanyaan yang Anda butuhkan, semakin baik.
Tugas
Tugas Anda adalah menulis sebuah program atau fungsi yang mengambil input bilangan bulat positif n
, dan deretan R
panjang biner n
. Urutannya bisa berupa array bilangan bulat, string, atau jenis pilihan masuk akal lainnya. Program Anda akan menampilkan urutan R
.
Program Anda tidak diizinkan untuk mengakses urutan R
secara langsung. Satu- satunya hal yang diperbolehkan untuk dilakukan R
adalah memberikannya sebagai input ke fungsi len_lcs
bersama dengan urutan biner lainnya S
. Fungsi len_lcs(R, S)
mengembalikan panjang urutan umum terpanjang dari R
dan S
. Ini berarti urutan bit terpanjang yang terjadi sebagai (tidak harus bersebelahan) berikutnya dalam keduanya R
dan S
. Input len_lcs
yang panjangnya mungkin berbeda. Program harus memanggil fungsi ini R
dan urutan lainnya beberapa kali, dan kemudian merekonstruksi urutan R
berdasarkan informasi itu.
Contoh
Pertimbangkan input n = 4
dan R = "1010"
. Pertama, kita dapat mengevaluasi len_lcs(R, "110")
, yang memberi 3
, karena "110"
merupakan urutan umum terpanjang dari "1010"
dan "110"
. Kemudian kita tahu bahwa R
diperoleh dari "110"
dengan memasukkan satu bit pada posisi tertentu. Selanjutnya, kita mungkin mencoba len_lcs(R, "0110")
, yang kembali 3
karena urutan umum terpanjang adalah "110"
dan "010"
, jadi "0110"
tidak benar. Lalu kami coba len_lcs(R, "1010")
, yang kembali 4
. Sekarang kita tahu itu R == "1010"
, jadi kita bisa mengembalikan urutan itu sebagai output yang benar. Ini membutuhkan 3 panggilan ke len_lcs
.
Aturan dan penilaian
Dalam repositori ini , Anda akan menemukan file bernama subsequence_data.txt
berisi 100 urutan biner acak dengan panjang antara 75 dan 124. File-file tersebut dihasilkan dengan mengambil tiga float acak antara 0 dan 1, mengambil rata-rata mereka a
, dan kemudian membalik-balik a
koin n
kali lipat. Skor Anda adalah jumlah ratalen_lcs
- rata panggilan ke urutan ini, skor yang lebih rendah menjadi lebih baik. Kiriman Anda harus mencatat jumlah panggilan. Tidak ada batasan waktu, kecuali bahwa Anda harus menjalankan program Anda pada file sebelum mengirimkannya.
Kiriman Anda harus bersifat deterministik. PRNG diizinkan, tetapi mereka harus menggunakan tanggal hari ini, 200116
(atau setara terdekat), sebagai benih acak. Anda tidak diizinkan untuk mengoptimalkan kiriman Anda terhadap kasus-kasus tes tertentu. Jika saya curiga ini terjadi, saya akan membuat batch baru.
Ini bukan kode golf, jadi Anda dianjurkan untuk menulis kode yang dapat dibaca. Rosetta Code memiliki halaman tentang urutan umum terpanjang ; Anda dapat menggunakannya untuk mengimplementasikan len_lcs
dalam bahasa pilihan Anda.
lcs
bukannyalen_lcs
.lcs(R, "01"*2*n)
kembaliR
. ;) Tapi itu bisa berhasil jika meneleponlcs(R, S)
akan meningkatkan skor denganlen(S)
alih-alih 1, atau sesuatu seperti itu ...Jawaban:
Java,
99,0498,4697,66 lcs () panggilanBagaimana itu bekerja
Exaple: Baris kami yang akan direkonstruksi adalah
00101
. Pertama-tama kita mencari tahu berapa banyak nol yang ada, dengan membandingkan (di sini membandingkan = menghitung lcs dengan string asli) dengan string hanya nol00000
. Kemudian kita melewati setiap posisi, membalikkan0
ke a1
dan memeriksa apakah sekarang kita memiliki substring yang lebih panjang. Jika ya, terima dan pergi ke posisi berikutnya, jika tidak, balikkan arus saat ini1
ke a0
dan pergi ke posisi berikutnya:Optimalisasi
Ini hanya implementasi "naif", mungkin mungkin untuk menemukan alogrithm yang lebih canggih memeriksa beberapa posisi sekaligus. Tapi saya tidak yakin apakah benar - benar ada yang lebih baik (misalnya berdasarkan perhitungan bit paritas mirip dengan kode Hamming), karena Anda selalu dapat hanya mengevaluasi panjang substring umum.
Untuk satu garis digit tertentu, algoritme ini perlu
#ofDigitsUntilTheLastOccurenceOf1 + 1
pemeriksaan persis . (Kurangi satu jika angka terakhir adalah1
.)EDIT: Satu optimasi kecil: Jika kita baru saja memeriksa digit terakhir ke-2 dan kita masih perlu menyisipkan
1
, kita tahu pasti bahwa itu harus berada di posisi terakhir, dan dapat menghilangkan centang yang sesuai.EDIT2: Saya baru saja memperhatikan Anda dapat menerapkan ide di atas dengan yang terakhir
k
.Tentu saja mungkin untuk mencapai skor yang sedikit lebih rendah dengan optimasi ini, dengan menata ulang semua lini terlebih dahulu, karena bisa jadi, bahwa Anda mendapatkan lebih banyak baris dengan yang di bagian paling akhir tetapi itu jelas akan menjadi dan optimasi untuk saat ini test case yang tidak lagi lucu.
Runtime
Batas atas adalah
O(#NumberOfBits)
.Kode lengkap
Berikut kode lengkapnya:
sumber
1
, yang setara dengan hanya ada nol yang tersisa.