ICPC Regional Jakarta 2016

Jadi beberapa waktu yang lalu (sebulan lel) aku ikut ICPC Regional Jakarta, dan karena pengen nulis, serta biar gak jadi wacana, aku tulis sekarang aja wkwk. Kemaren aku ikut sebagai tim Awrakin, dan Alhamdulillah bisa dapet peringkat 5 serta predikat Best National Team. Rada kaget sih huehue

Awrakin

Tim ini anggotanya aku, Zamil, sama Rakina. Namanya udah tau kan ya plesetan dari mana (code qlean semua suci aku penuh bug). Ini tim rada ga jelas sih, soalnya:

•  Aku selalu ngejek Rakina. Contoh: "Kin, kok fotomu yang di nametag Gemastik gak ada jerawatnya?"
• Rakina kerjanya mukul sama nendang aku. Koleksi luka luar tambah banyak semenjak kontes sama Rakina
• Zamil kayak sudah pasrah sama keadaan ini

Kami udah pernah ikut 2 lomba sih sebelumnya, INC (peringkat 2) dan Gemastik bidang pemrograman (peringkat 3) dengan nama Ristek - Kuikutsaja. Tim ini, entah karena sibuk atau apa, hampir nggak pernah latian :'( Sekalinya latian malah rada fail :''' Cheatsheet juga kami asal aja, jadinya pakai punya Terharu :') dengan sedikit modifikasi :') Strategi nggak ada yang khusus, paling yang sering dibilang:

• Kalo ada soal query kasih ke Ayaz

H-1

Harusnya kan hari sabtu ada practice session. Jum'at malam, aku baru inget kalo gak nyuci, bisa-bisa aku kehabisan baju dalam. Padahal biasanya nyuci hari sabtu atau minggu. Yaudah, jadinya malam-malam aku nyuci walaupun tepar parah. Terus kan hari itu ada demo, dan malamnya ada kerusuhan. Kupikir paling besok udah beres. Jadinya jam 10 aku tidur..
.
.
Dan terbangun esok harinya untuk mendapati akibat kerusuhan, kegiatannya dipadatin di hari Minggu. Kenapa masalah di Indonesia gak selesai-selesai sih hiks.
Jadinya hari Sabtu aku nonton anime sama ada nge-gym di CF sendirian. Hasilnya gak jelek, cuma aku sadar kalo aku tambah retard. Ngoding modular exponentiation udah ngebug. Malamnya aku tidur agak malam gara-gara keasikan baca :') RIP kontes besok.

Contest Day

Paginya aku bangun agak telat dari yang aku harapkan :' Untungnya gak telat buat ngumpul sih. Jam 6:15, naik bikun, pas belokan FIB bikunnya kayak mau keguling, terus sekalian "ngambilin" orang-orang yang telat. Nah, pas di perjalanan jadinya aku kayak yang tanggung jawab buat perjalanan itu.

