The 2007 ACM Asia Programming Contest – Singapore 5


The 2007 ACM Asia Programming Contest – Singapore

Pada tanggal 13 Desember kemaren, BINUS UNIVERSITY mengirimkan 2 team ke salah satu lomba pemrograman bergengsi dunia yaitu ACM Asia Programming Contest – Singapore yang diadakan oleh National University of Singapore (NUS).

Mari pertama2 kita lihat profile team BINUS ^_^

1. ACMon

Members:

  • Cun Cun Lim (ACSlayerS 2006, Bluejack 04-2)
  • Eko Wibowo (TOKI 2006)
  • Lie Gunawan (Bluejack 06-2)

Coaches:

  • Ibu Agustina Yosanny
  • Ibu Yenlina Prasetio

2. YoiMon

Members:

  • Andrian Kurniady (IOI 2004-2005, YoiAC 2006)
  • Kenny Hartono (TOKI 2004, ACSlayerS 2006)
  • Timotius Sakti (NoMoreAC 2006, Bluejack 05-2)

Coaches:

YoiMon and ACMon

Cowo dari kiri ke kanan: saya, kenny, cun cun, andrian, gunawan, suhendry dan eko.
Cewe dari kiri ke kanan: tania (our guide), yenlina, agustina.

[JOKES ONLY]

Mari kita lihat apa yang dikerjakan oleh team ACMon pada saat practice session ^_^.

gunawan.jpg
gunawan: hmm… soal ini sepertinya cukup mudah.

cun2.jpg
cun cun: sini gun, biar gw aja yg coding.

eko.jpg
eko: hmm.. cewe yang ada di depan gw lumayan cakep :D.

[ENDING OF JOKES ONLY]

Saya akan mulai bercerita tentang kejadian-kejadian yang kami (YoiMon) alami selama jalannya pertandingan.

Pada saat kontes dimulai, kami langsung menjalankan taktik yang semalam telah didiskusikan bersama coach. Kenny mulai membuat file .cpp dan input dari semua soal yang ada. Sementara itu Andrian mulai membaca soal dari depan, sedangkan saya mulai membaca soal dari belakang.
Selang beberapa menit kemudian, Andrian menemukan bahwa problem C dapat diselesaikan dengan metode Dynamic Programming.

Problem A berhasil AC, YoiMon!!!

