Selasa, 08 Desember 2015

ICPC Regional Jakarta 2015

Halo semua! Melanjutkan post selanjutnya, kali ini saya akan menulis tentang perjuangan tim saya, Terharu :') , di ICPC regional Jakarta beberapa hari yang lalu. Seperti yang diketahui dari post sebelumnya (baca dulu kalau belum baca :3 ), tim saya lolos ke regional Jakarta lewat INC.

Preparation

Untuk mempersiapkan diri, kami terkadang latihan di lab Fasilkom. Jadi buat kakak-kakak yang mungkin terganggu karena kami cukup ribut, maaf ya :') Latihan kami juga biasanya cuma nge-gym di CF, yang sering kepotong karena waktu udah cukup malam atau kami udah gila. Sebelum kontes ini, saya belajar beberapa algo baru, seperti Johnson's Algorithm, algoritma untuk menghitung bridge secara online, dan Gomory-Hu Tree. Malam menjelang practice session, team notebook kami belum jadi lo :') Jadinya kami semi begadang (semi karena banyak yang tumbang). Akhirnya, team notebook kami 21 halaman algo dan theorem + 4 halaman kotak-kotak.

Practice Session

Hari Sabtu, kami kumpul dulu di Fasilkom buat bareng-bareng pergi ke Binus naik Bikun. Saya datang pagi buat finalisasi team notebook sama Anthony. Setelah final, mau minta Agus ngeprint, Agusnya malah udah sampe Fasilkom. Jadinya kami nyoba ngeprint di lab babe. Cuma printernya asdfghhjkl. Yaudah ganti rencana, ntar ngeprint di Binus.

Sampai di Binus, kami registrasi dulu. Tiap kontestan dapet kaos biru (yay!). Pas registrasi, rada nervous juga ngeliat tim dari luar yang keliatan mukanya jago-jago. Habis kami ganti baju, ambil foto, akhirnya sarapan (yay!).

Pas sarapan, setelah sekian lama ketemu sahabat-sahabat TOKI lainnya :') Jadinya sesi sarapan banyak diisi dengan ngobrol. Habis sarapan, kami digiring ke aula buat pembukaan. Pembukaannya yah kayak pembukaan biasa lah, rada lucu aja pas tiap tim dipanggil, karena ada yang namanya susah dibaca seperti Koukyoukoukokukikou, yang dieja seperti H1N4, dan yang bisa dibaca secara universal seperti sen(3.14).

Setelah itu, kami makan siang dan sholat. Habis sholat, papasan sama Anthony dan escort tim kami, katanya mau ngeprint team notebook. Yaudah saya ikut, dan untungnya kami sempat ngeprint hingga detik terakhir :')

Setelah itu, practice session. Gak banyak yang kami lakukan, cuma nyoba ngerjain soalnya, ngetes klarifikasi, ngetes print, dan ngetes banyak operasi per detik. Kalau gak salah yang kami dapat banyak operasinya sekitar 200 juta per sekon. Karena bingung mau ngapain, kami ngeprint lagu doraemon yang dimodifikasi juga.
Tim JKT48 - Terharu :')
Credits to Anthony

Contoh klarifikasi yang baik
Diambil dari FB Pak Denny
Setelah itu, kami kembali ke Depok. Sepanjang perjalanan cuma nontonin orang-orang main quizup. Pas udah sampe, awalnya mau ngerjain PR sama Agus, cuma Agusnya pulang duluan. Teyek emang. Yaudah saya pulang. Tentu saja PR-nya nggak dikerjakan.

Contest Day, Murphy's Law does Exist

Saya mengawali hari sebagai mahasiswa teladan : mengerjakan PR. Akan tetapi, hal ini bikin saya agak terlambat ngumpul di Fasilkom. Parahnya, sampai setengah 7 Agus gak muncul-muncul. Ditelpon gak diangkat-angkat. Karena takut terlambat, akhirnya saya diantar Aldi ke stasiun UI, lalu lari ke apartemennya Agus. Saya gedor-gedor kamarnya, terus orangnya malah bilang

