12:14, 12 Juni 2006
Hari Sabtu, 10 Juni 2006, menjadi saksi diadakannya Fun Programming Contest 2006 di lab 1103 Fasilkom UI. Kontes dimulai pada 8.40, sepuluh menit di belakang jadwal. Pada awalnya hanya ada 7 tim yang hadir pada arena kontes, tapi setelah selang satu jam, total 10 tim yang berpartisipasi pada kompetisi internal tahun ini.
Pada satu jam pertama, juri dikejutkan dengan adanya peserta yang mengirimkan jawaban untuk soal "Pohon Silsilah" yang merupakan salah satu soal yang sulit. Sayang, kejutan tersebut tidak bertahan lama karena jawaban tersebut salah. Solusi pertama yang benar dikirimkan pada menit-menit awal dari jam kedua oleh Daniel Albert untuk soal "Persegi Panjang" setelah jawaban pertamanya untuk soal ini gagal. Akan tetapi, posisi pertama hanya dipegang oleh Albert selama 7 menit, karena Rizky Andriawan berhasil menjawab soal "Ular" pada percobaan pertama. Tak lama kemudian, pasangan Ricky Suryadharma dan Teddy masuk ke dalam papan nilai dengan program mereka, juga untuk soal "Ular".
Awal jam ketiga, Ricky dan Teddy berhasil menjawab soal "Persegi Panjang" dan menduduki ranking 1 menggeser Rizky. Satu jam kemudian Albert berhasil menjawab "Pusat Massa Segiempat" dan Rizky kembali tergeser. Posisi ini terus bertahan hingga akhir lomba.
Peserta tamu kita dari Fakultas Kedokteran, Deni Lukmanul Hakim, menjadi satu-satunya peserta yang berhasil memecahkan soal pada satu setengah jam terakhir. Deni berhasil menyelesaikan soal "Pusat Massa Segiempat" dan "Persegi Panjang". Dalam papan nilai tidak resmi, Deni menduduki posisi ketiga. Selamat.
Aktivitas kontes cukup ringan, dengan total submisi yang dikirimkan selama kontes berlangsung adalah 66. Jumlah submisi yang benar adalah 7. Semoga jumlah ini dapat meningkat setelah melalui pelatihan klub pemrograman.
Berikut ini adalah analisa jawaban soal-soal yang ditampilkan pada Fun Programming Contest 2006.
| Jumlah pengumpulan | 16 |
| Sukses | 0 |
Soal ini adalah soal klasik yang sudah berulang kali muncul dalam berbagai konteks yang berbeda. Inti dari soal ini adalah mencari solusi untuk masalah Knapsack 0-1. Solusi yang benar menggunakan teknik Dynamic Programming dengan kompleksitas O(N * K), dengan N banyak file, K kapasitas CD-ROM. Deskripsi solusi ini dapat ditemukan di berbagai buku teks tentang algoritma, seperti Introduction to Algorithms yang digunakan untuk kuliah Analisis dan Design Algoritma.
Klik di sini untuk mendapatkan contoh solusi dalam C.
| Jumlah pengumpulan | 18 |
| Sukses | 0 |
Soal ini adalah contoh soal yang penyelesaiannya sederhana, tapi banyak lubang jebakan. Ini adalah tipikal soal ICPC, di mana ketelitian dan kejelian dalam menganalisa kasus dibutuhkan. Banyak peserta yang jawabannya sebetulnya sudah benar tapi tidak dapat menangani kasus-kasus istimewa. Solusi dari masalah ini adalah melakukan simulasi seperti yang diminta oleh soal.
Jebakan pertama adalah masalah keluar grid. Bila sebuah turtle sudah keluar dari grid, maka posisi terakhir dari turtle tersebut sebelum keluar grid harus dicatat, sesuai yang tertera pada deskripsi soal. Kita tidak mempedulikan orientasi turtle sebelum jatuh.
Jebakan kedua ada pada masukan itu sendiri. Suatu turtle bisa saja tidak memiliki perintah apapun untuk dijalankan. Selain itu, dapat pula sebuah grid tidak memiliki satupun turtle untuk dijalankan. Kebanyakan solusi peserta gagal pada jebakan kedua ini.
Ada sejumlah trik dalam implementasi solusi yang dapat membuat solusi menjadi cukup ringkas. Trik-trik tersebut dapat dipelajari dari model solusi untuk soal ini.
| Jumlah pengumpulan | 11 |
| Sukses | 2 |
Menurut saya ini adalah soal termudah kedua dalam kontes ini. Dari segi solusi, soal ini adalah yang paling pendek solusinya.
Deskripsi soal yang matematis sebetulnya bila ditelaah perlahan memberikan jawaban dari permasalahan yang diamati. Cara ini yang tertera pada deskripsi soal dan digunakan oleh Albert untuk mendapatkan jawaban yang dicari.
Satu hal yang cukup berperan dalam menyelesaikan soal ini dengan mudah adalah intuisi. Bagi yang mengingat rumus pusat massa (xpusat = (x1 + x2 + x3 + x4) / 4, sama untuk ypusat) dari pelajaran fisika mungkin dapat langsung menggunakan rumusnya. Akan tetapi, hal itu tidak perlu dilakukan bila pengamatan soal dilakukan dengan jeli. Dari deskripsi titik pusat, koordinat x (dan juga y) selalu berada di tengah-tengah koordinat x keempat titik sudut. Hal ini kemudian dapat diverifikasi dengan melihat contoh yang diberikan. Ada 2 peserta yang berhasil menemukan cara ini pada waktu kontes berlangsung, tapi sayangnya mereka melakukan kesalahan dalam pembacaan masukan. Selain itu, perlu juga berhati-hati dengan kesalahan presisi yang muncul ketika menggunakan variabel berbasis floating point.
Implementasi model solusi dapat ditemukan di sini.
| Jumlah pengumpulan | 2 |
| Sukses | 0 |
Soal ini muncul sebagai soal berbobot 300 pada final Google Code Jam India 2006. Cukup banyak yang dapat menyelesaikan soal ini pada final tersebut, walaupun model solusi yang digunakan untuk kontes tersebut memiliki kompleksitas O(N3). Model solusi tersebut tidak cukup efisien untuk soal ini, sehingga perlu dicari solusi yang kompleksitasnya lebih rendah. Pada analisis ini akan saya paparkan solusi tersebut yang dilanjutkan dengan paparan solusi berkompleksitas O(N2).
Ide dasar untuk memecahkan masalah ini adalah kita mencoba melakukan level traversal dari pohon silsilah mulai dari akar pohon hingga daun pohon. Untuk setiap bebek, kita dapat membuat daftar semua leluhurnya, karena kita memiliki semua data leluhur terdekat bebek tersebut dengan semua bebek lainnya. Akar dari pohon silsilah ini adalah bebek yang tidak memiliki leluhur selain dirinya.
Setelah kita mengetahui bebek yang menjadi akar pohon tersebut, kita hapus bebek tersebut dari daftar leluhur bebek-bebek lainnya. Untuk melakukan hal tersebut, kita dapat melakukan iterasi terhadap daftar leluhur bebek-bebek lainnya dan mencari apakah bebek tersebut memiliki leluhur bebek yang menjadi akar pohon atau tidak. Bila ada bebek yang dalam daftar leluhurnya tidak ada lagi leluhur selain dirinya, maka bebek tersebut memiliki ibu bebek yang menjadi akar pohon. Kita masukkan bebek tersebut ke dalam daftar yang perlu diiterasi berikutnya. Untuk bebek-bebek yang baru ini, kita ulangi hal yang sama dengan bebek yang menjadi akar pohon. Sayangnya iterasi daftar leluhur dari semua bebek lainnya memakan kompleksitas O(N2). Karena ada N bebek yang akan kita kunjungi, maka total kompleksitas dari solusi ini adalah O(N3).
Untuk mengakali kondisi ini, kita dapat membuat daftar keturunan. Bila seekor bebek A memiliki leluhur bebek B, maka bebek B memiliki keturunan bebek A. Daftar keturunan ini dapat dibuat dengan mudah menggunakan array boolean dua dimensi untuk menghilangkan duplikasi. Pembuatan daftar keturunan ini juga dapat dilakukan seiring membaca input. Selain itu, kita juga dapat menghitung jumlah leluhur dari semua bebek dan menyimpannya dalam sebuah array. Kompleksitas untuk membuat daftar keturunan dan array jumlah leluhur ini adalah O(N2).
Sama seperti solusi O(N3), kita kemudian melakukan level traversal untuk menemukan ibu dari setiap bebek. Awalnya kita mulai dari bebek yang memiliki jumlah leluhur hanya 1, yaitu dirinya sendiri. Kita masukkan bebek tersebut ke dalam antrian. Untuk setiap bebek A dalam antrian, kita lakukan iterasi pada daftar keturunannya. Untuk setiap bebek yang berada dalam daftar keturunan bebek A tersebut, kurangi jumlah leluhurnya. Jika jumlah leluhurnya adalah 1, maka bebek tersebut kita masukkan ke dalam antrian dan kita dapat menyimpulkan bahwa bebek tersebut memiliki ibu bebek A. Karena untuk setiap bebek kita perlu melakukan iterasi sebesar O(N), maka kompleksitas untuk solusi ini adalah O(N2).
Kode dari solusi ini dapat diambil di sini.
| Jumlah pengumpulan | 3 |
| Sukses | 2 |
Soal ini adalah soal dengan tingkat keberhasilan paling tinggi. Sayangnya, tampaknya tidak ada banyak peserta yang mencoba mengerjakan soal ini.
Ada dua masalah yang perlu dipecahkan dalam soal ini. Pertama, untuk menemukan semua ular tanpa duplikasi. Hal ini dapat dilakukan menggunakan flood fill (bila tidak tahu, coba cari di google). Untuk setiap kotak yang masih bernilai X, kita lakukan flood fill (dapat dengan DFS maupun BFS) dan mengubah bagian yang menyambung dengan kotak tersebut dengan nilai lain, misalnya -.
Setelah kita menemukan struktur tubuh seekor ular, kita perlu mengetesnya untuk mencari tahu apakah ular tersebut melilit atau tidak. Ada dua cara untuk melakukan ini. Cara pertama adalah untuk melakukan rekursi untuk mencari tahu apakah struktur ular tersebut dapat dibentuk tanpa adanya lilitan. Cara kedua adalah untuk mencari tahu apakah pada sebuah kotak pada struktur ular yang bertetanggaan dengan > 2 kotak bagian lain ular tersebut. 2 kotak adalah bagian banyak kotak maksimum yang dapat bertetangga dengan sebuah kotak karena seluruh bagian ular harus tersambung. Lebih dari itu, kita dapat menyimpulkan bahwa banyak bagian dari ular tersebut yang bersinggungan dengan bagian lainnya.
Model solusi untuk soal ini dapat diambil di sini.
| Jumlah pengumpulan | 0 |
| Sukses | 0 |
Matriks ini sebetulnya soal yang cukup mudah. Intinya adalah sekali kita menetapkan nilai sebuah elemen pada matriks baris R atau matriks kolom C, nilai elemen-elemen yang lain langsung dapat ditentukan. Misalnya, dengan menentukan nilai elemen R1, kita dapat menentukan nilai semua elemen pada matriks kolom C dengan menggunakan baris pertama dari matriks A dan matriks B. Setelah itu, kita bisa menggunakan, misalnya, elemen C1 pada matriks kolom C dan kolom pertama dari matriks A dan matriks B untuk menghitung nilai elemen-elemen yang lain dari matriks R. Yang tersisa kemudian adalah verifikasi untuk semua elemen dari matriks A dan B.
| Jumlah pengumpulan | 15 |
| Sukses | 3 |
Soal ini adalah soal yang cukup mudah berikut soal Pusat Massa Segiempat. Soal ini dapat dengan mudah dipahami, sehingga banyak yang mencoba mengerjakannya.
Ada dua pengamatan yang dapat dilihat pada saat menganalisa deskripsi soal, walaupun hanya satu yang dibutuhkan untuk menjawab soal ini. Pengamatan pertama adalah kita tidak perlu memperhatikan koordinat dari tiap-tiap persegi panjang. Yang perlu kita perhatikan hanyalah ukuran kedua dimensinya (panjang dan lebar). Hal ini didukung dengan dibolehkannya melakukan translasi. Dengan pengamatan ini, setiap kali kita membandingkan dua persegi panjang, kita butuh mengecek 4 kasus yang mungkin.
Pengamatan kedua adalah kita diizinkan melakukan rotasi. Pengamatan ini dapat membuat coding jauh lebih mudah. Mengapa demikian? Kita dapat mengambil patokan bahwa ukuran dimensi pertama (misalnya panjang) selalu ≥ daripada ukuran dimensi kedua (lebar). Dengan adanya patokan ini, kita mengurangi jumlah kasus yang perlu diteliti hingga setengahnya.
Setelah kita melakukan pengamatan ini, kita dapat dengan mudah melakukan perbandingan setiap pasang dua persegi panjang, dan menghitung berapa banyak pasang yang dapat dibandingkan. Dengan demikian, solusi soal ini memiliki kompleksitas O(N2).
Solusi untuk soal ini dapat didownload di sini.
| Jumlah pengumpulan | 0 |
| Sukses | 0 |
Begitu membaca soal ini, cara pertama yang langsung terpikir oleh saya adalah brute force. Ternyata cara ini adalah yang diinginkan oleh pembuat soal, seperti yang tergambar pada batas masukan yang hanya 5 * 5.
Langkah pertama yang dapat dilakukan adalah melakukan prekalkulasi jarak terdekat dari satu kotak ke kotak lainnya. Ini dapat dilakukan dengan mudah dengan menggunakan BFS. Hal lain yang dapat dilakukan adalah dengan mencatat lokasi semua angka, dikategorikan berdasarkan nilai angkanya. Tujuannya adalah untuk mempercepat proses percobaan.
Brute force dapat dilakukan baik secara rekursif maupun iteratif berdasarkan kategori angka. Hal ini dilakukan karena tidak ada gunanya kita memasangkan dua bilangan yang nilainya berbeda. Untuk setiap kategori angka, kita catat berapa banyak pasangan yang dapat dibuat beserta penalti minimum yang diperoleh. Untuk melakukan akumulasi nilai penalti, kita dapat menggunakan hasil prekalkulasi yang telah kita hitung sebelumnya.
Untuk mempercepat brute force, kita dapat melakukan memoisasi terhadap kombinasi-kombinasi pasangan yang sudah kita hitung sebelumnya. Kompleksitas dari cara bruteforce dengan memoisasi ini adalah O(2(N*M)/2 * (N*M)2). Dengan demikian, program dapat mencari solusi dalam batas waktu yang ditetapkan.