Dec 222010
 

Day 3: Kontes!

Hari berikutnya gw bangun lebih awal, sebelum jam 7 udah bangun. Gw liat jam weker… lho koq beda ama jam tangan. Gubrak!! baru inget jam weker gw belum gw majuin 1 jam (masih jam indo), pantesan kemarin wekernya belum bunyi padahal udah 7:30 =.=. Gak lama kemudian pintu diketok tanda sarapan datang. Kali ini BK Wrapper yang ada tulisan chicken di bungkusnya, makan :-D.

Jam 8:25 kita orang turun ke lobi hotel yang ternyata udah ditungguin panitianya karena kita telat =.= (sebenarnya sih yang telat cuma Panji, kita nungguin dia doank). Sampai di kampus kita registrasi ulang lagi, titip tas, dan mereka masuk ke ruang kontes.

Gak lama kemudian (kurang lebih jam 9) kontes pun dimulai, gw nongkrong di bangku penonton di bagian atas (itu kan gedung olahraga). Kebetulan tim Hope duduknya deket pinggiran, jadi gampang foto mereka. Sedangkan tim Faith rada jauh di tengah, jadi sulit ngambil foto mereka, zoomnya ga sampe.

Sekitar 40 menit setelah kontes dimulai gw dapat kopi soalnya dari panitia, baca ah…

Total ada 10 soal, gw coba bahas sesuai dengan urutan soal yang gw baca:

A. Spread Out Message
Ini soal yang paling banyak disolve di awal-awal kontes. Ternyata ga susah, cuma diminta cari MST aja (maximum).

J. Falling Gift Game
Ini juga banyak yang bisa dan ternyata ga susah juga, cuma dynamic programming simple aja. Wah, gw jadi mikir, patut ditiru nih, soal bonusnya MST ama DP, ICPC Jakarta juga dibikin lebih susah ah soal bonusnya :p.

G. Tree Representation
Ini juga nggak susah. Diberikan sebuah tree dengan label berbeda-beda. Tree ini diberikan dengan representasi berikut: Cari node leaf dengan label terkecil dan hapus node tersebut dari tree, lakukan hingga hanya tersisa satu node. Kita dikasi sequence parent dari node yang dihapus, diminta output tree aslinya. Ya gampang, tinggal bikin pair setiap parent node yang dikasi sama node yang seharusnya dihapus.

D. Mobil Communications
Awalnya gw ga ngerti ini soal maunya apa dan ternyata gw salah baca satu kalimat. Setelah gw ngerti, ini soal cuma nyari jarak terdekat dari semua pasang titik. Gw ga mikir jauh di soal ini dan lanjut ke soal berikutnya, tapi si Kurniady ada post di milis kalo ini soal tinggal Closest Pair of Points (iya juga sih). Ya gampang lah.

H. Q-Bacteria
Soal yang ini gw ga ngerti maunya apa, problem statementnya ribet banget dan pake istilah aneh-aneh (famma, malus, verum, dkk). Tapi feeling gw sih ga susah dan tinggal BFS aja. Kata Ricky ini soal cuma cek cycle ganjil aja.

F. Houses
Diberikan rectangle grid dengan beberapa cell rusak, kita diminta membangun sebanyak-banyaknya rumah yang berukuran 1×2 atau 2×1 di grid tersebut dengan tidak ada rumah yang menempati cell rusak. Ukuran gridnya bisa mencapai 200×200. Ga gampang tapi ga susah juga, tinggal bipartite-matching setiap cell dengan tetangganya yang nggak rusak. Kalau satu cell akhirnya dipair dengan cell sebelahnya (hasil matchnya), artinya mereka bisa bangun rumah di situ.

E. AR Game
Wogh, ini soal makan 5 lembar. Sample input/outputnya 3 lembar. Intinya sih image recognition. Dikasi beberapa shape trus inputnya itu salah satu shape itu tapi bisa dirotasi/mirror/skala dan bisa ada noise yang ga lebih dari 3%, kita diminta mengenali itu shape apa. Si Winardi ketemu cara licik yang cukup pinter, dia ga mengenali itu shape apa dari jumlah pixelnya karena setelah diamati ternyata shape satu dengan shape lain jumlah pixelnya berbeda cukup jauh. Jadi ga usah pusingin masalah noise 3% lagi :-D.

