satukubik

Hari Kamis minggu lalu, TopCoder mengadakan babak kualifikasi ke-I algoritma untuk TopCoder Open 2008 yang akan diadakan bulan Mei yang akan datang. Lumayan alhamdulillah masih bisa lolos. Mudah-mudahan masih bisa dapet kaos meskipun kelihatannya cukup sulit.

Yang menarik dari babak kualifikasi ini adalah soalnya. Terutama soal paling mudahnya yang bernilai 250. Soalnya diberi nama “Monsters and bunnies” jadi kalau di-Indonesia-kan kira-kira jadi “monster dan kelinci”. Problem statementnya kira-kira seperti ini (lengkapnya bisa diperoleh di sini):

Di sebuah kota, ada tiga jenis makhluk hidup. Kamu, x ekor monster dan y ekor kelinci. Jika monster bertemu kelinci, monster agak membunuh kelinci. Jika monster bertemu monster, mereka akan bertarung hingga keduanya mati. Jika moster bertemu kamu, kamu akan dibunuh juga oleh monster. Jika kamu dan kelinci bertemu, kamu bisa memilih untuk membunuh kelinci tersebut atau tidak.

Pertanyaannya: Jika x dan y diberikan, berapa probabilitas kamu untuk hidup?

Bingung? Tidak usah bingung. Ini persoalan cetek sebenarnya… asal tahu triknya Jawaban akhirnya 1/(x+1) jika x genap dan 0 untuk kasus lain.

Nah loh… kok bisa pertanyaan probabilitas yang kelihatannya rumit itu jawabannya jadi sederhana? Disinilah menariknya soal ini. Banyak koder yang menyangka bahwa faktor kelinci harus diperhitungkan dalam menentukan hasil akhir. Ini juga didukung dengan contoh-contoh soal yang kelihatannya seperti menjebak para koder.

Bila dilihat dari contoh soal, jelas bahwa jika x = 0 maka probabilitas kamu tetap hidup adalah 1 karena kelinci tidak dapat membunuh kamu dan sudah pasti kamu akan tetap hidup. Sebaliknya jika jumlah monster ganjil, maka kamu sudah pasti mati karena biar bagaimanapun kamu berusaha dan biar bagaimanapun jumlah kelinci, bakal ada satu monster yang akhirnya membunuh kamu. Yang menarik baru jika jumlah monster genap, karena kamu masih punya kesempatan hidup. Masalahnya adalah berapa besar kesempatan itu? Jawaban akhirnya seperti yang telah dikemukakan diatas hanya dipengaruhi oleh jumlah monster.

Hal ini seperti menimbulkan kontroversi di antara para peserta kualifikasi. Well, biasanya soal-soal TopCoder jarang yang tricky seperti ini, atau kalaupun ada biasanya nilainya lebih besar alias tingkat kesulitannya lebih tinggi. Banyak di antara peserta yang tidak sadar bahwa jumlah kelinci tidak berpengaruh terhadap hasil akhir. Dan karena ini soal ini soal paling mudah, mereka lebih konsentrasi untuk menjawab dua soal lain yang lebih sulit.

Kontes algoritma di TopCoder menarik karena selain babak koding, juga ada babak challenge di mana kita bisa melihat jawaban peserta lain dan men-challenge jawaban peserta lain tersebut. 50 poin tambahan akan diperoleh jika challenge berhasil dan -25 jika challenge gagal.

Dengan soal yang sedikit ‘nakal’ seperti itu, babak challenge jadi benar-benar luar biasa. Banyak koder yang berhasil men-challenge jawaban koder lain. Tentunya mereka yang men-challenge sebagian besar adalah mereka yang sadar bahwa kelinci sama sekali tidak berpengaruh terhadap hasil akhir. Hasilnya benar-benar menakjubkan… prosentase keakuratan jawaban soal yang seharusnya paling mudah ini menjadi dibawah 40%.

Dan itu tidak selesai sampai disana. Diskusi terus berlanjut. Salah satu yang tersadar bahwa kelinci tidak berpengaruh hanya bisa mengumpat tertahan, ‘Stupid irrelevant bunnies’. Yang masih belum yakin terus mendebat dengan berbagai cara dan meminta pembuktian matematika. Singkatnya buat saya, problem ini benar-benar problem 250 paling menarik yang pernah saya lihat. Atau malah benar-benar problem paling menarik yang pernah saya lihat.

Penulis soal ini sampai harus menulis editorial yang cukup panjang untuk soal ini. FYI, biasanya untuk soal termudah editorialnya hanya berkisar 5 sampai 10 baris. Tapi kali ini, sang penulis benar-benar mengeksplorasi semua kemungkinan jawaban dari yang paling mudah seperti disampaikan di atas, sampai mereka yang berniat mengaplikasikan dynamis programming untuk soal ini.

Begitu serunya perdebatan, sampai hari ini pun masih banyak bermunculan anekdot-anekdot lucu di forum TopCoder (mungkin ini juga kenapa saya suka dengan TopCoder. Selera humor mereka benar-benar luar biasa). Mungkin sayangnya untuk benar-benar mengerti letak kelucuan anekdot tersebut, kita harus cukup aktif mengikuti forum.

Beberapa thread yang paling menarik:

Thread ini dibuat untuk mengumumkan keberhasilan TopCoder melobi pemerintah US supaya peserta dari negara-negara seperti Iran (yang diembargo US) bisa ikut bertanding di TCO.

So now that TopCoder is involved in international politics when are we going to start seeing diplomatic contests where TopCoder members compete to solve the world’s political problems?

Well, we already saw that it’s surprisingly hard to solve the world’s monsters and bunnies problem.

Judul thread ini adalah You know you are a TopCoder when …. Isinya adalah ciri-ciri apa saja yang membuat kamu bisa merasa bahwa kamu adalah TopCoder sejati. Macam-macam isinya, ada yang berkorban besar untuk ikut SRM (Single Round Match/ kompetisi mingguan TopCoder), tentang nama-nama besar di TopCoder, dan sebagainya. Setelah persoalan kelinci dan monster ini, ada post baru:

(You know you are a TopCoder when) … you are not surprised by the fact that a couple of very intelligent people are discussing if you should kill the bunnies.

(You know you are a TopCoder when) … you and another TopCoder get into a loud and animated discussion about killing bunnies in a lab full of astonished people who have no idea what you’re talking about.

Hehehe.. sepertinya memang problem yang satu ini tidak akan bisa dilupakan dengan mudah oleh komunitas TopCoder.