Yakk…. setelah dibuka selama 1 minggu, kelar juga akhirnya lomba nya. Sebagai info, lomba ini diselenggarakan oleh ITB (nice ^^ and applause buat temen2 di itb terutama alumni2 toki yang sudah ikut andil dalam penyelenggaraannya). Kali ini nama tim adalah SleepingPanda (terinspirasi dari suatu movie ) Anggotanya sama kyk ICPC kemarin, Gue, Eko Wibowo, dan Lie Gunawan. Problem set untuk penyisihannya terbilang mayan bagus, dalam arti benar-benar algoritmik dan modelnya memang model soal Algorithm Contest, selain juga karena tingkat kesulitan soal yang diberikan. Walau beberapa soal di antaranya keliatannya seolah-olah diambil dari Online Judge, tapi IMO ok lah. Hasil untuk tim gue (SleepingPanda) sebenarnya bagus, tapi ga bisa dibilang bagus amat sebagai kontestan World Final ICPC -_- (tapi gimanapun harus bersyukur ^^). Yah, kami mendapat kritikan karena hanya berada di posisi 2 (kalah dari tim Bontor Humadong dari ITB), yang mana “katanya” memalukan sebagai salah satu kontestan World Final ACM ICPC ~_~ Oh para senpai2, maklumilah kami yang cupu2 ini Mungkin Panda nya musti dibangunin nih :p

Untuk Kali ini gue ga bahas terlalu banyak. Gue cuma bakal bahas soal-soal yang jadi jatah gue pas penyisihan kemarin. Kalau mau liat kira-kira gimana soalnya, ada link2 ke soal2 yang mirip di berbagai OJ, silahkan main2 ke postingan blognya si marcadian AKA Eko Wibowo di sini. Di blog dia juga ada pembahasan singkat beberapa soal.

Ok mari mulai

Soal B -> Bipartite Matching. Bagi jadi 2 kelompok node, yaitu yang horizontal dan yang vertikal. Sisanya tinggal pasang edge antara 2 node yang berpotongan, lalu cari maxflownya. Skor : 60. Ntah terkena TLE atau MLE, soalnya worst jumlah node bisa mencapai puluhan ribu, dan gue pake adj matrix mentokin 5000×5000 boolean Keliatannya harus pake adj list, mengingat pada kasus terburuk, meski node banyak, edgenya sebenarnya sedikit.

Soal E -> Dynamic Programming. Untuk tiap titik, gue coba bfs sambil caching (memo), untuk mencari berapa panjang path optimal bila puncak path ada di titik tersebut. Skor : 100.

Soal I -> Ga usa dibahas. Gue brute force soal ini =)) Ga kepikiran solusi optimal nya. Ga nyangka masih dapat 50 =))

Soal J -> Convex Hull. Gue pake Graham scan, trus tinggal pilih titik paling kiri atas, trus iterasi semua titik di convex hull nya searah jarum jam. Skor : 100

Soal K -> Dynamic Programming. DP dengan state (L,R), yaitu bagaimana yang optimum dari posisi L ampe R. Jenis soal ini gue ud pernah kerja, dan AC pas di OJ. Gue kerjain ulang dengan cara yang sedikit berbeda. Tes di OJ ternyata AC. Ok submit. Ternyata disini cuma dapat 70. Kemungkinan paling besar adalah kena TLE, mengingat constraint disini agak lebih gede.

Yang mau liat hasil akhirnya siapa aja yang lolos bisa ke sini. Kalo mau liat hasil lengkap disertai skor per soal untuk tiap tim, bisa download filenya di sini

Dengan ini, lagi-lagi kami ke bandung buat Final nya Asik2, berburu brownies lagi dah =))

That’s all. See u in my next story!! ^^