Hercules Algorithm
Biasa cukup dengan disebut "Hercules" saja. Pertama kali saya menyadari adanya teknik ini adalah pada saat OSN 2009.Pada saat itu, saya menghadapi soal untuk memeriksa apakah sebuah array bilangan memenuhi pola yang nilainya menaik, menurun, menaik, menurun, dst. Apabila ya, cetak "zig-zag", dan apabila tidak, cetak indeks pertama yang menyebabkan syaratnya tidak terpenuhi. Karena sudah kehabisan waktu, saya membuat program pendek berikut:
Dan mendapatkan nilai 10 dari 100 pada soal tersebut.
Hercules adalah teknik untuk mencetak suatu nilai pada keluaran yang dipastikan bahwa peluang nilai tersebut benar cukup tinggi. Misalnya untuk soal yang saya jelaskan di atas, dipastikan ada setidaknya 1 kasus uji yang memenuhi kasus tersebut. Sehingga dipastikan saya akan mendapatkan nilai yang tidak 0.
Variasi lain dari Hercules adalah membuat fungsi yang bergantung dari input yang ada. Misalnya diberikan soal untuk membagikan N barang kepada dua orang dengan seadil-adilnya (mungkin meminimalkan selisih total nilai barangnya). Tugas kita adalah mencetak banyaknya barang yang didapatkan oleh masing-masing orang. Dengan Hercules, Anda dapat membuat program:
Peluang bahwa membagi rata N barang adalah solusi optimal terlihat menjanjikan. Pada contoh ini kita melihat bahwa menuliskan fungsi dari input yang diberikan merupakan bentuk dari Hercules.
Untuk kasus yang lebih ekstrim, random juga dapat digunakan. Misalnya untuk soal yang meminta kita mencetak nilai "YA" atau "TIDAK", solusi Herculesnya adalah:
Bergantung pada nilai yang didapatkan, mungkin ada baiknya kita cukup untuk selalu mencetak "YA" atau "TIDAK".
Teknik ini umum digunakan pada Pelatnas TOKI zaman dahulu, terutama ketika sudah mendekati akhir sesi latihan. Teknik ini sudah tidak dapat digunakan karena pada zaman modern, kasus uji sudah "dipaket". Untuk mendapatkan nilai, semua kasus uji dalam suatu paket harus dijawab dengan benar. Akibatnya peluang Hercules untuk menjawab dengan benar menjadi sangat rendah.
Saya tidak tahu kenapa namanya Hercules.
Konstanta Marshal
Konstanta Marshal adalah teknik untuk membuat suatu konstanta membatasi. Apabila program sudah memenuhi konstanta tersebut, maka program akan bertindak dengan cara yang berbeda. Sebagai contoh, diberikan sebuah array bilangan berukuran N dan angka M, lalu tentukan apakah terdapat cara untuk memilih beberapa bilangan pada array yang apabila dijumlah nilainya sama dengan M. Cetak "YA" bila mungkin, dan "TIDAK" untuk sebaliknya. Batasan untuk N adalah 30, dan M adalah 1000.
Banyaknya cara memilih angka pada array adalah 2^N. Apabila digunakan backtracking, kompleksitas solusinya adalah O(2^N). Dipastikan backtracking akan time limit exceeded.
Solusi dengan konstanta Marhsal adalah membuat sebuah konstanta K, yang membatasi apabila kita sudah mencoba K kemungkinan kombinasi, maka hentikan program dan cetak "TIDAK". Nilai K yang ideal mungkin adalah 100 juta.
Dengan cara ini, program tidak akan TLE. Apabila kombinasi yang memenuhi persyaratan sudah ditemukan pada 100 juta pencarian pertama, kita berhasil mendapatkan nilai untuk kasus uji tersebut. Apabila tidak, daripada TLE, lebih baik kita mencetak suatu jawaban asal yang mungkin saja benar (Hercules).
Konstanta Marshal dapat digunakan ketika solusi mungkin ditemukan pada K pencarian pertama. Lebih besar peluang ditemukannya, lebih ampuh teknik ini bekerja.
Menurut legenda, teknik ini berasal dari Brian Marshal. Saya pernah membaca post dari blog Brian tentang teknik ini, tetapi sekarang saya tidak dapat menemukannya.
Hybrid Algorithm
Teknik Hybrid merupakan teknik menggabungkan beberapa algoritma untuk menjawab suatu persoalan. Pertama kali saya mengetahui teknik ini adalah dari Aji.
Misalnya diberikan soal untuk menentukan urutan paling optimal untuk melakukan instalasi N program. Setiap program ke-i membutuhkan waktu A_i untuk di-setup, dan B_i untuk proses instalasi. Pada suatu waktu, kita hanya dapat melakukan setup untuk 1 program. Ketika suatu program memasuki proses instalasi, kita dapat meninggalkannya dan melakukan setup untuk program lain. Tentukan waktu terpendek supaya seluruh N program terpasang.
Soal ini memiliki aroma greedy yang sangat kuat. Sepertinya program-program ini harus diurutkan dengan suatu parameter, supaya didapatkan urutan optimal. Namun apabila kita tidak yakin harus memilih parameter yang mana, kita bisa melakukan hybrid untuk beberapa parameter, mencobanya, lalu mengambil hasil yang *paling optimal*.
Sebagai contoh, kita mungkin saja mencoba untuk mengurutkannya berdasarkan:
- Waktu setup
- Waktu proses instalasi
- Waktu setup dikurangi waktu proses instalasi
- Waktu proses instalasi dikurangi waktu setup
- Rasio waktu setup dengan waktu proses instalasi
- Rasio waktu proses instalasi dengan waktu setup
- ...
Hybrid juga dapat digunakan untuk mengurangi keraguan. Pada era sebelum IOI 2010 atau OSN 2011, peserta tidak dapat melihat nilai programnya sampai akhir kontes. Ketika peserta membuat kesalahan kecil pada implementasi, akibatnya sangat fatal. Nilainya bisa jadi lebih rendah daripada nilai peserta yang mengerjakannya dengan solusi brute-force.
Pada kenyataannya, seringkali algoritma yang optimal sulit diimplementasikan. Pada sisi lain, algoritma sub-optimal mudah diimplementasi. Sehingga yang dapat dilakukan adalah membuat if:
Hibridisasi ini memastikan nilai untuk solusi sub-optimal sudah dicapai. Saya pernah menggunakan teknik ini untuk Pelatnas 2 TOKI 2011, ketika harus mengimplementasikan DP 5 dimensi secara bottom up + flying table.
Tidak ada komentar :
Posting Komentar