Panduan ACM-ICPC Programming Contest (part I)

ACM-ICPC Programming Contest tahun ini akan segera dimulai, melalui post ini saya ingin membagi pengalaman saya mengikuti ACM-ICPC Programming Contest pada tahun-tahun sebelumnya.

Apa itu ACM-ICPC

ACM-ICPC Programming Contest adalah suatu ajang perlombaan yang mengadu kemampuan algoritma dan pemrograman mahasiswa untuk membuat program yang dapat menghasilkan output yang benar dari input yang diberikan oleh juri. Perlombaan ini dibagi menjadi 2 tingkat, yaitu Regional dan World Final.

Untuk bisa mengikuti perlombaan Regional harus merupakan perwakilan dari universitas. Universitas dapat mengirimkan sebanyak mungkin team untuk mengikuti Regional yang ada. Karena kita kuliah di Indonesia, maka kita dapat mengikuti Regional Asia, dimana pada tahun ini perlombaannya ada di :

• Aizu (Jepang)
• Amritapuri (India)
• Beijing (Cina)
• Chengdu (Cina)
• Dhaka (Bangladesh)
• Hangzhou (Cina)
• Harbin (Cina)
• Hefei (Cina)
• Ho-Chi-Minh-City (Vietnam)
• Jakarta (Indonesia)
  
• Kanpur (India)
• Kuala Lumpur (Malaysia)
• Seoul (Korea)
• Taipei (Taiwan)
• Tehran (Iran)

Untuk bisa mengikuti World Final, team harus menjadi juara atau runner up di Regional yang diikuti. Hanya boleh 1 team dari universitas yang ikutan World Final. Untuk yang mengikuti Regional pada tahun ini, World Final akan diadakan di Stockholm, Swedia, April 18-22 2009.

Persiapan yang dilakukan

Untuk bisa menang dalam sebuah kompetisi, tentunya kita harus banyak berlatih dan berdoa. Perlu ketekunan dan semangat untuk terus belajar mendalami algoritma dan pemrograman. Saya sangat menyarankan untuk berlatih setiap hari secara teratur. Latihan untuk sukses mengikuti lomba ini dapat berupa hal-hal berikut:

• Mengerjakan soal-soal di Online Judge
• Membaca buku-buku algoritma
• Menyelesaikan puzzle-puzzle matematika.
• Coding tiap hari (apa aja, yang penting semakin memperlancar penggunaan bahasa pemrograman).

Saran saya, lebih baik fokus memperdalam penggunaan 1 bahasa tapi betul-betul dalam (betul-betul bisa menggunakan tanpa liat help lagi).

Untuk daftar Online Judge yang ada, dapat anda lihat disini: Daftar Online Judge

Untuk buku algoritma, saya menyarankan:

• Introduction to Algorithm, karangan Thomas H Cormen
• Art of Programming Contest, karangan Ahmed Samsul Arifin
• Algorithms, karangan Robert Sedgewick
• The Art of Computer Programming, karangan Donald Knuth (saya sarankan ini yang terakhir anda baca :p)

Untuk puzzle matematika, anda bisa mencoba Project Euler

Saya juga sangat menyarankan supaya menggunakan library dari bahasa pemrograman dengan optimal (seperti STL yang ada di C++ dan Collections yang ada di Java) karena akan sangat menghemat waktu dan menghindari bug yang tidak perlu terjadi.

Pada saat perlombaan, team diizinkan untuk membawa notes yang biasanya adalah 25 halaman (masing-masing site punya aturan berbeda). Oleh karena itu sebaiknya algoritma yang sulit kita implementasikan (butuh waktu lama / sering ngebug) diletakkan dalam team notes. Karena akan membantu sekali ketika pada saat lomba, kita membutuhkan algoritma tersebut.

Berikut adalah beberapa cabang ilmu algoritma yang menurut saya sering muncul (berdasarkan pengalaman sebelumnya) :

