ACM ICPC Kaohsiung-Taiwan 2012 : Day 2

 Day 2 : 23 November 2012
Well hari itu gw bangun pagi karena di telpon Kak Muhsin dan magicnya, gw gak ngantuk lagi :)) kayaknya dia pakai sesuatu deh >.<. Selesainya mandi dan siap siap, pakaii baju ACM ICPC Taiwan, kami berangkat menuju Universitas Sun Yat Sen. Setelah diberi pengarahan dan menitipkan barang, kita langsung menuju ruang kontes.

Posisi sementara, gw dan Welly baca soal dan Alvin bangku panas (Baca : Kursi Coding). Waktu kontesnya mulai parah banget, tanpa ada apa apa, tiba tiba ada orang pake mic bilang "Oke contest start" ~_~. Gw gak tau dia ngomong apa karena suaranya gema, tapi karena yang lain udah buka soal, berarti gw asumsikan dia bilang kontes mulai. Gw langsng minta amplop soal, pas gw mau buka susahnya bukan main jadi langsung gw robek (Hampir kerobek problemnya). Gw baca problem A, B, C sisanya gw kasih mereka berdua.

Soal A : Diberikan sebuah angka N, hitung berapa jumlah angka 1 jika N diubah menjadi bilangan biner {0, 1}. dan hitung berapa minimum angka 1 jika N diubah menjadi bilangan basis signed biner {-1, 0, 1}. Dan bilangan N bisa samai 120 Digit.
Soal B : Diberikan puzzle 3 * 3 kayak mainan anak kecil, 1 - 8 dan 1 kosong. Dikasih state awal dan akhir, Hitung langkah minimum agar state awal = state akhir.
Soal C : Diberikan jalur travel di tiap node mempunyai region. Kalau regionnya sama, gak usah bayar, kalau regionnya beda harus bayar. Dicari berapa biaya minium jika kita mau dari node X ke node Y dan kita adalah orang dari region Z.
Soal D : Diberikan sebuah deretan bilangan. Berapa biaya minimum agar A1 <= A2 <= A3 <= ... <= An dan maksimal bilangannya adalah X dan selisih Ai dengan A i-1 adalah Y.
Soal E : Gak Baca
Soal F : Gak Baca
Soal G : Diberikan 3 perusahaan dengan masing masing mempunyai N buah keompok pekerja. Cari perusahaan yang kalau kita bikin kelompok pekerjanya jadi 2 bagian, memiliki selisih paling dikit.
Soal H : Diberikan pola bentuk garis pada koordinat dimana setiap N, region koordinat menjadi 2^N * 2^N. Kita disuruh mencari koordinat berapa titik nomer X dan mana yang merupakan titik terjauh dari tetangganya (atas, bawah, kiri, kanan).
Soal I : Kalau gw gak salah ngerti soal. Diberikan graph beserta node dan edgenya, kita mau mark N buah node dengan syarat, kalau node A sudah di mark, maka node yang bersebelahan langsung dari A tidak boleh di mark. Hitung berapa maksimal node yang bisa kita mark.
Soal J : Ada N buah orang dan N buah orang ini membentuk suatu complete graph. Kita tau mana yang teman dan mana yang musuh. Jika ada 2 yang musuhan maka dia jadi teman (Teman = +, Musuh = -. - sama - = +). Hitung berapa group maksimal yang bisa dibentuk jika groupnya balance (kalo gak salah yang -'nya genap dan +nya boleh berapapun).

Soal yang pertama kami AC itu soal B, gw yang ngoding dan pas di sample I/O 2 salah, gw sama ko Welly debug dan akhirnya AC, abis itu ternyata Pandawa AC juga. (Balon balon :D). Abis itu alvin katanya nemu yang H, dia jelasin ke ko Welly dan gw cari soal yang bisa solvable. Gw bilang ke ko Welly G bisa di DP, tapi memorynya terlalu besar untuk top-down. Akhirnya kita pake Map dan ternyata TLE, Ko Welly coding DP Bottom-up akhirnya AC setelah kita debug. Alvin yang masih mikirin H gw bantu ternyata dia udah bisa ubah dari nomor titik ke koordinatnya, gw bantu debug dan akhirnya ko Welly turun tangan juga. Akhirnya AC setelah sadar ternyata Alvin salah rumus.

Ko Welly coding soal C dan gw sama Alvin corat coret soal D. Setelah kita dapat, langsung ngusir ko Welly buat kita coding =)). Setelah gw coding, loh kok untuk semua testcase, jawaban kita lebih minimu ? (Kita menemukan jawaban lebih optimal dibanding juri =))). Ternyata ada yang Bug parah di fungsi Absolutnya. Setelah di debug, bener untuk semua sample, pas kita kirim TLE -_- Gawat. Akhirnya kita print dan kita debug sedangkan Welly lanjut coding C. Ko Welly bilang udah dan katanya mungkin TLE, akhirnya kirim aja dan bener TLE juga. Pas gw sama Alvin optimize code D kita kirim ternyata tetep TLE, kita gak tau lagi akhirnya kita bantu ko Welly. Pas memonya diubah menjadi int array (Sebelumya map) ternyata jadi WA. Kita mikirnya ada harapan AC karena udah gak TLE. Ternyata kita tau Bugnya waktu pencetakan jawaban dimana harus minimum dan jika ada yang sama harus leksikograf. Pas dibenerin Priority_queuenya, ternyata masih WA. Sampai akhir kita tetap Solve 3 sedangkan Pandawa nambah 2 waktu Freeze. Kata mereka, mereka solve H <= 10 detik sebelum kontest berakhir :)), wah GG :).

Selesai kontest kita jalan jalan ke pantai + poto poto (FYI : Di univnya, belakangnya itu pantai WoW). Setelah bosan kita kembali ke Gym untuk pengumuman lomba. Awalnya adalah pengumuman NCPC (National Collegiate Programming Contest) Membosankan sekali karena banyak bener team lokal yang dapat penghargaan -_-. Abis itu baru pengumuman ICPC. dan WHAT soal A adalah soal termudah dan G sama H itu sekitar medium karena ketauan dari banyaknya team yang AC. "-" kenapa kita gak Solve yang A. Pas udah selesai kontest gw tanya teddy caranya dan masih gak ngerti =)). Dan ternyata Pandawa rank 7 mungkin berdasarkan Univ Congratz for them :). Kita terdepak gak tau rank berapa :(.

Setelah dianalisis, ternyata yang C itu Djikstra dan kita udah mungkin 89% udah kayak Djikstra tapi masih WA. dan yang D itu linear searchnya diganti Binary Search sisanya sama kayak DP kita -_- Close Enough :(. Harusnya kita bisa dan yah emang harus banyak latihan lagi :). Malamnya pas di hotel gw ko Welly sama Alvin ngomongin yang A dan ternyata harusnya bisa. . Aduhhhhhh dan yang I gw udah kasih tau problemnya ke ko Welly katanya dia bisa tapi gak kesentuh sampai akhir kontest. Aduhhhhhhh dan pas Alvin baca soalnya katanya dia bisa. Aduhhhhhhh. Moral of the story : "Baca soal seberapapun dikitnya soal itu di solve". Dan yah akhirnya kita ngeDotA map lucu sampai pagi =)).

ACM ICPC Kaohsiung-Taiwan 2012 : Days 0 & 1