"Ini jam berapa?"

Saya reply dengan setengah teriak. Habis itu kami buru-buru ke stasiun UI, nunggu bikun kami datang. Setelah itu, kami naik dan sepanjang perjalanan saya habiskan dengan mencoba tidur, yang untungnya bisa saya lakukan. Setidaknya, setelah sekian lama saya akhirnya melakukan olahraga pagi.

Sesampainya di Binus, kami langsung sarapan. Setelah sarapan, kami masuk ke ruang kami. Dapet tempat di sudut, sebelahan sama DELAPAN.3gp T_T. Nunggu kontes dimulai, timernya diganti-ganti terus dan beda ruang countdown-nya bisa beda-beda :v Dan akhirnya, kontes dimulai!

Awalnya, kami mencoba mencari soal bonus. Setelah baca semua soal, akhirnya soal yang menurut kami cukup mudah baru soal A. Problemnya simple, cuma coba-coba pasang operator. Begonya, saya bikin masih ngebug. Selang beberapa menit, A - Arithmetical CAPTCHA Accepted.

Setelah itu saya baca-baca problemsetnya lagi. Ketika saya sedang baca, Agus pakai komputernya buat ngerjain soal I. Pas masih baca-baca, liat scoreboard, terus tau-tau ada yang AC soal L! Saya dan Anthony langsung baca soal L, dan ternyata math.

Ayaz : "Siapa yang bisa matik?"

Sudden realization : kami gak ada yang lumayan bisa matik.

Saya lalu coba ngutak-atik dikit, terus nyerah. Akhirnya saya baca-baca soal lagi, dan dapet soal F ternyata hanya simulasi. Setelah sedikit ngebug, soal yang dikerjain Agus, I - National Disaster AC!