1. Dynamic Programming, ini adalah yang paling favorit sering muncul. Biasanya minimal 2 soal akan muncul dalam regional contest.
2. Graph Theory, ini yang kedua favorit sering muncul. Biasanya juga minimal 2 soal akan muncul dalam regional contest.
3. Ad Hoc, ini biasanya keluar sebagai soal bonus(termudah) dan saya yakin selalu ada (kecuali regional Cina, saya ngga yakin bakalan muncul :p).
4. Math, Brute Force, Geometry, Advanced Tree, Advanced Graph, Number Theory.

Jumlah soal dalam regional contest biasanya 6-10 (tergantung site penyelenggara). Biasanya akan terdapat minimal 2 soal easy, minimal 2 soal medium, minimal 2 soal hard, sisanya adalah soal-soal yang menentukan untuk menjadi juara (very hard).

Pada saat hari lomba

Biasanya perlombaan untuk regional contest akan berlangsung 2 hari, dimana susunan acaranya sebagai berikut (mungkin akan berubah) :

Hari 1

• Acara pembukaan
• Sesi latihan
• Sesi tanya jawab
• Sesi seminar dari IBM
• Sesi jalan-jalan :p

Hari 2

• Acara perlombaan
• Sesi pemberian hadiah (biasanya top 10 dapet hadiah)
• Acara penutupan (makan buffet )

Pada saat acara perlombaan jangan tegang/grogi, santai saja. Rileks akan membantu konsentrasi kita sewaktu coding. Biasanya akan diberikan 2 buah copy soal kepada setiap team. Jangan pernah biarkan komputer kita istirahat(usahakan selalu menggunakan komputer disetiap saat). Perlombaan berlangsung selama 5 jam, jadi tidak perlu khawatir pada saat 1-2 jam pertama team kita tidak solve 1 soal pun. Aku punya suatu cerita menarik tentang hal tersebut, silahkan disimak:

“Teamku sewaktu di Manilla 2006 (NoMoreAC) itu tidak solve 1 soal pun dalam 90 menit pertama. Pada saat itu ada team dari Singapura (NUSSOC-2) sudah solve 2 soal. Lalu ketika NoMoreAC solve 2 soal, NUSSOC-2 sudah solve 4 soal. NoMoreAC lalu solve 3 soal, NUSSOC-2 masih 4 soal. NoMoreAC solve lagi jadi 4 soal, NUSSOC-2 masih tetap 4 soal. Sampai pada akhirnya kami berhasil solve 6 soal, NUSSOC-2 masih tetep soal 4 soal. Akhirnya tibalah masa freeze (1 jam terakhir) dimana Scoreboard tidak lagi di update. Pada saat itu NoMoreAC berpeluang solve 1 soal lagi, tapi sayang tidak berhasil . Posisi NUSSOC-2 tepat berada didepan kami dan kami mendengar mereka berteriak “YES” sebanyak 2 kali dan “YES” yang terakhir itu betul2 keras terdengar . Saat itu kami tahu bahwa mereka telah berhasil solve 6 soal juga.”

Ini hasil pertandingan kami dulu : Result Manilla 2006

Pelajaran berharga yang bisa saya dapat adalah 1 jam injury time dalam ACM-ICPC itu paling menentukan pada hasil akhir pertandingan, jadi mental kita jangan langsung “down” kalo dalam awal-awal pertandingan kita kalah jumlah solve. Kita harus terus berusaha dan berjuang sampai pertandingan berakhir.

Kemudian jangan sering-sering mendebug program melalui komputer, usahakan untuk selalu mencetak source code kita (Dalam ACM-ICPC, kita diperbolehkan untuk memprint source code yang kita buat), jadi kita mendebug program melalui kertas. Hal ini akan menghemat waktu, sehingga komputer dapat digunakan oleh anggota team yang lain untuk menyelesaikan problem yang lain juga.

– to be continued –