Tapi kayaknya ini keputusan yang salah, karena aku bikin nyasar dengan salah nunjuk belokan di peta :'( Alhasil nyampenya jadi sedikit telat, maafkan aku kawan-kawan :'( Ini bukan cara yang baik untuk mengawali pagi. Entah kenapa dari tahun lalu aku selalu kecapekan sebelum tanding pas hari-H :'(

Sampai di Binus, langsung registrasi terus ambil baju sama nametag. Pas ketemu orang-orang, kayaknya pada ngetawain rambutku. Apa salahnya botak!? Botak itu adem parah dan potong laginya butuh waktu lama! #abaikan Habis ganti baju, escortnya ngajakin sarapan dulu, biar fotonya nanti. Aku sendiri walaupun ikut ke tempat makannya cuma ngambil minum, gara-gara udah sarapan sebelum berangkat. Kayak tahun sebelumnya, sarapan ini jadi tempat ngobrol sama ngegosip bareng sahabat-sahabat dari univ lain, sekalian foto-foto.

Lanjutan dari TOKI UI Welcoming Party
Credits: ICPC Regional Jakarta 2016

Udah gak terbang-terbang photoshop lagi :')
Credits: ICPC Regional Jakarta 2016

Selesai sarapan, kami lalu ke tempat fotonya. Untung gaya yang dipropose Rakina gak senajis gaya pas welcoming party.

Normal enough
Credits: ICPC Regional Jakarta 2016

Habis foto, kami masuk ke auditorium buat pembukaan. Selama beberapa lama pas pembukaan aku justru main sih :P Gak terlalu merhatiin pembukaan lel. Habis pembukaan, ada practice session. Kan practice session itu buat ngetes environment dll. Terus entah kenapa, yang bisa ngetik cepet sekarang cuma aku (idk Rakina Zamil kayak kurang pas sama keyboardnya). Practice sessionnya juga kebanyakan ketawa-ketawa doang, mostly aku ngetawain Rakina Zamil ngebug :v yang penting udah tes TL dan ini itu deh.

Selesai practice session, kami dapet makan siang. Kali ini aku nyomot sedikit makanan biar gak kelaparan. Habis itu kami yang muslim sholat. Disini dilema : Dijamak apa nggak? Akhirnya aku gak ngejamak, biar nanti ada waktu dimana aku bisa jalan-jalan keluar cari udara segar. Kadang kalo lagi ngerjain soal atau bikin soal aku juga sering gitu soalnya: jalan-jalan, kosongin pikiran, biar fresh lagi buat mikir, dan seringnya efektif.

Anyway, setelahnya persiapan buat kontes. Kami masuk ke ruangan masing-masing. Kebetulan, kami seruangan sama TeamTam (Agus+Rais+mas-mas Malaysia). Yang enak, kami duduk di paling belakang, dan tim sebelah kami gak datang. Jadinya aku tanpa dosa sering jalan-jalan di belakang. Lagi-lagi, kalo penasaran, ini kebiasaanku di rumah, mikir sambil jalan-jalan keliling rumah (aku gak bisa diem). Terus ada yang lucu, jadi kan nama tim kami Awrakin. Terus di amplop yang isinya cheatsheet tim kami, orangnya itu keliatan banget salah nulis, Awka Awrakin. Sayang gak difoto :(

Lalu, kontes pun dimulai! Karena ICPC Jakarta biasanya taruh soal bonus di A, jadilah aku baca A. So far so good, sampe akhirnya baca:

To punish teams who did not read this problem statement carefully, we'll add one trick input: if the input is 04-05-01, the output should be 1 (not 6).

*Mikir* *Baca soal lagi* *Mikir keras*
(dalam hati) "INI GIMANA CERITANYA OUTPUTNYA JADI 1? KAN ADA 6 CARA? MASAK SALAH NGERTI SOAL SIH?" #emosi

Akhirnya setelah Rakina bilang bisa ngerjain A, aku nyerah dan cari soal lain. Rakina juga nerangin soal L kayak interval-interval apa gitu, cuma aku gak ngerti. Zamil terus bilang E kayaknya gampang, tapi aku gak yakin, dan yaudah dia ngerjain itu dulu. Lalu aku baca soal J. Wah, cuma rumus-rumus deret geometri terus pake mod inverse. Terus aku lupa rumus deret geometri. Jadinya nurunin rumus dulu. Habis itu, A buatan Rakina ngebug, dan jadinya aku minta dia ngeprint dulu, sementara aku kerjain J. Lalu, J - Super Sum Accepted!

Aku terus baca soal K, dan rasanya soal ginian familiar. Tapi habis nyoret-nyoret, ternyata soalnya beda :( Habis itu, aku baca soal L, karena kalo mirip sekelebat yang Rakina jelasin, dan karena TeamTam udah AC, harusnya ini doable. Turns out, selain ada input yang gak penting (agency), ini mirip soal yang pernah kubuat untuk Coderclass tahun ini :/ DP simple, statenya waktu. Karena paranoid, aku tambahin coordinate compression biar statenya gak terlalu banyak, terus submit, dan L - Tale of Happy Man Accepted!

Setelah itu, aku coba bantuin Rakina benerin A. Aku baca codingannya Rakina, dan baru ngeh statement yang bikin aku gak ngerti itu ternyata cuma perlu dibikin if --" Dia suspect kala baca inputnya bermasalah, jadi yaudah kami parse manual. Tapi tetep WA. Aku terus baca soal D. Hmm, mungkin DP on Tree. Tapi constraintnya gede gitu. Mikir bentar, baru nyadar kalau tree-nya gak penting :( dan ini jadi soal kombin yang klasik gitu :( aku coret-coret rumusnya dulu biar gak ngebug, terus ngoding, dan D - Pay Day Accepted!

Aku lalu balik ke soal A. Aku baca codingannya lagi, terus baru sadar: "Kin, kalo ada angkanya yang dobel kayak 03-03-03, lu keluarannya 6 gak sih? bukannya 1?" Dan kami jadi dapet pencerahan gitu :') Aku terus modifikasi kodingannya biar bisa handle itu, dan A - Confusing Date Format akhirnya AC :'))))