Saya lalu mencoba bikin soal F. Harusnya hanya simulasi, tapi entah kenapa ngebug -_- setelah ngebug dan rombak beberapa tempat, F - Problem on Group Trip AC! Seandainya gak ngebug mungkin bisa first solve :'''

Kemudian, kami bertiga diskusi sebaiknya ngerjain yang mana. Agus bilang soal K jadi soal Maximum Sum kalau pakai logaritma, hanya saja karena saya agak trauma dengan log semenjak IOI 2015, saya pikir lebih baik fokus di soal lain dulu. Akhirnya, kami bertiga mencoba mengerjakan L. Karena tidak mendapatkan ide, saya malah propose untuk bikin solusi ngide. Solusinya cuma ngerandom sebanyak-banyaknya, terus cari GCD dari semua cara random tadi. Ketika propose, saya pikir seharusnya pakai random sudah cukup kuat. Daripada komputernya nganggur, jadinya dibolehin Anthony.

Setelah itu saya coding, dan test sample yang untungnya hasilnya benar. Setelah comment debug-debug, saya submit. Wrong Answer.

Akhirnya, saya coba pikirin soal B, sementara Agus sama Anthony mikir soal G. Karena nganggur, saya liat solusi L saya. Wah, bodoh sekali. Print solusinya dicomment, sementara print debugnya dibiarin. Setelah submit lagi, L - Summation and Divisors AC! Gak sia-sia suka judi.

Kemudian, kami bertiga kerjain soal B. Lumayan jelas kalau ini jadi kayak grundy, tapi karena N nya 10^9, pasti ada polanya. Anthony bikin generator grundy-nya, tapi entah kenapa saya kurang yakin dan bikin ulang, yang ujung-ujungnya hasilnya sama :') maafkan aku Thon :')

Karena Agus mau ngerjain soal G, kami ngeprint losing state untuk cari polanya. Gak tanggung-tanggung, kami ngeprint semua losing state <= 1000. Ketika saya dan Anthony ngerjain beberapa anggota awalnya, kami tidak bisa menemukan polanya. Sial.

Karena B gak nemu pola, saya coba ngerjain soal yang lain. Saya baca-baca soal, lalu putusin untuk ngerjain soal C. At least ada berita baik, G - Dungeon Trap kami Accepted!

Sambil saya coba mikirin soal C, Anthony yang masih nyari pola soal B tiba-tiba bilang kalau setelah suatu titik, polanya bakal konsisten. Dan ternyata benar! Setelah itu, kami tinggal bikin losing state yang kurang dari titik tersebut, dan sisanya tinggal pakai polanya. Soal B - Udin and Ucok Accepted!

Setelah itu, saya dan Anthony mikir soal C, sementara Agus mulai ngerjain soal J. Pas lagi mikir ide soal C, tiba-tiba dapet ide penting : kalau disimulasikan biasa + binary search, kompleksitasnya akan jadi O(N * log(N) * log(N)) karena harmonic series. Lucu juga ketika semua terasa jelas ketika diomongin keras-keras.

Karena sudah cukup yakin dengan C, saya dan Anthony mulai ngerjain soal H. Ternyata saya salah baca soal, dan soal versi saya salah mengerti itu jauh lebih brutal dari soal aslinya. Saya mikirnya mesinnya bisa jalan di 2D. Anthony juga salah ngerti soal. Dia kira mesinnya bisa jalan berkali-kali. Ya, 2 kesalahan terkadang tidak jadi kebenaran ketika digabung.

Saat awalnya, saya pikir bisa O(N * M^2). Akan tetapi, karena rasanya bakal TLE, tidak saya pikirkan. Selain itu, ternyata saya salah, karena masih ada variabel A dan B. Anthony mikir mungkin bisa jadi O(N * M * log(M)) pake ternary, tapi gak diprove jadi ada kemungkinan besar bakal salah.

Meanwhile, Agus mulai stres. Solusi H-nya gak lolos-lolos TC sample. Awalnya mau saya takeover buat ngerjain soal C. Tapi karena dia yakin, jadi yaudah biarin dulu. Setelah beberapa menit, moment of truth . Agus salah ngerti soal. Langsung lemes.

Habis itu, saya ngoding C. Saya bikin offline, dan setelah ngebug, tes sample, akhirnya saya submit. Setelah grading lama, Time Limit Exceeded. Bingung, saya coba debug dan optimisasi, hasilnya sama, TLE. Sudah mulai stres, pada submission ke-n (lupa berapa), karena masih TLE jadinya saya pergi buat sholat.

Balik dari sholat, saya baru sadar (dan ingat) kalau disediain makanan. Lots of makanan. Karena lapar, saya ambil secara acak. Setelah makan, "wah nanti harus makan lagi"

Balik-balik, sambil mencoba ngedebug C, Agus kerjain D. Setelah bikin TC acak, saya kaget karena program saya tidak berhenti-berhenti. It turns out I made a lot of fatal bugs. Karena C tidak berbuah hasil, saya print, lalu Agus mulai ngoding D.

Setelah makan waktu cukup lama, Agus selesai implementasi D. Buru-buru, submit, dapet WA. Jadi, pada saat freeze time kami kerja paralel : Saya debug C, Agus debug D. Sekitar 20 menit terakhir, akhirnya gantian saya yang nyoba benerin C, sementara Agus dan Anthony benerin D. Menit-menit terakhir kompetisi dapat diringkas menjadi :

Saya debug C - Agus suruh ubah suatu bagian di D - submit C/D - gak AC - Saya debug C

5 Menit terakhir, saya belum AC - AC, dan Agus tiba-tiba menemukan sesuatu yang fatal tapi entah kenapa bisa gak Runtime Error :O Setelah saya ubah itu, submit, lalu saya kembali ngerjain C. Selang beberapa saat, D - An ICPC Problem without Statement AC!! Saya lalu ngebom soal C, namun sayangnya gak ada yang AC :'(

Habis itu, pas keluar, dibagiin analisis problemsetnya. Rasanya kesel banget pas baca analisis soal C sama kayak solusi saya, yang artinya saya gak bisa ngoding dengan benar :( Selain itu, trauma saya benar-benar membawa masalah, begitu melihat analisis soal K :( Habis itu, kami makan dan sholat, lalu bersiap-siap untuk penutupan.

Pas penutupan, awalnya ada presentasi dari blibli. Tapi sejujurnya, antara saya yang tidak tertarik atau lelah, semua hanya masuk telinga kanan keluar telinga kiri :( Setelah itu, ada semi-pembahasan dan statistik dari kompetisi tadi oleh Pak Suhendry. 

Sebelum masuk ke pengumuman ICPC Jakarta, diumumin dulu juara INC 2015 sama pembagian hadiahnya. Dari sini, kami dapet voucher blibli (punya saya mau dipakai bapak saya wkwk).
 
Duit!
Credits : Pak Denny

Kemudian, mulai dibaca ranking dari yang solve 4 kalo gak salah (maaf udah lupa, udah tua)

 Masuk ke top-10, Saya mulai deg-degan. Yang saya khawatirkan seandainya DELAPAN.3GP nambah AC. Soalnya, seandainya mereka gak nambah, kami ngegeser mereka dan jadi rank 3. Selain itu, saya juga khawatir seandainya ada tim lain yang meroket ketika freeze time. Namun, untungnya kekhawatiran itu tidak terlalu berarti, karena sampai rank 5, nama kami maupun DELAPAN belum disebut. Oh iya, begitu masuk rank berapa gitu, di slidenya juga ditampilin hasil perjuangan tim rank itu di final scoreboard.

Ketika mau masuk rank 4, saya benar-benar tidak sabar. Yang saya ingin liat justru cuma 1 : Time AC di soal D. Seandainya waktunya mepet di akhir, artinya itu kemungkinan kami. Kemudian:

D. 2/200
Saya meninju keras kursi kosong di depan saya.

Di menit-menit terakhir, kami berhasil merebut posisi ketiga :''') Kami dipanggil ke panggung, kemudian disebut kami dapet 3 biji Zenfone 2. Selain itu, kami dapat "Best Local Team" (duit++). Juara 1 nya RRWatameda, yang AC-nya banyak banget :')