B. Bricks
Soalnya ga susah dimengerti dan gw pernah mau bikin soal yang mirip gini buat ICPC Jakarta tapi ga jadi. Intinya kita dikasi beberapa bidang dan disuruh hitung ada berapa shape yang serupa di bidang tersebut. Shapenya ini bisa hasil rotasi/mirror/skala. Ya bisa dibruteforce sih… tapi gw liat banyak bener tim yang WA di soal ini, kemungkinan sih ada precission error.

C. 2D Folding Game
Jujur gw ga ngerti ini soalnya maunya apa pada awalnya. Bahasanya gw ga ngerti: “An embedding of P into R is an injective function phi: {1, …, m} -> V from the positions of the sequence to the vertices of the lattice that assigns adjacent positions in p to adjacent vertices in R i.e., (phi(i), phi(i+1)) in E for all 1 ≤ i ≤ m – 1.” Gimana ga mabok?? Tapi setelah dibaca-baca ulang dan liat sampe input/output gw jadi ngerti ini soal maunya apa… ga gampang :). Feeling gw sih bruteforce, tapi bruteforcenya ga kepikir enaknya gimana, ribet.

I. History of Dots
Soal yang ini sampe kontesnya selesai gw tetep ga ngerti maunya apa. Yang bisa solve soal ini total ada 7 tim.

Overall gw liat soal-soal Kaohsiung tahun ini rata-rata susahnya itu pas baca soalnya. Kebanyakan problem statementnya muter-muter bikin mabok.

Alhasil sampe kontes kelar, Hope berhasil solve 7 di rank 15 dan Faith solve 4 di rank ga jelas. Di atas Hope ada 9 tim dari National Taiwan University!! Jadi kalau dihitung-hitung, Hope itu berada di peringkat 6 sebenarnya (berdasarkan rank universitas). Juara 1 nya adalah tim National Tawan University (319ea952988933f93af9dcf1d6e4c2) , mereka berhasil solve 10 soal. Di peringkat 2 ada University of Tokyo (USAGI Code) dan di peringkat 3 ada National Taiwan University (+1 ironwood branch) yang juga solve 10 soal.

Hasil kontes bisa dilihat di sini.

Selesai kontes peserta dibawa jalan-jalan keluar kampus yang ternyata ke pantai mereka. Meskipun masih jam 3-4 siang, tapi di sana anginnya sejuk, gak panas. Setelah gw tanya-tanya, ternyata emang lagi winter jadi ga panas, kalau summer katanya sih panas. Ini pantai katanya sering jadi tempat nongkrong couple-couple dan emang gw liat di situ juga lagi ada beberapa couple bersantai ria.

Si Panji sempat iseng minta gw fotoin dia pas lagi loncat, timingnya rada susah tapi dalam 2-3 kali jepret gw udah dapet. Si gendut pengen ikutan minta difotoin juga… tapi yang ini SUSAH BANGET. 5-6 kali jepret pun masih ga dapet, dia di udara itu ga sampe 0.5 detik! Timingnya susah banget! Ini orang terlalu berat…

Selesai refreshing pasca kontes, kita orang kembali ke gedung lomba buat awarding. Wah, banyak bener awardnya. Kayaknya hampir semua tim lokal Taiwan dapat award dari kontes lokal mereka. Pas awarding buat ICPC, ternyata Hope rank 5! Woooooo…. ternyata SJTU ga dimasukin ke rank karena mereka bukan di subregion sini.

Selesai awarding, kita dibawa ke tempat makan-makan masih di dalam kampusnya. Makanannya juga enak-enak! Tempat makannya ternyata di tepi pantai, jadi habis makan sempat ke pantainya meski gelap-gelap :-D.















  4 Responses to “ACM-ICPC 2010 Kaohsiung”

  1. bukan 2.66 GB, tapi 2.66 Ghz…cmiiw 🙂

  2. eh, kita hari keberapa sih ke BK malem2 itu? =)) yang lu pergi ke “CL” :p~

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)