Meanwhile, Zamil pake komputer karena mau ngetes soal E. Dia bilang ada soal query-query gitu, yang artinya belum kubaca. Aku baca, dan ternyata soal F. Sekilas baca, keliatan kalau model soal binser. Terus binser satu-satu kelamaan, jadinya mikir, "ah ini kayaknya bisa parallel binser deh. Tapi napa query-nya bentuknya persegi semua ya?". Akhirnya, karena Zamil kayaknya butuh waktu, aku gusur (dan ini bakal terjadi berkali-kali dalam kontes ini), dan ngoding F. Untuk caranya, aku pakai BIT 2D untuk keep-track banyak bilangan yang nilainya <= x dalam suatu interval. Jadinya solusiku O((Q + N^2) log N log MAXVAL). Awalnya gak yakin AC, tapi bodo lah ya, submit aja. Dan kagetnya, F - The Cure AC! Yay ada first solve suatu soal :")))

Habis itu aku baca soal B, dan come up sama solusi yang O(N * length * 26 * log (N * length * 26)) pake hashing. Ngecek TL yang gede, aku cukup confident bisa lolos. Aku terus nggusur Zamil lagi (habis dia ngeprint codenya), terus coding B. Pas coding, Rakina nanya di cheatsheet ada theorem matik atau nggak. Seingetku sih ada, jadi kubilang iya. Terus dia nanya "lu tau McNugget nggak?".
.
.
.
.
Kenapa ini orang nanyain McD? Terus kukacangin dan lanjut ngerjain B. Habis selesai dan tes sample, submit. Terus TLE. Sad. Aku coba mikirin optimizenya, tapi gak dapet. Terus aku nanya ke Rakina dia lagi ngerjain soal apa. Ternyata soal I, dan itu soal yang dia nanya McNugget-McNugget itu. Aku baca deskripsi soalnya, intinya dikasih N bilangan prima, dan K, cari bilangan X terkecil, X >= K, sehingga X bisa dinyatakan sebagai kombinasi linier N bilangan tersebut, dengan konstanta pengalinya non-negatif. Terus Rakina jelasin kalo dia pernah baca McNugget's Theorem yang kayaknya bisa ngebantu ngerjain soal ini, tapi dia lupa theoremnya gimana. Habis ngecerna soalnya, baru nyadar kalo ini mirip parah sama soal pas Pelatnas 4 :'( pelajaran berharga: baca semua soal. Aku ngesolve dengan modelin ini sebagai shortest path, dengan vertexnya merupakan hasil modulo prima terkecil. Terus primanya juga udah dibikin unique, kompleksitasnya kurang lebih O(smallest_prime * (N + smallest_prime)), karena entah kenapa aku paka Dijkstra's O(V^2). Submit, dan I - Peculiar Microwave AC!

Habis itu Rakina bilang B harusnya bisa O(N * length * log (N * length)). Jadi dia ngereduce semua operasi jadi pakai delete, dan itu make sense. Jadi kalau insert, bisa dipandang dengan ngedelete dari string hasil insert. Terus substitue bisa dipandang sebagai banyak string lain yang setelah delete satu karakter, dan kita delete satu karakter dari string ini, hasilnya sama. Aku lalu modifikasi solusi, dan udah stres, kebiasaan namain variabel dengan kata kasar jadi keluar. Habis itu submit, dan ternyata masih TLE. Terus habis itu baru sadar ada double counting juga, tapi karena keluarnya TLE bukan WA, tetep aja bermasalah.

Karena Zamil masih berkutat di soal E, aku sama Rakina lalu coba kerjain soal lain. Kami lalu nyoba soal K. Rakina bilang pakai dp bitmask gitu, cuma kompleksitasnya O(N * 2^15), gak feasible. Tapi jadinya aku kayak dapet hint: Formulasikan dp[mask] sebagai banyak set yang unionnya hasilnya mask, dan anggotanya non-empty (bisa 1). Aku mikir, harusnya compute dp[mask] ini bisa dalam O(3^15). Jadinya, untuk ngitung dp[mask] kita bakal iterasiin per submask-nya dia untuk ngitung subproblemnya. Cuma, aku gak dapet cara untuk nge-enforce orderingnya biar gak double counting :( sekalinya dapet, brutal parah, jadi O(15^2 * 3^15), dan jelas TLE, tapi begonya kusubmit.

At this point karena pusing, aku lalu turun ke bawah buat sholat. Balik-balik, tetep nyoba mikir. Terus Rakina bilang soal C constraintnya aneh, mungkin bisa di-maxflow. Tapi aku gak dapet graph modelling-nya. Aku malah ngerasa ini bisa di-ternary search, cuma gak yakin. Ngeliat scoreboard udah ada yang AC, bodo lah ya, coba aja, gak bakal nyesel juga. Jadinya aku nyoba ternary search + DP on DAG. Pas ngoding, tau-tau udah masuk 1 jam terakhir. Submit. Nunggu. WTF, C - Stress Factor AC.

Habis lapor C AC, Zamil takeover komputer lagi. Aku lalu nyoret-nyoret soal K lagi. Seketika merasa bodoh: Gampang nge-enforce orderingnya. Seandainya mask kita pecah menjadi submask1 dan submask2, kita bisa menganggapnya kita menambahkan elemen dengan nilai submask1 ke dalam set dengan unionnya submask2. Bagaimana caranya supaya orderingnya fix? Kita cukup pastikan submask1 mengandung MSB dari mask, dan artinya submask1 selalu lebih besar dari submask2. Ini bisa berjalan dalam O(3^15), jadi aku langsung nggusur Zamil lagi dan ngoding K. Habis tes sample, aku submit, dan udah gak TLE. WA. dafuq. Baca codingan, ternyata lupa ngemod. goblok. Habis ngemod, submit, dan K - 2-ME Set AC! :')

Habis itu, aku keluar buat ngemil bentar. Lumayan ada minum sama snack enak. Terus aku masuk lagi. Pada tahap ini, untuk soal E aku percaya saja sama Zamil dan Rakina. Aku terus baca soal G. Gak ngerti, dan sekalinya ngerti pasti gak sempet. Baca soal H. gak ngerti juga. Yaudah deh ikut bantuin Zamil Rakina.

Aku gak ngerti mereka ngoding apaan, jadi aku cuma baca kemungkinan bugnya. Pas skimming codenya, anehnya aku gak baca ada kata mod sedikitpun. Padahal seingatku constraintnya sampe 10^9, yang artinya kasarannya jawabannya bisa 10^27. Aku tanya ke Zamil, dan responnya "astaga bener juga". Yey.

Lalu semua penghitungan kami kasih mod, terus submit. WA. asem. Baca-baca lagi, ada fungsi yang kayaknya balikin range, terus nanya Zamil, "ini emang boleh dimod ya?". Terus ternyata nggak :")) Habis ilangin mod di situ, submit lagi, dan AKHIRNYA E - Guessing Game AC!!! Aku seneng banget sampai ninju Zamil. Kalo gak AC sedih kan Zamil dari siang sampe sore cuma kerjain itu :'(

11 menit terakhir kami desperate ngedebug B, karena cuma itu harapan satu-satunya buat nambah AC. Tapi udah gak kuat, dan akhirnya kami berakhir dengan 6+3 AC. Alhamdulillah :') dan setelah ngitung aku ngoding 7 soal dan bantu debug 2 soal :O Harusnya lebih banyak memperbudak Rakina. Ngobrol sama Agus, dia bilang timnya AC 10 M(_ _)M

Keluar dari ruangan sambil membawa banyak balon, terus ngobrol sama yang lain bentar. Habis itu ketemu Pak Denny, lapor kalo nambah 3. Terus top 3 INC dipisah, disuruh makan bareng sponsor dan orang-orang penting lainnya. Awrakin makan bareng orang Tokopedia. Aku sendiri gak terlalu banyak ngomong, karena terlalu capek sama pusing. Cuma makan sama minumnya aja banyak :P

Setelah semua itu selesai, ternyata makan-makan yang seabrek - tahunan ICPC Jakarta - juga udah selesai :( Kami lalu ke auditorium, sambil ngambil pernak-pernik yang belum diambil kayak yang dari Tokopedia. Lagi-lagi aku nyempetin buat main SIF bentar. Terus pas acara penutupan, ada beberapa speech dan performance, ada speech dari Menkominfo (aku baru tau Menkominfo itu yang mana lel). Oh, selain itu ada lucky draw. Meh, event ginian gak mungkin aku menang sih. Selain stat luck-ku yang kecil parah, aku juga gak dapet nomornya :v Habis itu ada Contest Review dari Pak Suhendry. Terus pengumuman pemenang. Pengumumannya dimulai dari INC, jadinya kami maju karena peringkat 2. Yey hadiah!

Top 3 INC
Credits: Pak Denny

Setelahnya pengumuman ICPC. Unlike tahun sebelumnya, sekarang pakai resolver :O Lumayan lah seru ngeliat terbang-terbang. Pas run pertama, laptopnya entah kenapa mati atau ngehang gak merhatiin. Sedihnya, pas ngeproses WinRAR - Free Trial Forever. Udah saatnya kita bayar kayaknya.

Pas run kedua udah aman. Pas Awrakin diproses, awalnya B fail, terus terbang karena C. Okeh. Terus terbang lagi karena E :') At this point, kami paling atas di tim lokal :O Lalu untuk ketiga kalinya, kami terbang karena K, dan sekarang di posisi 4. Terus kegusur sekali, posisi 5. Was-was bisa 5 besar apa nggak, tergantung tim Running dari Universitas Keio. Dan ternyata, AWRAKIN RANK 5 :")))) Kami lalu maju untuk dapat hadiah Best National Team.

Best National :")
Credits: ICPC Regional Jakarta 2016

Hadiahnya gak kira-kira: 1 Drone, 1 Samsung Gear VR, sama Xiaomi yii (gak salah tulis kan ya?).  Habis itu pengumuman top 3 nya, dan hasil akhirnya:

1. AcThPaUNpPuAmCmBkCfEsFmMdNoLr - National Taiwan University
2. TeamTam - National University of Singapore
3. LINUX - University of Engineering and Technology - VNU

Congrats!
Habis itu ada foto-foto lagi :D :

Sama Pak Menkominfo
Credits: Pak Denny

Cah UI
Credits: ICPC Regional Jakarta 2016

Hari sudah malam, sementara PR MD2 belum dikerjakan. Orang-orang UI lalu mencoba cabut. Tapi aku diajak Irvin buat foto bareng SC P1 2017. Jadi ya, kami foto dulu :')

SC P1 2017 - {Prabowo,Stacia}
Credits: Irvin

Setelah itu akhirnya beneran kembali ke Depok, kembali ke realita bahwa besok kuliah dan tugas belum dikerjakan.

In the end, terima kasih panitia yang sudah menyelenggarakan Regional ICPC yang bagus :") dan bisa tetap lancar walaupun hari sebelumnya ada kekacauan :"( Secara pribadi aku paling senang dengan Regional Jakarta, walaupun bisa saja ini karena aku memang belum ke banyak Regional lain :P

Terima kasih juga Rakina Zamil, dari INC, Gemastik, sama ICPC tahan setim sama orang kayak aku :') dari INC bikin banyak "dosa" (penalty), Gemastik nge-retard, dll. Yang jelas ICPC ini gak mungkin hasilnya sampe begini kalo gak ada kalian, tapi malas jabarin kenapanya huehue.

Seperti lomba biasanya, lesson learned, beberapanya:

• BACA PETA DENGAN LEBIH TELITI
• Biasakan ngertiin hampir semua soal untuk nentuin prioritas ngerjain -- I harusnya bisa lebih cepet disolve kalo gak terburu-buru ngerjain B
• Harusnya Rakina bisa lebih banyak diperbudak
• Biasakan mendengarkan, jangan seenak jidat ngejudge McNugget itu cuma dari McD
• Nekat itu gak salah
• Belajar sesuatu itu gak pernah rugi -- seandainya gak pernah belajar konsep Parallel Binary Search paling gak dapet F :")

 Trivia:

• Supir busnya serem :(
• Makna Nem_HCNU_Peno direveal sama Pak Suhendry. Sad.
• Zamil ngeprint soal E tiap kali aku gusur. Total bisa 5-8 kali ngeprint.
• Droneku sama Samsung Gear VR-nya Rakina dijadiin doorprize acara Pekan Ristek, walaupun masih gak terima kepada siapa Dronenya jatuh. Samsung Gear VR-ku nangkring di Ristek, karena di rumahku juga gak ada HP yang compatible.
• Suvenir Tokopediaku hampir ketinggalan, untungnya dibawa Zamil :')
• Sampai hari ini, sertifikat INC sama Gemastik punya Zamil sama Rakina masih di aku karena aku lupa ngasih. Padahal sebulan ada di tasku :v 
• Jika dihitung di tingkat nasional, maka kami:
• Peringkat 2 INC
• Peringkat 3 Gemastik
• Peringkat 1 (nasional) di Jakarta
• :O

Sekian dulu kalik yah? Lanjutnya either ngebahas soal atau ngeblog Yangon. Yangon harus diblog sih, karena belum pernah ada perjalanan seabsurd itu dalam hidupku :)