2nd Runner-up + Best local team
Credits : ???


Note : Pas kami dipanggil, saya baru sadar nama tim kami bisa jadi lucu, ketika ada orang nanya "Kalian Terharu ya?"

Setelah itu foto-foto, dan tiap univ juga diberi kesempatan foto-foto

Credits : Pak Denny
Malamnya ditutup dengan menyenangkan : more free foods! Saya kalap dan makan banyak sekali sampai gak kuat makan xD Sehabis ngobrol-ngobrol sama Pak Auzi tentang plastic model dan Irvin nimbrung ngomongin Pelatnas dsb, tim UI pulang, dengan selamat, sentosa, hermawan (?)

Wew, lama juga bikin kayak beginian :'D padahal udah nyuri-nyuri waktu pas DDP (maaf Pak Denny), sama gak ngerjain tugas (ini sih akunya yang malas). Mungkin post ini terlalu panjang dan agak ga jelas :' tapi terima kasih bagi kalian yang sudah menyempatkan diri membaca! :D

5 komentar:

  1. Gw lupa gw udah pernah nanya ini ato belom,

    soal C lu udah pake memoisasi? (jawab querynya langsung kalau udah pernah jawab sebelumnya). Kalo ga pake memoisasi bisa O(NQ)

    BalasHapus
    Balasan
    1. Oh, lupa nulis kalau aku ngerjain C-nya offline, jadi pas query tinggal cari di memonya. Kalau gak salah pas processing offlinenya banyak ngebug

      Hapus
  2. Kak, punya editorial-nya gak? Atau boleh minta source code pas kontes? Mau belajar tapi gak ada referensi :')

    BalasHapus
    Balasan
    1. Editorialku antara di Anthony atau Agus :') source code pas kontes gak bisa diambil :'(

      Hapus
  3. Wah congrats kak...(telat banget)...klo top 3 gtu bisa ikut WF gtu ga sih kak? thx kak infonya :)

    BalasHapus