Pada saat Andrian mulai mengerjakan problem C, saya melihat team-team yang lain sudah banyak yang solve problem A. Kemudian saya dan Kenny mulai membaca problem A yang memang ternyata mudah :D. Yang diminta pada soal ini adalah menghitung A^B mod C.
Kenny menggantikan Andrian untuk menyelesaikan problem A dan tidak sampai 5 menit sudah selesai, setelah itu langsung submit dan langsung AC ^_^. Ini pembukaan yang sangat baik oleh Kenny :D. Saya jadi teringat ketika bulan lalu kami mengikuti lomba di Taipei, kami dapet AC setelah 1 jam :(( dan tahun lalu pada saat di Manila, team NoMoreAC dapet AC setelah 1,5 jam :((.

Problem C berhasil AC, YoiMon!!!

Setelah Kenny selesai coding problem A, Andrian langsung melanjutkan problem C dan sekitar 5 menit kemudian selesai, disubmit AC ^_^, YoiMon!!!. Wow saya sangat senang sekali, kalo ngga salah waktu itu TOKIERS020606 ada dibawah kami posisinya ^_^. Problem C adalah soal simulasi yang dapat dipecahkan dengan metode Dynamic Programming(biasa disingkat DP). Andrian Kurniady adalah master DP di team kami, soal2 seperti itu adalah “makanan sehari2nya” andrian :p, apalagi kalo dia udah pake “dpmat” variabel :D.

Setelah itu saya mulai membaca problem E, Andrian mulai mengerjakan problem B dan Kenny membaca problem G. Sebelumnya saya dan Andrian sempat membahas tentang bagaimana memecahkan problem G. Problem G: diberikan weighted graph yang undirected, cari minimum cost untuk membentuk himpunan E(kumpulan edge2), supaya semua kemungkinan cycle pada graph itu melewati salah satu anggota dari E. Idenya Andrian adalah mencari semua cycle yang ada terus dijalanin min-cost max-flow. Wow, sepertinya sulit banget :(.

Problem G berhasil AC, YoiMon!!!

Pada saat Andrian mengerjakan problem B, saya melihat banyak sekali team yang berhasil AC problem G. Saya penasaran dan akhirnya membaca ulang problem G sambil mencari teknik mudah untuk bikin AC soal ini. Makin lama, saya melihat sepertinya ini berhubungan erat dengan Minimum Spanning Tree. Saya memberitahukan hal ini pada Andrian dan Kenny. Andrian menyempurnakannya menjadi Maximum Spanning Tree ^_^, kemudian ia mulai mengerjakan soal G sampai setengah (Disjoint-Set Data Structures), setelah itu saya lanjutkan sampai akhir.
Kemudian disubmit dan langsung AC… YoiMon!!!

Problem F berhasil AC, YoiMon!!!

Problem F ini cukup panjang ceritanya, tapi algonya mudah ^_^. Andrian mengerjakan soal ini dengan Algoritma Djikstra (terlalu over, tapi ngga apa2, yg penting AC πŸ˜€ πŸ˜€ πŸ˜€ ). Problem ini juga bisa diselesaikan dengan Floyd-Warshall ( ACMon memberitahu kami setelah selesai lomba ).

Problem D berhasil AC, YoiMon!!!

Pada saat itu kami telah berhasil menyelesaikan 4 soal dan masih tersisa waktu 2 jam lagi. Kami semua yakin bakalan sapu bersih semua soal, Andrian telah menemukan cara untuk menyelesaikan problem D, saya menemukan cara untuk menyelesaikan problem E ( yang pada akhirnya saya sadar bahwa cara yang saya gunakan masih sangat lambat pada keadaan worst-case :(( ), dan Kenny memutuskan untuk mengerjakan ulang problem B menggunakan A* .
Andrian menyelesaikan problem D, kemudian submit terus dapet WA :(. Setelah itu diperbaiki, submit lagi langsung AC! YoiMon!!!
Untuk Problem D, saya hanya bisa bilang seperti ini:
“Relax, Andrian Kurniady was there ^_^”

Masih ada waktu sekitar 50 menit lagi, dan problem D yang berhasil disolved oleh Andrian membangkitkan semangat kami kembali :D.
Sebelum problem D solved, TOKIERS020606 telah berhasil solved 5 problems( A, B, C, F, G ). Saya kemudian mulai “membakar” semangat Andrian untuk solve problem B dengan berkata: “mon, si felix udah solve problem B, masa u kalah mon :p”. Jurus ini pernah saya gunakan 1,5 tahun yang lalu ketika saya mengikuti PIC 2006 bersama Ryan :D.

Sampai akhir pertandingan kami(YoiMon) masih tetap solve 5 soal dan harus puas dengan peringkat 7 πŸ˜€ .
Saya masih penasaran dengan problem E, kemudian saya bertanya pada Sofasquad (team dari Shanghai Jiao Tong University) tentang cara untuk menyelesaikan problem E. Mereka mengatakan bahwa problem E adalah tentang struktur data, dan kita dapat menggunakan “Segment Tree” untuk solve soal ini dengan kompleksitas O(n lg n).

Rejudge Problem B

Beberapa hari setelah perlombaan, telah diketahui bahwa solusi juri untuk problem B telah salah. Saya tidak terlalu terkejut mendengar bahwa solusi juri telah salah. Karena pada saat perlombaan, Andrian sangat yakin bahwa solusinya benar. Problem B adalah tipe soal Dynamic Programming yang merupakan “makanan sehari2nya” andrian :p, apalagi kalo dia udah pake “dpmat” variabel :D. Kenny juga berpendapat bahwa problem B cukup mudah. Team-team peringkat atas juga banyak yang ngga solve soal ini. Hal ini sudah mencurigakan, karena problem B adalah soal DP yang algonya sudah pasti ^_^. Akibat dari rejudge ini, YoiMon jadi berhasil solve 6 soal dan mendapatkan peringkat 5 (sebetulnya masih urutan 7) di situs ACM/ICPC.

Special Thanks

  • Suhendry Effendy, yang telah melatih kami selama beberapa bulan terakhir ini.
  • Ibu Yenlina, yang telah menyediakan konsumsi dan ruangan selama pelatihan ACM.
  • Felix Halim, yang telah membantu untuk terjadinya rejudge problem B :D.
  • Teman-teman pelatihan ACM 2007 (Albert,Andrian,CunCun,David,Eko,Gunawan,Kenny,Nicolas,Panji,Ronald) untuk pengalaman dan kenangan indah selama pelatihan ACM. Sampai bertemu lagi di pelatihan ACM 2008 ^_^.

Merry Christmas 2007 and Happy New Year 2008

5 comments

  1. YoiMon!!! lumayan juga hasilnya, gak sia-sia latihan selama ini meskipun target membuat Prime nggak masuk World Final jadi gagal πŸ˜›

    Ayo mon, tahun depan giliran lu bantu di pelatihan πŸ˜€

    btw, itu yang eko pikirin (di foto) emang beneran koq πŸ™‚ gak usah dilabelin jokes juga gpp ;;) bwahahahaha :))

  2. hahahahaha sialan…cuma iseng buka ternyata ada ginian πŸ˜› itu gua lg ngapain aja udah lupa kok gua berasa nih jokes sasaran utamanya gua ya πŸ˜›

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s