Kamis, 13 Desember 2018

ICPC Regional Singapore 2018

Nggak, aku nggak ke Singapore.

Tadi aku ikutan mirror ICPC Singapore 2018. Nah, kemarin aku gak yakin bisa ikutan apa nggak, soalnya ada yang harus kupelajari terkait TA. Terus Degol sama Inigo ada kuliah. Tapi ya, daftar-daftar aja dulu di Kattis. Oh, bisa bikin nama tim. Aku bikin nama tim cuma biar gak keliatan ikutan aja. Awalnya mau bikin "Your Lonely Tayo Driver" (pun intended) atau "Ching chong Does Not Dream of Bunny Boy Classmate" (entahlah lagi keinget Sakurajima Mail). Tapi, kalo misalnya ada kemungkinan nanti aku ikutan kontes dengan low effort, buat apa aku put effort untuk bikin nama tim. Aku liat layar, oh placeholder kalo gak ada nama timnya itu "(no name)". Aku copas, jadiin nama tim deh.

Post ini bakal bahas soal-soal yang kukerjain pas mirror, sama yang udah ku-upsolve tadi pas maghrib. Soal dibahas sesuai urutan aku ngerjain. Scoreboard mirror bisa dilihat di sini, dan solusi-solusiku bisa dilihat di sini.

Oiya, aku rada late start karena harus presentasi dan tadi dosennya agak molor datangnya :< Iya, aku selama 2 jam pertama ngerjain di kelas, setelah aku presentasi. Terus antara ngerjain A sama D aku gak ngerjain karena lagi belajar terkait TA (gak fokus sih) sama brunch.

B - Hoppers (menit ke-26)

Karena loncatnya 2, artinya semua bakal kekunjungi iff grafnya  bukan bipartite. Itung ada berapa connected component, sama cek di antara connected component itu ada yang nggak bipartite apa nggak. Bisa pake DFS/BFS biasa. Kalo ada yang bukan bipartite, jawabannya banyak_component-1. Kalo nggak ada, banyak_component. O(N + M).

L - Non-Prime Factors (menit ke-28)

Modifikasi sieve, sama loop harmonic aja. Precompute semua jawabannya dalam O(MX log MX) (MX = 2 juta), terus jawab tiap pertanyaan dalam O(1). Jadinya O(Q + MX log MX).

J - Free Food (menit ke-30)

Aslinya karena kecil bisa main loop brute force aja, cuma aku tadi pake prefix sum soalnya ngodingnya gampang juga. O(N + 365) = O(N).

C - SG Coin (menit ke-48)

Hmm, ada cerita blockchain segala. Tapi intinya sih, daripada nyari transaction string, gampangan nyari token, secara dia cuma ditambahin di akhir. Aku selalu set transaction string = "a", terus brute force mau hasil hash-nya berapa, yang merupakan kelipatan 107. Kalo token yang dibutuhin nilainya gak di luar batas, yaudah langsung ambil aja. O(1). Btw, aku salah set nilai maksimum tokennya jadi 107 di solusiku :)) tapi ya tetep nemu solusi sih.

F - Wi Know (menit ke-79)

Misal prev[d] menyatakan indeks terbesar sehingga elemen ke-d dan elemen ke-prev[d] sama. Misal 4 indeks yang mau kita ambil berturut-turut a, b, c, d. Misal kita fix-kan nilai c. Maka, a pasti paling enak pake elemen pertama yang nilainya sama dengan c. Terus, ini bakal ekivalen dengan nyari indeks d, sehingga prev[d] > a, yang nantinya dijadiin b.

Aku pake segment tree yang rada aneh rasanya. Segment tree-nya untuk nyari dari suatu range [1, x], nilai prev yang mana nilai elemennya (A[prev[]]) itu = i, untuk 1 <= i <= x. Ada mainan update berdasarkan prev, terus nyari x minimum, sehingga nilai query(1, x) itu > a. Maaf aku agak gak jelas jelasinnya, rada njelimet emang solusiku :<

Awalnya aku ngoding O(N log2 N) (binary search + query segtree), tapi TLE. Jadinya aku modifikasi jadi O(N log N), ilangin binary searchnya. Baru deh AC.

Btw, submission pertamaku buat soal ini gak sengaja masuk ke Kattis lomba aslinya :')) Untuk keadilan bersama, aku submit juga ke mirror-nya supaya dapet penalty :'))

A - Largest Triangle (menit ke-138)

Kayaknya cukup langka aku mau ngerjain geometri, dan itupun cuma karena gatel kenapa ini soal pada AC :<

Aku awalnya ngerjain urut dari titik terkiri bawah. Sort berdasarkan polar angle, terus cobain untuk tiap titik lain, pasangin ke titik sekarang sebagai alas segitiga. Tinggi segitiga harusnya bisa di-ternary search, seandainya kita ngerjainnya urut. Setelah selesai, hapus titik terkiri bawah. Cuma ya.. O(N2 log N), dan TLE :<

Habis itu aku ngide, coba daripada ternary search, dibikin macam two-pointer. Gak ngeprove kebenarannya. Disubmit, WA. Habis itu ngide lagi, jawaban harusnya ada di convex hull. Terus two-pointer lagi. Duh, WA. Pas aku bikin tes sembarang, entah kenapa ada keluar digit di belakang komanya 1, padahal harusnya 0 atau 5 (karena titiknya bilangan bulat semua). Lho, lupa dikali 5. Habis dibenerin, submit, AC. Wut. Jadinya O(N2).

Btw, pas aku mulai ngerjain ini aku masih di kelas. Terus aku gerakin tanganku buat ngebayangin alas sama tinggi segitiga. Tapi pas ngelakuin aku jadi kepikiran, itu gerakannya kayak Ultraman.

Pada titik ini, aku belajar terkait TA sama memutuskuan buat brunch, karena udah lapar banget. Habis makan aslinya udah niatin gak lanjutin. Hanya saja, iseng kepikiran sesuatu yang bego di D terus mau nyobain.

D - Bitwise (menit ke-221)

Soal macem ginian pasti hampir selalu iterasi dari bit terbesar ke terkecil, lalu cek bisa gak solusi terbaiknya masukin bit itu. Untuk ngecek apakah X bisa dibentuk di K subarray, aku pake kayak DP tapi lebih kayak greedy. Untuk kemudahan, misal or(l, r) menyatakan bitwise OR dari elemen ke-l sampai ke-r, dan dp(i) adalah pair<int, int> yang mana:

  • dp(i) = {0, or(1, i)} apabila X bukan submask dari or(1, i)
  • Selain itu, pasti ada l sehingga X submask dari or(l, i). Cari l maksimum, terus dp(i) = {1 + dp(l-1).first, dp(l-1).second)}
Mudahnya, dp(i) menyatakan {banyak subarray max, sisa or}. Selanjutnya, brute force i, sehingga dari i+1..n akan digabung dengan sisa or. Kita bisa itung banyak subarray partisi yang mana X adalah submasknya dengan mudah dalam O(N). X valid kalo banyak subarray partisi >= K.

Nah, masalahnya untuk nyobain bit-nya ada O(log 109) bit. Terus, pas kontes aku nggak kepikiran cara sliding window or selain pake prefix sum per bit. Jadinya, solusi ini kompleksitasnya O(N log2 109). Aku coba kasus sembarang di laptopku, 4 detikan. Liat TL Kattis, hmm 3 detik. Aku coba submit aja. To my surprise (and annoyance), dapet AC dalam 2.2 detik. Setelah kelai sama TL F sama A, tau-tau di sini malah lebih ringan :s Habis chat sama Ammar pasca kontes, katanya emang N diturunin jadi 500.000 di kontesnya. Oh, pantes kepangkas separo.

Anw, tadi kepikiran cara mangkas O(log 109) dari prefix sum. Intinya ganti ke sparse table sih, soalnya kita bisa precompute untuk tiap length, berapa 2 pangkat terbesar yang <= length. Jadinya sekarang ngecek or(l, r) bisa dalam O(1). Silahkan cek D2.cpp kalo masih penasaran.

I - Prolonged Password (menit ke-251)

Phew, untung yang bikin soal baik, panjang string transformasinya di rentang [2, 50]. Untuk soal ini, aku bagi 2 kasus, yang K <= 100 sama K > 100.

Pertama, misal dp(k, char) itu menyatakan panjang string kalo kita transformasi char sebanyak k kali. Ini bisa dalam O(k * |T|) doang. Untuk kemudahan, batasi dp(k, char) dengan nilai yang > 1015. Misal kita pengen nyari karakter ke-x dari string hasil transformasi char sebanyak k kali. Kita bisa iterasi sebanyak O(|T|), ngecekin karakter ke-x itu munculnya sebenarnya hasil transformasi karakter mana dari Tchar dengan memanfaatkan dp tadi. Jadinya, karakter ke-x juga bisa dicari dalam O(k * |T|).

Nah, kenapa tadi aku bagi kasus? Intinya sih:

  • Kalo K <= 100 (bukan tight bound), kita harus cek dia itu awalnya transfomasi dari karakter mana di S. Nah, masalahnya |S| <= 106. Kalo kita loop aja, bisa O(|S|) per query, TLE dong. Jadinya.. bikin prefix sum, terus binary search karakternya pake prefix sum. Lanjutnya pake solusi di atas.
  • Kalo K > 100, pasti sebenernya itu hasil transformasi dari karakter pertama terus-menerus sampai K = 100 (kasarannya, 2100 > 1015), jadi untuk K > 100 pasti karakter ke-x ada dari transformasi karakter pertama secara terus-meneurs. Aku pake semacam sparse table untuk nyari setelah berubah K-100 kali, karakter pertamanya itu jadi apa. Lanjutnya bisa pake solusi di atas.
Keseluruhannya, per query butuh O(100 * |T|), jadi totalnya O(M * 100 * |T|).

Btw, pas ngerjain ini awalnya aku kira K itu dikasih per query juga (jadi beda-beda), terus stres karena prefix sumnya bakal jebol :')

K - Conveyor Belt (menit ke-276)

Aku gak ngerjain soal ini sampe di akhir karena males baca ceritanya (yea, i'm a simple man). Habis baca singkat, intinya ini bisa dimodelin jadi network flow. Untuk kemudahan, ubah semuanya jadi 0-index (nggak ngubah solusi). Misal (i, j) artinya vertex ke-i, pada waktu j dalam modulo K. Bikin graf berikut:

  • source ke (i, i) untuk tiap 0 <= i < K, dengan kapasitas 1 (produsen)
  • (n-1, i) ke sink untuk tiap 0 <= i < K, dengan kapasitas INF (tujuan)
  • (a, i) ke (b, (i+1) mod K) untuk tiap a, b edge di input dan 0 <= i < K dengan kapasitas 1 (edge per satuan waktu modulo K)
Tinggal cari max flow dari graf tersebut. Karena banyak jawaban maksimum K ya.. O(K * BFS) = O(K2 M).

Anw, pas chat sama Ammar ternyata ada masalah wording di soal ini.

"These robots can be programmed, but their behavior on each product is deterministic, depending only on the producer which produces the respective product. ".

Ini bisa dipahami kalau untuk tiap produk, di setiap persimpangan gerakannya deterministik, jadi sebenarnya nggak bisa ada cycle (graf yang tadi mungkin ada cycle, cuma waktunya beda). Karena aku bacanya kecepetan, aku nggak nyadar ada kalimat itu. Dan kayaknya emang intended dari pembuat soal nggak kayak gitu. Jadi kasihan sama yang nggak ngerjain gara-gara mikir begitu :<

G - Rectangular City (post-contest)

Kalo gak salah pas kontes aku skip gara-gara salah ngerti soal. Pas nyoba upsolve, salah ngerti lagi :/ Btw, karena samplenya begitu, sekedar mengingatkan bahwa walaupun N event itu bentuknya persegi panjang, K titik yang diambil gak harus ngebentuk persegi panjang (sample nunjukin persegi semua).

Misal intersection dari N event itu kita nyatakan sebagai (r1, r2, c1, c2) dengan r1 <= r2 dan c1 <= c2. Kita akan pandang permasalahan r dan c ini terpisah, karena solusi permasalahan ini bisa dipakai di keduanya.

Sekarang kita fokus untuk r. Ada berapa banyak cara bikin N event, sehingga intersectionnya punya batas row (r1, r2)?

  • Ada r1N - (r1-1)N cara nentuin batas atas N event supaya batas atas intersectionnya r1. r1N artinya banyak cara yang intersectionnya <= r1, sedangkan (r1-1)N yang < r1. Kalo dikurangi jadinya pas di r1 intersectionnya
  • Dengan cara serupa, ada (R-r2+1)N - (R-r2)N cara nentuin batas bawah N event supaya batas bawah intersectionnya r2.
  • Untuk banyak cara (r1, r2), kaliin aja dua nilai itu
Nah, kalo sudah, kita bisa hitung rows[X], yang mana rows[X] menyatakan banyak cara sehingga tinggi intersectionnya X. Tinggal brute force (r1, r2) yang mungkin, terus tambahin banyak caranya ke panjangnya. Dengan cara serupa, hitung cols[Y], dengan patokan (c1, c2).

Selanjutnya, bisa kita lihat kalau rows[X] * cols[Y] menyatakan banyak cara bikin N event yang intersectionnya punya ukuran tepat X * Y. Jawaban yang kita cari itu banyak cara bikin N event yang intersectionnya punya ukuran >= K. Dengan precompute iN untuk tiap i yang mungkin di awal, kompleksitas solusi ini O(max(R, C) log N + R2 + C2 + RC).

H - Sliding Blocks (post-contest)

Ini soal lain yang males kubaca :/ Pas kontes aku udah baca dan came up sama suatu solusi, tapi males ngoding. Pas chat sama Ammar ternyata solusinya bener :P

Intinya karena bentuk grafnya tree, kita bisa cari urutan masukin baloknya pake toposort. Bikin edge berdasarkan treenya, terus berdasarkan arah slidenya. Kalo ke atas, artinya kita harus masukin ini duluan sebelum balok terdekat di bawahnya. Kalo ke kiri, artinya harus lebih dulu berdasarkan kanan terdekatnya. Dst, dst.

Solusiku O(B log B) dan lumayan jorok, copas-copas di mana-mana. Oh well, yang penting nggak TLE :P


And that's all!

Aku nggak ngerjain E, dan setelah chat dengan Ammar, untung aku nggak ngerjain. Salah ngerti soal >.> Kayaknya hampir semua tim salah ngerti soal. Kayaknya pengertian soal yang Ammar jelasin (convert -> asterisk check -> convert -> asterisk check dst) lebih doable, cuma aku nggak terlalu minat buat nyobain.

Overall, kayaknya... regional yang ini nggak terlalu susah? Mayoritas soalnya medium. Cukup yakin kalo ngerjain bertiga bareng Degol sama Inigo juga bisa AC 10-11 gitu. Agak sayang ada masalah sama soal D sama K (Donkey Kong?). Tapi ya, kontesnya cukup menarik. Menurutku Soal H sama I lumayan menarik. Terima kasih untuk panitia yang bikin mirror hehe. Semoga kalo ada ICPC Singapore lagi (mungkin beberapa tahun lagi? ada gap 3 tahun dari ICPC Singapore terakhir) bisa lebih keren lagi ^^

Sabtu, 08 Desember 2018

ICPC Regional Hanoi 2018

Beberapa minggu setelah Regional Jakarta, timku berangkat ke Hanoi buat ikut ICPC Regional Hanoi. Alhamdulillah bisa dapat hasil yang baik :')

Pre-ICPC 2018

Ini nggak sepenuhnya terkait ICPC Regional Hanoi 2018, jadi mungkin aja di-skip.

Sejujurnya, aku gak berencana masuk tim inti UI (yang dikirim ke regional luar) tahun ini. Setelah 1 tahun yang sangat bikin stres (2017), aku udah pengen rehat dari CP-CPan. Mungkin masih ngerjain soal-soal, cuma aku udah gak terlalu kepengen ikut ICPC. Awalnya, rencanaku buat tahun 2018 mungkin bantuin Pak Denny terkait coaching, ikut ICPC Jakarta jadi tim hore, terus gak ngapa-ngapain dulu yang serius terkait CP.

Pengennya sih gitu.

Namun, Pak Denny beberapa kali nyaranin buat tetep ikut ICPC. Sementara itu, seleksi buat tim inti udah mulai, dan aku nggak ikut karena aku yang nyiapin soal-soal seleksinya. Berhubung aturan seleksi Pak Denny bisa masukin beberapa wildcard (orang-orang yang dirasa sesuai masuk tim inti tapi pas seleksi mungkin lagi bego atau ada masalah), aku mungkin aja diselipin ke tim inti. Akhirnya aku bilang ke Pak Denny kalo aku bakal mutusin ikut tim inti atau nggak setelah kontes seleksi terakhir.

Singkat cerita, akhirnya aku mutusin buat ikut. Untuk tim inti, aku diskusi sama Pak Denny terkait pembagian timnya (tanpa preferensi orang-orangnya, karena udah mepet batas pendaftaran INC :'( ). Aku milih untuk setim sama Degol dan Inigo, untuk alasan yang mungkin kapan-kapan kuceritakan.

Oiya, kenapa nama timnya Supir Tayo? Awalnya aku ngasih 2 nama, IDA Pro (tools yang biasa kupake di CTF, IDA bisa jadi singkatan nama kami) sama Supir Tayo (lagi suka dengerin parodi Tayo). Akhirnya kami mutusin pake nama Supir Tayo, walaupun Inigo kayaknya gak tau kenapa aku ngasih nama itu. Yaudah, habis itu tiap minggu latian, dengan pace yang kurang lebih sama.

Day 0 - Keberangkatan

Ada 2 tim inti yang dikirim UI ke Hanoi, Supir Tayo sama YouR Lovely JatengPRiDe.

Kami berangkat cukup pagi, dari CGK jam 8.25. Artinya, paling lambat harus sampe bandara jam 6. Artinya lagi, aku harus dari Depok sekitar jam 4 kalo mau sampe dengan aman. Berhubung aku nge-kos di Kutek, dan aku gak tau gerbatama UI buka jam berapa, aku akhirnya mutusin buat nginep di Ristek dulu malam sebelumnya, terus nyeret koper ke Margonda dan naik taksi dari situ. Semalaman, aku mungkin cuma tidur sekitar 10 menitan karena masih nyiapin soal-soal buat Ristek Festival (dulu Pekan Ristek, tapi karena sudah tidak sepekan namanya diganti). Btw, Ristek Festival ini diadainnya di malam hari keberangkatan ke Hanoi, emang rada nekat ini semua persiapannya dadakan.

Setelah itu, nyeret koper ke Margonda, naik taksi, dan sampai di CGK. Udah ada Salman sama Yoga. Setelah yang lainnya datang (minus Degol, walaupun rumahnya sebelah bandara), kami masuk buat check in. Pak Denny ternyata berangkat sama anaknya, Linus. Habis check in, aku cek tempat money exchange, dan ternyata belum buka. Karena lapar, kami sarapan dulu.

Habis itu, Degol datang, lalu kami masuk ke ruang tunggu. Aku rencananya mau nuker duit di money exchange di ruang tunggu, tapi ternyata baru buka jam 8, padahal boarding juga sekitar jam segitu...

Ya, aku ke Vietnam tanpa bawa Dong (mata uang Vietnam) sepeser pun.

Kami transit di Singapura selama sekitar 4 jam. Setelah bisa dapat koneksi Wi-Fi (yang OTP-nya nunggu setahun), persiapan Ristek Festival masih kacau karena server-nya mati. Sementara aku beres-beresin terkait soal, Firman sama Norman bilang kalo lagi ada diskusi TC CPC dari masa-ke-masa. Jadinya ya.. cukup yakin kalo bakal aman, lol. Setelah beberapa jam, kami ke ruang tunggu, lalu terbang ke Vietnam.

Di Bandara
Sumber: Pak Denny

Setelah sampai dengan selamat, ngambilin koper, dan nuker duit, kami lalu berangkat ke hotelnya. Di perjalanan, Linus sama Inigo kayak ngobrol seru terkait sains, macem biologi, fisika, kimia. Cuma.. aku gak ngerti mereka ngomongin apaan :| Kayaknya dulu aku pas SMA pernah belajar beberapa yang mereka omongin, tapi tetep aja nggak ngerti :| Pas liat Pak Denny, mukanya juga kayaknya bingung. Yah seenggaknya yang gak ngerti nggak cuma aku xD

Habis sampai ke hotel, pembagian kamar. Aku sekamar sama Inigo di 502. Kami semua lalu jalan ke mall di depan buat cari makan. Ujung-ujungnya makan Pizza Hut sih :P Selesai makan, aku sama Degol liat-liat soal Educational Round CF yang lagi jalan. Aku diskusi soal E sama Degol, tapi ternyata aku salah ngerti soal Dx Terus aku baca soal G, kayaknya bisa pake Max Flow cuma aku gak terlalu mikirin. Pengennya pas balik nyoba ngoding terus submit.

Degol: "Gw ada ide soal E deh, kayaknya bener"
Ayaz: "Yaudah ntar submit aja"
Degol: "Lah ntar rating gw turun"

Habis itu kami balik ke hotel, aku ngoding G, sementara Degol ngirimin solusi E dia ke aku. Berhubung aku pasti out-of-contest, jadi ya.. aku submit aja :P Dua-duanya lolos.

Mandatory 404 joke
Sumber: Pak Denny
Oiya, malam itu juga Ristek Festival-nya beres. Hasilnya lumayan sesuai sama perkiraanku. Anyway, repository soal-soalnya bisa diakses di sini. Setelah bikin repository-nya jadi public, aku tidur karena udah lumayan capek.


Day 1 - Pembukaan + Practice Session

Untungnya besok paginya bisa bangun dan gak terlalu telat. Habis cek Cookie Clicker, dan sudah diajak sarapan, aku sama Inigo ke tempat sarapannya. Makanannya lumayan enak, suka banget dengan Croissant sama Pho (mi khas Vietnam)-nya. Selesai makan, aku balik ke kamarku.

Registrasinya dilakuin di hotelnya. Pak Denny ngurus registrasi, terus nganterin name tag sama kaos ke kamar masing-masing. Welp, dapet kaos warna putih. Habis itu, kami ke bawah buat foto tim. Setelah foto tim, Pak Denny ngajak jalan kalo misalnya mau cari oleh-oleh kopi. Berhubung aku gak punya duit dan emang nggak berniat beli kopi, aku mutusin buat istirahat di kamar aja.

Siangnya, kami berangkat ke PTIT (tempat lombanya). Oiya, di Vietnam ini helm-nya rada lucu, bentuknya kayak topi. Kata Pak Denny sih awalnya orang-orang gak pake helm, terus pas disuruh pake helm, kecelakaannya malah nambah gara-gara susah nengok. Makanya bentuknya jadi kayak gitu. Kenapa aku bicarain masalah helm dan kecelakaan? Karena baru sehari di Vietnam, udah ada pemandangan orang jatuh dari motor...

Sesampainya di PTIT, kami diantar LO kami ke KFC dulu karena pada kelaparan. Tentunya, untuk beli KFC, aku harus ngutang dulu. Habis beli KFC, kami balik ke PTIT buat pembukaannya. Pas pembukaan, ada ditayangin video yang isinya interview ke beberapa tim di pagi hari tadi. Dari Binus, ada yang menutup dengan bilang "Let's kill each other". Satu aula pada ketawa.

Videonya lanjut, terus ada foto-foto tim.
Ada tim-tim yang di namanya ada "Police", "Military", dll.
Ahh.. mungkin tim Binus nggak bisa balik dengan utuh.

Sliver
Digantikan TLX, TLC sekarang sponsorin ICPC
Setelah pembukaan (ada lagu, Hello Vietnam? Lumayan catchy), ada briefing dari SC. Lumayan standar lah, nggak ada yang terlalu signifikan, selain bakal ada soal interaktif :O Soal interaktif ini lumayan jarang ada di ICPC, dan aku sendiri gak terlalu bisa interaktif :"

Go Green
Habis itu rada nggak jelas, nunggu dipanggil masuk ke ruang kontesnya untuk practice session. Di luar ada denah, dan Supir Tayo.. di nomor 120 dari sekitar 125 tim. Welp. Sisi positifnya, duduknya paling belakang, dan leluasa buat gerak-gerak. Dan dipanggil masuknya satu-satu, jadi kami terakhiran banget baru masuk. Sambil nunggu, ngobrol-ngobrol sama tim Binus (Rapel dkk). Nah, pas dipanggil itu aku bingung, ini kok aku gak jelas ya denger yang manggil itu bilang apa? Tapi kenapa tim-tim dari Vietnam pada ngerti? Ternyata, kalo tim dari Vietnam bakal dipanggil pake bahasa Vietnam (angkanya pake bahasa Vietnam), sementara kalo tim luar baru pake bahasa Inggris. Hue.

Habis masuk, ngecek komputer. Keyboard-nya rada nggak enak, tombol enter-nya kecil :/ Selain itu nggak terlalu masalah sih. OS-nya Ubuntu, yey :D Habis nyoba-nyoba, ternyata practice session udah mau mulai. Pas mulai, liat-liat soalnya.. oh soal VNC kemarin. Kami cuma nyoba-nyoba ngoding aja, cuma nggak terlalu serius. Yang penting bertiga udah pernah ngerasain keyboard sama mouse-nya. Nah, ini practice session rada gak jelas kalo menurutku.. Dari sekitar 3 jam practice, setelah 2 jam kayak separo lebih tim udah ilang :| Pulang? Entahlah. Ko FJ datengin tempatku, nanya compile di tempatku berapa lama. Cuma sekitar 1 detik. Terus Ko FJ bilang kalo tempatnya Rapel bisa lama banget, beberapa detik. Aku terus ke tempatnya Rapel, ternyata beneran. Kalo mo cepet gak boleh #include <bits/stdc++.h>, tiap header nambah waktu compile secara lumayan signifikan. Kalo liat klarifikasi, kayaknya tiap tim punya masalah yang beda-beda.

Oiya, kayak biasa habis practice kami harus ninggalin barang-barang yang mau dibawa ke kontes besoknya. Untungnya Degol print citsit dua biji, soalnya serem kalo besok gak dikasih coretan (gak ada indikasi bakal dikasih :|). Jadinya, dua citsit itu kami tinggalin, biar kalo besok gak ada coretan pun kami bisa nyoret-nyoret di salah satu citsit.

Post practice session
Sumber: Pak Denny
Habis practice session itu, ada makan malam. Selama perjalanan ke tempat makan malam, aku merenung beberapa hal, malah bikin mood-ku buruk sendiri Sampai ke tempatnya, terus mulai makan. Ikan, telur, tahu, sama jus jeruknya enak, tapi ayamnya jahannam. Alot parah. Kenyang, malam itu balik ke hotel dengan senang. Aku nyoba review beberapa topik, habis itu tidur.

Day 2 - Kontes

Paginya, akhirnya alarmku berguna untuk bangun pagi. Kudu bangun pagi karena bakal cabut ke tempat kontesnya jam 7, jadi sarapan harus jam 6-an. Habis mandi, masih sempet nonton Youtube dulu :P Terus sarapan deh. Setelah sarapan, berangkat ke tempat kontesnya.

Pas sampai ke tempat kontes, kudu nitip tas terlebih dahulu. Sambil nunggu antrean, aku ke toilet, untuk mendapati kalo ya.. aku nggak bisa BAB di toiletnya. Welp.

Setelah nitip tas, kami lalu masuk ke ruang kontesnya. Kontesnya masih lama, dan nggak jelas ini apa aja yang boleh dilakuin. Tim depan kami ngetik template mereka. Funny, I remember I've seen that template before on CF (dan ternyata emang itu orang yang sama di CF). Sementara itu, kami nggak ada template, dan lumayan nganggur sebelum kontesnya mulai. Paling cuma setup gedit doang. Habis itu tidur-tiduran. Kayak biasa, bilang "udah nyantai aja, gak usah terlalu serius". Oiya, ternyata ada kertas coretan, pake kertas-kertas yang agak aneh.

Tik. Tok. Tik. Tok. Kontes dimulai!

Degol ngurus login, terus aku sama Inigo bagi-bagi soal. Kayak biasa, Degol A-D, Inigo E-H, aku I-L.

I: Paling nggak separo '1', artinya paling banyak 215 pattern. Bisa pake DP di Aho-Corasick, kudu cek ML sama banyak operasi
J: Hmm.. rada panjang, skip dulu
K: Cek ada apa nggak segitiga sehingga semua titik ada di border segitiganya. Geometri, ntar kasih ke Degol sama Inigo
L: Itung-itungan kompleksitas banget. Intinya sort string di dictionary, terus kerjain offline untuk tiap batas kiri. Cari tiap kata bisa muncul paling awal di mana. Reduce ke nyari elemen ke-k pake BIT.

Degol mulai ngoding A. Setelah rada lama.. "Yaz ini gak segampang yang gw kira". Lol, entah kenapa udah kebiasa. Inigo udah ngoding di kertas buat soal H, terus dia pake komputernya. Setelah beberapa menit, H - Hydra's Heads Accepted! Cek scoreboard, yang udah AC masih dikit banget, padahal udah > 10 menit :O

Aku terus pinjem komputernya buat ngitung banyak operasi soal I sama ML. Hmm, 50 * 215  * 30, 1 GB cukup lah ya. Aku terus ngoding soal I. Ada ngebug beberapa kali :/ Setelah lolos sample, submit. I - Insider's Identity Accepted! Yey first solve \ :v / Pada saat ini kami ada di rank 1 :O

Degol terus ngerjain soal C, sementara aku ngoret-ngoret buat soal L. Kayaknya BFS aja, tapi ngebug. Aku jadinya bantu debug-debug dulu. Lolos sample, tapi Degol gak yakin. Ternyata masih salah. Debug lagi, akhirnya bener setelah gak keputer-puter masalah baris sama kolom. Submit, C - Conquest Campaign Accepted! Kembali ke atas lagi :O

Degol sama Inigo terus diskusi soal D, sementara aku ngoding soal L. Ngodingnya rada ribet, ada beberapa bagian yang harus dibikin. Setelah lolos sample, aku cek codingan lagi. Ada bagian yang return string, tapi setelah kupikir lagi, kayaknya lebih aman balikin indeks aja. Setelah modifikasi dikit, submit, dapet Wrong Answer.

Oke, ini aneh. Aku cek lagi, kayaknya udah gak ada yang salah. Satu-satunya yang aku rada ragu cuma bagian nyari elemen ke-k nya, yang O(log N) dengan observasi macem sparse table. Karena gak ngeliat ada yang aneh lagi, aku ganti bagian itu, jadinya O(log2 N) pake binary search + query BIT-nya. Submit, WA lagi :| Mau misuhin panitia tapi orang Vietnam jago-jago :|

Pada tahap ini aku rada stres, terus ternyata ada pengumuman.

"Kalau string ke-k nya lebih dari 10 karakter, keluarin 10 karakter pertama saja"

asdfghjkl. Salah juga sih aku, baru nyadar kalo naif gitu outputnya bisa sampe 15 * 107 karakter. Setelah modifikasi, aku nyoba dikit buat yang karakternya lebih dari 10. Udah oke. Submit, nah akhirrnya verdict-nya lama. Setelah beberapa saat, L - Lazy Learner Accepted! Kembalikan 30 menitku :""

Degol bilang soal D mungkin ada pake sqrt-sqrt gitu, kalo ngeliat batas interaksinya yang aneh. Aku cari-cari soal lagi. Aku baca soal G, bikin graf dengan banyak vertex dan edge paling banyak sekian supaya banyak shortest path-nya A. Hmm, ini bukannya gampang? Terus baru nyadar kalo cara gampangnya butuh 2 * log A vertex, jebol batasan, gak jadi gampang deh :/ Soal F kayaknya lucu, cuma brutal banget: Cari F[F[F[...F[N]...]]] mod P (F sebanyak K). Ini pasti pake Pisano Period, cuma aku gak tau cara nyarinya :| Aku minta dijelasin soal E ke Inigo, ribet parah soalnya.

Pas cek scoreboard, ada tim yang udah solve soal J. Degol terus jelasin soal J (padahal harusnya aku yang baca xD). Intinya buat graf dengan N vertex dan M edge, sehingga kalo orang jalan random ke vertex yang belom pernah dikunjungi sebelumnya, bakal selalu bisa jadi hamiltonian cycle. Nah, terus kami mikirnya grafnya harusnya bentuknya 1 cycle atau complete graph. Karena gak terlalu yakin, aku coba bikin generatornya dulu. Generatornya brute force grafnya, terus di-DP bitmask untuk ngecek. Pas nyoba N = 4 sama N = 5, kami cukup yakin kalo grafnya bentuknya cuma 2 itu. Submit, dapet Wrong Answer. Lho, lupa print "YES" kalo jawabannya complete graph. Habis benerin itu, submit lagi, Wrong Answer lagi.

Welp okay. Kami lalu nyoba N = 6. Terus kaget, karena ternyata ada yang pake 9 edge doang :O Pas digambar, ternyata itu grafnya  K3,3. Jadi kalo complete bipartite graph dengan banyak node sama juga bakalan bisa. Nah, pada tahap ini kami nyoba nyari ini bisa digeneralisir apa nggak (misal jadi tripartite gitu). Jadi kami nyoba run generator lagi, tapi gak nemu apa-apa sih.

Inigo nemu observasi soal D, terus Degol bantu verifikasi. Karena gak tau mau ngapain, aku mutusin untuk YOLO soal J aja, jadi cuma pake 3 graf yang udah ditemuin tadi. Submit, wew verdict-nya lama gak keluar-keluar :O Selang beberapa saat, J - Jurassic Jungle Accepted! :O dafuk. Sekarang AC 5, kayaknya pas itu masih memimpin. Ngecekin Jateng Pride, kayaknya masih nge-stuck :""

Inigo terus ngerjain soal D, selalu pake log 109 query aja. Idenya kayak binser gitu, cuma aku gak tau ngapain. Aku coba baca soal lain sambil Inigo ngoding D sambil dicek Degol. Ada bug simple, habis dibenerin, kami coba-coba kasus kami sendiri. Hmm, pada bener. Akhirnya mutusin buat submit aja. Wrong Answer.

Aku jadinya bantuin debug. Input sama interaksinya kuubah dikit jadi macem functional kalo pas pelatnas :P Jadinya cukup masukin N sama tempat-tempat sprinkle-nya, ntar dia bakal jalanin query-nya sendiri. Never know when your experience will come handy. Pas dicoba, paling banyak butuh 30 query nanya. Sama output, artinya 31 kali interaksi. Dan kalo cek constraint, kalo N = 2 harus paling banyak 30 kali interaksi :| Kalo kata Degol constraint aneh itu buat nyembunyiin hal ini doang. Nah, kami ngeliat kalo kami masih nanya pas L = R di binsernya, padahal gak butuh. Akhirnya.. ubah dikit binsernya, supaya gak nanya pas L = R. Oke, sekarang udah 30 kali interaksi. Benerin interaksi sama input lagi, terus submit. Nah, verdict-nya lama nih. Akhirnya, D - Divide Doughnut Accepted! Kalo gak salah ada tim lain yang juga AC 6, tapi penalty dikitan kami.

Cek scoreboard, yang mungkin dikerjain soal A atau B. Kami cek soal B. Ini intinya.. ngitung nimber untuk setiap bipartite graph dengan a dan b node. Ada tim yang cepet banget solvenya, jadi kami pikir harusnya bisa lah ngerjain ini. Degol nyobain nyari winning state sama nimber manual, cuma pusing. Jadinya ya.. daripada komputernya kosong, Degol nyoba ngoding generator untuk cari pola. Aku sambil mikir yang lain. Inigo bilang K harusnya convex hull, terus gak ada jawaban kalo sisinya lebih dari 6. Oke, masuk akal. Cuma kayaknya kudu bagi banyak kasus untuk sisi <= 6.

Degol pusing ngoding generatornya, jadi kugantiin. Pair programming sih ujung-ujungnya. Agak lama, tapi akhirnya bener. Setelah kejadian aneh pake STL map, kami jadinya nggak nyimpen nimber-nya di map, jadi plain rekursi aja. Terus aku baru mikir, ini kalo pengen pemain kedua yang menang bukannya jadi Misere Nim? Kasus winning state-nya aneh dong? Mana gak nyimpen di citsit. Terus Degol kayaknya bingung. Habis itu aku baru nyadar kalo aku yang bingung. Butuhnya bukan yang gak bisa jalan yang menang (Misere Nim), tapi pemain kedua yang menang (Nim biasa, tapi nimbernya 0). Oke, semua udah lurus kembali. Nah, pas nyoba-nyoba, dapat pola

  • Kalo (a + b) ganjil, ada 2a*b-1 graf yang nimbernya 1 dan 3
  • Kalo (a + b) genap, ada 2a*b-1 graf yang nimbernya 0 dan 2
Dafuk. Aku mikir ini kayaknya bisa dibuktiin, cuma karena udah terlihat bener, yaudah deh. Nah pas mau ngoding, aku lupa matiin generatornya. Terus walaupun gak pake map, aku lupa comment barisnya, jadi sebenarnya masih bikin entri di map, walaupun gak dipake. Dan ya.. komputernya tambah lama tambah pelan. Mau nge-hang. Aku terus panik CTRL+C, terus mutusin buat angkat tangan buat manggil panitia. Pas panitia teknisnya dateng, generatornya udah berhasil di-stop. Jadinya ya kami keliatan kayak orang bego gitu, ngejelasin masalah yang udah beres, sementara panitianya keliatan bingung. Mungkin mikir "ini anak kok bisa ikut sampe sini ya".

Nah, dengan pola tadi, aku ngoding DP-nya. Lumayan simple, tapi ngebug-ngebug. Submit, wogh gak langsung keluar WA. B - Bipartite Battle Accepted!

Aku terus ke toilet. Kayaknya udah kedua atau ketiga kalinya buat hari ini. Kaget, pas masuk ada 2 mbak-mbak. Tapi karena ada toilet berdirinya.. ya gak mungkin salah toilet artinya.

Pas balik, Inigo sama Degol diskusi soal A. Aku terus nanya soalnya. Intinya dikasih grid N * M, sama 4 petak B, C, G, U. Cari shortest path B -> C -> G yang gak lewatin U, dan semua petak di B -> C -> G unik. Solusi Inigo kayak ada beberapa kasus gitu. Aku mikir-mikir dikit, terus ke toilet lagi. Pas di toilet, mikir itu soal A bukannya kayak soal di TROC 3? Pas balik, aku bilang ke Inigo. Terus baru inget kalo jalannya gak mesti kanan-bawah doang, bisa kudu muter dulu Dx

Oiya, scoreboardnya udah frozen. Kami target nambah 1-2 soal lagi, untuk amanin posisi.

Mikir-mikir lagi, baru dapet ide buat Max Flow: Modelin jadi vertex capacity, source ke petak B sama G, C ke sink. Kalo bisa ngirim 2 flow, artinya ada cara. Terlihat benar, cuma gak yakin masalah shortest pathnya. Yah, YOLO aja deh. Terus baru nyadar, harus print jawabannya, dan kami gak ada yang tau cara nyari augmenting path-nya. Tapi yaudah, sambil ngoding pasti nemu caranya. Jadinya aku ngoding A, Degol sama Inigo diskusi soal K.

Nah, pas ngoding, baru kepikiran supaya jadi shortest path kudu Min Cost Max Flow. Okelah, cuma ganti BFS jadi SPFA. Ngoding-ngoding-ngoding, jadi Min Cost Max Flow. Aku pertama-tama cek dulu bener apa nggak hasilnya, bisa ngirim 2 flow apa nggak, dan kalo bisa cost-nya berapa. Pas masukin sample.. Lho gak berhenti-berhenti. Ternyata karena lupa reset graf setiap kali ganti test case Dx

Setelah reset graf, oke hasilnya terlihat benar. Sekarang sisa cara nyari augmenting path-nya.. Aku mikir buat pake back flow-nya aja. Jadi telusurin path yang punya back flow. Wew, idenya terlihat benar. Ngoding-ngoding jorok, akhirnya beres. Cobain sample, wah sama persis. Submit, Runtime Error! WA gak papa, tapi kalo RTE kemungkinan gak nemu augmenting path-nya Dx Aku terus nyoba bikin tc simple ukuran 5 * 5, cuma keluarnya malah aneh: Ada gerakan UD, ngapain bolak-balik?

Inigo sama Degol terus ngoding soal K, sementara aku nge-print soal A. Cek lagi, terlihat benar. Lalu aku baru nyadar kenapa RTE: Ada yang harusnya ukurannya 2 * N * N (2 * 100 * 100), aku tulis 2 * N (2 * 100) doang. Ya RTE lah, kurang gede Dx Walaupun itu pasti gak benerin percobaan sebelumnya (yang UD), aku coba submit aja. Nah, akhirnya WA.

Degol sama Inigo kayaknya pusing ngerjain soal K. di 10 menit terakhir, aku minta mereka nulis di kertas dulu, sementara aku debug soal A di komputer. Aku coba cetak edge-edge yang kubuat. Anehnya, ada bikin ke (0, -1)! :O Gimana cara bisa pindah ke indeks negatif? Usut lagi, ada kesalahan konyol dari awal:

for (int i = 0 ; i < n ; i++)
    for (int j = 0 ; j < m ; j++) {
        // code lain
        for (int k = 0 ; k < 4 ; k++) {
            int ii = i + dr[k];
            int jj = j + dc[k];
            if (ii >= 0 && ii < n && j >= 0 && j < m) {
                addEdge(getOut(i, j), getIn(ii, jj), 1)
            }
        }
    }
Gak persis pas kontes, cuma kurang lebih kodenya begitu. Dan inilah kenapa, ngasih nama variabel yang rada panjang itu gak masalah daripada ngebug bego begini...

Habis itu dibenerin, nyoba sample dan tc sederhana tadi, lolos semua! Oke, submit lagi. Akhirnya, running lumayan lama :O Dan A - Amazing Adventures Accepted! :') Sejam ngoding ginian, bug bego semua.. Yah, yang penting AC sebelum kontes selesai :"D

Oh, aku hampir teriak pas AC terus mukul Degol. Very relieved, I say. Panitia di belakang kami juga kayak langsung excited gitu pas kami AC A. Antara mereka penasaran scoreboardnya jadi kayak gimana, atau excited karena ada print-print-an baru.

Inigo sama Degol terus buru-buru lanjutin K, cuma kayaknya nggak sempet. Degol bilang dia ngira 1 tc per berkas, jadinya semua taruh di main, dan pas udah ketahuan YES atau NO malah bingung cara keluar dari loopnya gimana :P Makanya tetep taruh di fungsi lain, karma nge-joke "read, prepare, work". Jadinya kami liat-liat scoreboard aja. Dan kontes berakhir!

Submisi Supir Tayo
Sumber: Pak Denny

Selesai kontes, Pak Denny dateng. Ada diskusi sekilas mengenai soal A sama K. Habis itu kami diskusi hasil, katanya Waseda nambah 2 (jadi 8), Korea nggak nambah. Artinya kami mampus kalo gak nambah A. Aku cek scoreboard lagi, kalo itunganku gak salah dan Kattis gak boong, artinya kami kemungkinan besar peringkat 1 di Hanoi :O

Aku, Degol, Ucup, Salman, Yoga terus sholat dulu. Selesai kontes ada excursion, cuma kami kayaknya ketinggalan bus. Terus Supir Tayo diajakin foto.

Sumber: Pak Denny
How I Met Your Mother
Sumber: Pak Denny
 Setelah busnya datang, kami semua cabut ke tempat excursion. Excursion-nya ke tempat kerajinan keramik. Degol, Inigo, Pak Denny nyobain bikin keramik, aku nontonin aja. Jateng Pride pergi ke market, nyari yang bisa dibeli mungkin. Oiya, yang excursion cuma tim luar negeri aja, katanya yang tim Vietnam mungkin penutupan VNC-nya. Setelah dari tempat keramik, dibawa ke semacam kafe gitu. Pesanannya lumayan lama jadi, punyaku juga terancam gak dibikin. Untungnya setelah pembicaraan "politis", punyaku dibikin juga xD Aku gak terlalu ngerti excursion ini ngapain, kayaknya gak terlalu jelas. Setelah mau maghrib, semuanya cabut lagi ke PTIT buat penutupan.

Pas penutupan, untungnya semua tamunya ngomongnya gak panjang lebar, mungkin paham kalo semua orang udah capek xD Oiya, ada penampilan nyanyi lagu Vietnam, bareng sama video bola Vietnam lawan negara lain. Pas gol semua tepuk tangan xD Terus disetel juga video pas lomba. Btw, di acara ini ada 2 MC, satu bahasa Vietnam, satunya lagi bahasa Inggris. Yang Vietnam ngomong duluan. Terus kalo diminta tepuk tangan ya.. kita yang gak ngerti bahasa Vietnam bingung kenapa orang-orang pada tepuk tangan, setelah MC bahasa Inggris baru ngeh kenapa pada tepuk tangan.

Sudah dibenerin, lol
Akhirnya, pengumuman juara! Awalnya udah gak minat karena pake google slides, tapi ternyata ujung-ujungnya pake resolver. Panitianya gak kuat nge-rap kayak Irvin :") Tapi hasil resolver ini juga lumayan bosenin, secara cuma ada 2 soal bonus (C sama H), sisanya rada brutal semua. Sampe akhirnya sisa top 12. Udah tahu kalo kemungkinan besar peringkat 1, dan ya.. di resolver sisa 1 pending run, A Supir Tayo. Dan Accepted, membawa kami ke peringkat 1 :")

Pas pembagian medali emas, aku udah siap-siap maju, tapi ternyata 2-4 dulu. Baru Champion disuruh maju. Pas maju, bapak-bapaknya bawa piala terus nanya, "who is the leader here?". Semua nunjuk aku :' Terus aku nerima piala, bapak-bapak tadi lalu nyuruh angkat pialanya. Well, this feels weird. Nggak biasa, aneh banget. Malah takut gak sengaja jatuhin pialanya.

Sumber: Pak Denny
Setelah itu lanjut penutupan, ada diminta interview dulu. Aku udah ngasal sih ngomongnya. Terus lanjut ke Gala Dinner. Kayak di Indonesia lah.. liar kalo ada makanan banyak dan gratis. Aku udah rada males, terus Rapel ngajak ke KFC. Jadinya Aku sama Degol (kami berdua ngutang ke Inigo supaya bisa beli KFC) dan teman-teman Binus jalan ke KFC buat makan. Setelah makan, balik lagi ke PTIT, untuk pulang ke hotel.

Day 3 - Kepulangan

Besoknya kami pulang tanpa Pak Denny sama Linus, karena memang Pak Denny sama Linus stay beberapa hari lagi. Untungnya sih gak ada masalah selama perjalanan pulang xD Sampai di Indo tengah malam, sampe kosan sekitar jam 2 pagi. Teringat harus nyuci di pagi hari, akhirnya tidur.

Aftermath

Bener-bener gak ngira kalo hasilnya kayak begini. Kinda glad that I decided to compete in ICPC again this year. Kalo kata Pak Denny, ini pertama kalinya UI menang di Regional. Nama kami artinya bakal ada di sejarah :P Oiya, ini juga berarti UI bakal lolos ke WF 2019 di Porto, Portugal. Welp, artinya kudu latian lagi.

Terima kasih untuk panitia yang sudah menyelenggarakan lomba yang bagus. Mungkin kebanyakan konstruktif sih tapi :''' Secara pribadi tertarik ngerjain F sama G, mungkin nanti kapan-kapan nyobain G. I just spent the entire day trying to solve F ;_; Thankfully now I got AC :'D Update: Solved G as well, now I feel stupid for not thinking this problem thoroughly during the contest :|

Buat WF 2019, semoga seenggaknya UI hasilnya bisa lebih bagus dari sebelumnya (sejauh ini joint-34, pas 2017). Semoga tahun depan juga dari UI bisa lolos ke WF lagi, biar Pak Denny 5 kali bawa tim UI ke WF, hehe.

Selasa, 04 Desember 2018

ICPC Regional Jakarta 2018

Udah tahu aslinya mau nulis kayak gimana, cuma entah kenapa numbuhin niatnya susah >.< Karena udah lewat sekitar sebulan, mungkin ada beberapa yang kurang akurat, maapkeun >.<

Jadi ya.. sesuai judulnya blog ini bakal bicarain tentang ICPC Regional Jakarta 2018 kemarin. Aku ikut dalam tim Supir Tayo, sama Inigo dan Degol. Dengan strategi "tanpa-strategi", kenekatan, dan hoki, kami kemarin bisa perform yang menurutku lumayan bagus di ICPC Regional Jakarta 2018. Biar gak pake lama, langsung ke acaranya aja.

Day 1 - Practice Session


Berhubung tidak ada demo seperti pas 2016 (yey), jadinya ICPC Reg. Jakarta tahun ini bisa berjalan sebagaimana mestinya. Di hari pertama bakal ada pembukaan sama pemanasan. Malam sebelumnya, entah kenapa aku susah tidur, jadinya sekalian nunggu sampe tengah malam buat nonton To Aru. Untungnya bisa bangun pagi buat berangkat dari Fasilkom rame-rame, sekitar jam 6.30 cabut dari Fasilkom. Di jalan aku sama Anab main Rayman Legends, Alhamdulillah gak muntah-muntah karena motion sickness. Perjalanan ke Binus-nya lumayan lancar.

Sesampainya di sana, dijemput sama LO-LOnya. LO kami sama tim Stoqi biasa dipanggilnya Doski, untungnya orangnya lumayan friendly untuk orang-orang pendiam macam kami. registrasi (yang sudah modern pakai QR-Code) terus ganti baju. Bajunya ijo, terus di bajunya kayak ada maskotnya. Setelahnya, kami ngantre buat foto tim. For the sake of the joke, aku sama Degol masing-masing udah beli 1 boneka tayo. Awalnya Degol mau beli yang warna ijo, cuma habis, jadinya dia beli yang warna biru kayak punyaku. Di fotonya maksudku biar keliatan kayak nyetir, cuma kayaknya keliatan rada aneh.

Supir Tayo, siap nabrak
Sumber: laman ICPC Regional Jakarta
Habis itu sarapan, sekalian ngobrol-ngobrol sama beberapa orang. Lumyan seru ngobrol-ngobrol sama Ammar, Pak Auzi, dsb. Mumpung ada Prabowo juga, sekalian foto #Prabayar.
#Prabayar dan timsesnya yang dikirim ke Yangon
Setelah sarapan, ada 
  • Pembukaan (yang aku gak terlalu perhatiin), 
  • Talk dari Traveloka (yang aku malah galau enaknya merhatiin apa main), 
  • Ngenalin tim-tim yang ikut (dih, Ayas)
  • Briefing dari Irvin (tentu saja tidak diperhatikan) 
Kinda unrelated, but I think I need to explain the whole "Ayas" fiasco, berhubung kayaknya banyak yang salah nangkap. Kalau nanya yang pertama kali bikin nama "Semoga Ayas Juara" (Firman), dia pasti bilangnya "Ayas" itu "Saya" dibalik, dan gak ada hubungannya dengan "Ayaz" (yang dibaca seperti "Ayas"). Walaupun aku gak terlalu percaya, tapi aku udah terlalu malas untuk ngurusin dan akhirnya percaya-percaya aja. Jadi, kalau ada yang merasa tertipu, tolong marahnya ke Firman aja ya. Kalo dari sudut pandangku, sekalipun aku (menganggap diriku) percaya, aku tetap risih ngeliat tulisan "Ayas", karena orang biasa salah nulis namaku jadi Ayas, and I don't like it (Salah satu alasan kenapa aku prefer dipanggil ayaze, simply karena "z"-nya tetep dibaca sebagai "z".) Anjir satu paragraf cuma bahas "Ayas".

Habis acara-acara itu, aku sama Anab beli beberapa buku CP 3 untuk keperluan Ristek. Setelahnya, kami pergi ke tempat makan buat makan siang. Btw, emang ICPC Reg. Jakarta ini acara penggemukan pesertanya kok. Habis makan-makan, sholat, dan ngobrol-ngobrol, akhirnya masuk ke sesi practice session. Practice session pakai soal-soal tahun lalu yang gak terlalu susah, jadi selesainya gak terlalu lama. Yang aku cek awalnya klarifikasi, kalo gak salah semacam:

"Tolong balas klarifikasi ini dengan "Hei Tayo" :')"

Terus panitianya bales klarifikasi itu dengan lirik opening Tayo dalam bahasa Indonesia. Mantap. Padahal maksudku cuma pengen dibales "Hei Tayo" doang :")

Aku sama Degol udah males ngecekin TL dan stack size, sementara Inigo memutuskan tidur. Karena waktunya masih lama, aku sama Degol jadinya cari apapun yang bisa dimainin di komputer lab Binus. Akhirnya kami mainin aplikasi kamusnya, buat cari kata-kata kotor. Ajaibnya ada beberapa kata kotor di dalam kamusnya. Oiya, boneka Tayo yang kami tinggal buat besoknya cuma punya Degol, soalnya kalo dua-duanya di workstation jadinya kepenuhan. Punyaku kubawa pulang buat kupake tidur juga.

Selesai practice session, yang dari UI balik ke UI. Macetnya lumayan lama, nyampenya jadi rada lama. Habis sampai UI, jalan dikit ke kosan, terus istirahat~

Day 2 - Contest Day


Lagi-lagi kudu bangun pagi buat berangkat, untungnya gak sepagi hari pertama. Perjalanan juga lumayan lancar, di jalan main Rayman lagi. Pas sampe di Binus, entah kenapa aku gak terlalu nafsu makan. Jadinya aku cuma makan dikit aja, padahal masih belum pengen diet.

Habis itu, kami mobilisasi ke ruang kontesnya. Kontesnya sendiri masih lama, sekitar 30 menitan lagi. Aku jadinya tidur-tiduran pake boneka Tayo yang kami tinggalin. Deket-deket waktu kontesnya, Degol hapalin username sama password akunnya, katanya sih biar cepet kalo perlu masukin lagi. Oiya, Degol ditaruh sebagai first coder karena biasanya ngodingnya cepet (tapi belom tentu bener). Sebelum kontes, aku bilang "udah nyantai aja", padahal pasti pas kontes bakalan gak nyantai.

Tik. Tok. Tik. Tok. Kontes dimulai! Btw, soal-soalnya bisa diakses di sini

Aku sama Inigo buka amplop terus bagi-bagi kertas soal. Soalnya ada 12, Degol baca A-D, Inigo E-H, aku I-L. Selang beberapa detik Degol bilang, "Yaz gw ngoding A".

Dan beberapa detik kemudian, Degol bilang "Yaz A WA". Sementara itu, dari soal-soal yang kubaca:

  • I: Oh simulasiin aja, harusnya gampang
  • J: Oh panjang stringnya kecil, bisa DP 15 * 215, cari untuk tiap substring dia bisa loncat ke mana habis diurutin
  • K: Konstruktif, kayaknya greedy-greedy lucu
  • L: Baca sekilas, kayaknya gampang
Berhubung gak ada yang pake komputer, aku jadinya ngoding I. Submit, WA. Sial, ternyata ada ngebug off-by-one :' Habis dibenerin, submit lagi, I - Lie Detector Accepted!

Habis itu aku nanya Degol soal A kenapa WA. Inti soal A kan dikasih binary string S, cari string T dengan panjang sama yang edit distance-nya >= |S| / 2. Degol cuma greedy bitnya di-flip, padahal kalo "010101..." bakalan edit distance-nya 2 dengan cara itu. Terus aku minta dia coba cari-cari pola lain. Pas liat scoreboard, Jateng Pride udah AC soal L. Jadinya aku coba ngerjain soal L.

Inti soal L simple sih, sebisa mungkin habisin MSB ke-2, dan selama masih > K, hapus 0-nya. Sederhana tapi entah kenapa aku rada awkward ngodingnya. Akhirnya setelah ngebug-ngebug, L - Binary String Accepted! Habis itu, Degol ternyata udah pindah ke soal D. Sambil Degol ngerjain D, aku ngoret-ngoret soal J. Pas Degol submit, WA. Habis itu diskusi sama Inigo, benerin WA lagi. Ketemu 1 corner case lagi, dan akhirnya D - Icy Land Accepted!

Habis itu aku ngoding soal J. Untungnya gak terlalu ada masalah. Submit, dan J - Future Generation Accepted! Ini ngelempar tim kami yang di awal-awal rada di bawah jadi ke atas. Pas cek scoreboard,

Ayaz: "Cuy ini cuma kita cuy tim di atas yang belom AC soal A"
Degol: "Gw gak tau lagi cuy itu soal diapain"

Sementara itu, Inigo udah selesai ngoding F di kertas dan nyoba implementasi. Aku sama Degol lalu nyoba-nyoba ngide buat soal A. Cuma kami ngerjain A ini lumayan kacau; Aku salah cara ngitung edit distance (kalo gak salah ada pake LCS gitu), nyoba modelin DP, yang pas di-coding sambil nggusur Inigo baru nyadar DP-nya ngawur. Terus juga nyoba nge-random, ngarep peluangnya gede, auto gagal. Ini sampe bikin A.cpp, A2.cpp, A3.cpp. Inigo lanjut ngoding F lagi.

Aku sama Degol terus nyoba cari pola sama lemma-lemma buat A. Intinya, kalo ada yang karakternya muncul lebih dari separo, cukup bikin string yang isinya kebalikannya doang. Yang masalah kan cuma kalo kemunculan 0 sama 1 sama. Kami nyoba cari beberapa pola, gagal semua. Berhubung Inigo F-nya ngebug, aku jadinya coba bikin brute force buat A. Hasilnya, ada beberapa pola yang lumayan bagus hasilnya: "01111...", "1111...0", "10000...", "0000...1". Kesel, akhirnya aku sama Degol putusin buat cobain aja di antara keempat kasus itu yang valid yang mana pakai DP (yang sekarang sudah bener). Submit. Wew, akhirnya A - Edit Distance Accepted! :"""

Kami liat scoreboard, terus kayaknya soal H paling doable. Sementara itu, F Inigo ngebug. Sampe sekarang aku masih gak terlalu ngerti solusi Inigo kayak gimana buat F; Kalo gak salah ada binser sama Segment Tree-nya. Aku coba bantu debug, nemu kalo segment tree-nya ngebug. Habis itu ada bug-bug lagi. Habis dibenerin, terlihat benar. Submit, dapet WA.

Sementara Inigo nyoba-nyoba, aku sama Degol nyoba ngerjain soal H. Aku ternyata salah ngerti soal H, disuruh ganti elemen 0-nya jadi -1 atau 1, kukira bisa dari -N sampai N :""" Inti soalnya sih cuma ganti tiap elemen 0, supaya semua syarat dalam bentuk "subarray L sampe R jumlahnya harus >= X" terpenuhi, dan hasilnya leksiko terkecil. Kami nemu solusi yang intinya asumsikan semua 0 awalnya nilainya 1, lalu dari kiri ke kanan. coba ganti jadi -1 kalo memungkinkan. Memungkinkan itu artinya misal kita ganti jadi -1, dengan sisanya masih 1 semua, syarat-syarat itu masih terpenuhi. Degol bilang mungkin bisa pake segment tree, tapi aku ogah ngoding segment tree. Ujung-ujungnya untung bisa pake prefix sum sama set doang. Ini ngerjainnya literally pair programming: Aku ngoding Degol liatin sama bantu debug. Setelah lewat beberapa bug, soal H - Lexical Sign Sequence Accepted!

Inigo lanjut debug F. Degol baca soal G, aku baca soal C. Hmm, rasanya dulu pernah ngerjain soal mirip C ini untuk angkanya biner di SPOJ, cuma lupa gimana. Seingatku bisa dikerjain greedy bego gitu, cuma aku udah lupa greedy bego-nya gimana.

Habis itu, aku nanya soal G kayak gimana. Degol jelasin, intinya cari K minimum supaya ada urutan nambah edge yang bikin grafnya jadi complete. Pas baca sama dijelasin, "lah ini bukannya mirip soal yang gw kasih pas seleksi tim inti ya? Macem graph transitivity?" Yea, harusnya baca semua soal lebih dini.

Tapi walaupun aku bilang gitu, aku belom tau juga sih solusinya gimana. Aku mikirnya bisa dibinser, terus dalamnya ada pq-pq gitu buat cari edge-edge mana yang jadi aktif. Setelah itu, cek di akhir apakah semua edge jadi aktif. O(N3 log2 N), berat banget. Cuma daripada komputernya gak dipake ngoding (Inigo debug di kertas), aku jadinya nyobain aja. Pas ngoding, baru nyadar kalo gak perlu pq, cuma perlu queue doang. Jadinya O(N3 log N). Aku ngoding ngebug-ngebug, gara-gara berubah konvensi dalam solusi sendiri beberapa kali. Akhirnya lolos sample. Submit, WA. Kampret. Kalo TLE gak masalah, kok ini WA.

Inigo diskusi sama Degol buat benerin F, terus nyoba-nyoba lagi. Submit-submit, WA juga. Terus mereka nyadar kalo dari awal tuh udah salah buat sample, ada yang jebol batasan :") Aku nyoba debug G di kertas sama kadang nyobain di komputer. Duh, rasanya gak ada yang salah. Pas nyobain beberapa kasus bikinan sendiri, baru nyadar kalo ini soal jahannam: Jawabannya itu bisa sampe 2N-3, bukan cuma N. Misalnya kalo grafnya hampir complete gitu, tapi ada satu edge ilang. Jadinya aku ganti batas di binsernya, karena takut jadi 0 sampai 3N. Submit lagi, dan G - Go Make It Complete Accepted! 2 menit sebelum freeze :""

Degol sama Inigo terus debug soal F. Selang 10 menit dari soal G, F - Popping Balloons Accepted! Ini jadi keinget Zamil, Inigo baru ngerjain satu soal ini aja dari awal kontes :"" Berhubung waktu masih lama, kami cukup yakin bisa nambah seenggaknya satu soal lagi. Antara soal C sama K. Yang soal C:

Ayaz: "Gol sumpah gw inget dulu pernah ngasih soal ini di Pelatnas dah"
Degol: "Iya gw inget dulu lu pernah ngasih solusinya gampang banget"

Tentu saja kami berdua nggak ada yang inget solusi gampangnya kayak gimana. Yang kami cukup percaya, solusinya selalu punya panjang N+K-1. Karena soal SPOJ yang kami bicarakan itu biner, kami nyoba cari solusi bego buat biner. Akhirnya, kami mutusin untuk coba cari greedy bego: Mulai dari suatu biner ukuran N, lalu coba tambahin 0 kalo misalnya substring ukuran N baru itu belum pernah nongol, dan jika sudah, maka 1. Aku coba bikinin brute force (yang tentunya ngebug) buat cari polanya. Turns out, kalo kami pakai "111...11" (sepanjang N) dulu di awal, maka solusi barusan bakal munculin semua pola biner ukuran N.

Degol terus nyoba ngecek itu bisa digeneralisir nggak buat yang basisnya lebih dari 2, dalam hal ini dia nyoba basis 3. Ternyata bisa! Artinya, mungkin bisa jalanin greedy tadi untuk basis apapun, terus simpen rolling hash untuk tiap substring ukuran N. Aku terus coba ngoding. Banyak bug bego yang terjadi: salah nge-hash lah, salah karakter yang kudu di-hash lah, dll. Sampe akhirnya, sample lolos, tc buatan kami (yang harus munculin semua kemungkinan string ukuran N) lolos, dll. Kami lalu coba submit. WA. Eek. Oh, aku lupa benerin basis sama mod hash-nya gara-gara tadi masih debug. Benerin, submit. WA lagi. Eek kuda.

Iseng, aku nyoba-nyoba beberapa kasus gede. Pas nyoba "100000 5 100000" sama 5 angka ngawur, assert-ku gagal. Ternyata ada collision. Kenapa yakin collision? Karena kalo 5-nya diganti dari 1-10 selain 5 bisa semua. Akhirnya, dalam beberapa menit... Aku tambahin hash-nya jadi double hash. Code-nya bikin eneg. Submit lagi, dan C - Smart Thief Accepted! :O

Aku lalu ke toilet dulu. Balik-balik, sisa sekitar 20 menitan, kami coba mikirin soal K. Inigo sama Degol terus modelin soalnya jadi begini: Anggep tiap edge kita assign mau ujungnya kepake di U atau V. Misal U ke-assign cnt[U] edge. Artinya, jawaban kita bakal nambah cnt[U] / 2, buletin ke bawah.

Nah ini kayaknya modelnya bener. Habis itu aku mikir + bilang kalo ini artinya kita pengen minimize banyak node yang cnt[]-nya ganjil, soalnya sayang satu edge. Nah, mikirnya kalo misalnya ada edge yang hubungin 2 node yang paritas cnt-nya ganjil, balik aja edge-nya. Cuma ini aja kayaknya gak cukup. Habis itu baru kepikiran: Misal ada path p1 -> p2 -> ... -> pk. Kalo kita flip semua edge dari path itu, maka paritas dari p2 sampai p(k-1) tetap, sementara p1 sama pk jadi kebalik. Nah, bisa pake ini buat minimize node yang cnt-nya ganjil.

Hanya saja.. waktunya sisa sekitar 10 menitan, terus kami masih gatau cara ngoding yang flip path itu gimana. Jadinya yaudah, sisa beberapa menit itu nyoba-nyoba dikit cuma gak serius, sama nontonin scoreboard. Aku baru nyadar kalo aku masih belum tau sepenuhnya soal B sama E ngapain (iya, aku bego). Soal B aku baca sekilas doang, query-query gitu, tapi gak yakin bisa ngerjain. Aku terus nanya ke Degol sama Inigo.

Inigo: "B intinya bisa cabut pasang di tree gitu"
Aayaz: "OOOH INPUTNYA TREE?? TADI KUKIRA GENERAL GRAPH"

Degol: "Lu mo gw jelasin soal E apa denger tag-nya dulu?"
Ayaz: "Tag-nya apa dah"
Degol: "Ada geometrinya"
Ayaz: "Oke skip"

Habis itu cuma nontonin scoreboard sama aku ngira-ngira peringkat berapa. Cukup optimis bisa antara rank 5-7, kalo hoki rank 5. Habis itu kontes beres. Ngobrol-ngobrol sama Prabowo tentang AC berapa, habis itu ada Pak Denny. Yaudah lapor kalo nambah 2. Terus Pak Denny bilang soal K katanya pernah ada di CF :O Kebetulan parah. Habis itu kami mobilisasi ke tempat makan, kali ini aku udah punya nafsu makan.

Habis makan-makan, Doski ngajak foto buat yang challenge Instagram. Yaudah kami foto, bareng tim Stoqi. Pas foto, diceritain kalo tim Korea (KAIST, yang leading parah) di hari sebelumnya banyak makan micin. Micin emang bisa bikin pintar.

Selanjutnya, balik ke auditorium buat penutupan sama pengumuman. Pas masih belum pengumuman, aku main Rayman lagi. Degol, Rakha, Anab main Mario Kart. Sampe akhirnya ditayangin video flashback, aku mulai merhatiin acaranya lagi. Terus ada contest review, yang mana Irvin ngasih brief solution dari kontes tadi. IMHO, aku lumayan seneng ada dikasih buklet solusi sama pembahasan singkat di kontes ini. Jadinya bisa belajar dari hal yang sebelumnya kita gak bisa.

Setelah pembahasan singkat, ada pengumuman hasil INC, yang sebenarnya hasilnya udah bisa dilihat dari sebulan sebelumnya:

  • Juara 1: Binus - Kth-D Hyperprism
  • Juara 2: UI - Supir Tayo
  • Juara 3: UI - YouR Lovely JatengPRiDe
Btw post-ku terkait INC bisa dilihat di sini. Pas maju, Inigo bilang "Ini Binus uang hadiahnya uang judi ya" :")) Konteksnya mereka AC soal K pake random, nggusur kami ke rank 2.

Tayo!
Sumber: laman ICPC Regional Jakarta
Setelah itu, mulai masuk ke pengumuman terkait ICPC-nya. Pertama-tama ada bagiin hadiah first solver. Kalo gak salah liat, dapet semacam tumbler atau mug. Terus tiap tim bisa dapet berkali-kali. Tim KAIST dapet banyak banget, kayaknya bisa bikin bisnis jualan mug ICPC Jakarta.

Nah, lanjut ke bagian utamanya: Resolver! Jadi kalo ICPC bisa macem simulasiin pas frozen, kalo ada AC jadi terbang-terbang gitu timnya. Btw ini Irvin harus diapresiasi karena nyebutin satu-satu nama timnya, dengan kecepatan yang hampir setara nge-rap :") Setelah melewati puluhan tim yang beterbangan, akhirnya masuk ke top 12. Ada saat-saat Supir Tayo diterbangin ke rank 2 pas ditunjukin AC 9, walaupun aku tahu itu gak mungkin bertahan lama :P

Mak pernah rank 2
Nah, yang jadi pertanyaan itu NTUSECURE sama map nambah apa nggak, soalnya cukup yakin CMP at least AC 9, earlybird AC 10, dan kami udah tahu 3Sophomores AC 10. Dan.. NTUSECURE sama map gak nambah! Jadinya Supir Tayo ada di rank 5, dapet medali perak sama penghargaan "Best National Team"

Silver Medalist
Sumber: laman ICPC Regional Jakarta
Untuk hadiah dari jadi Best National ada beberapa, seingatku: Mi Band 3, Power Bank, Speaker, sama Hard Disk. Lumayan :D

Habis itu masuk ke medali emas. Sesuai dugaan, earlybird AC 10, terus 3Sophomores juga AC 10, cuma kalah penalty. Nah, KAIST yang sebelum freeze udah AC 10, masih punya 2 pending run. Yang B.. AC! :O Satu-satunya AC B di kontes. Sebelum masuk ke soal E, Irvin nyebutin quote Bill Poucher yang kurang lebih, "ICPC itu pertandingan antara pembuat soal sama kontestan". Kemudian E KAIST... nggak AC! Artinya bisa dianggap pembuat soal yang menang ya :")


Top 12 ICPC Jakarta 2018

Setelah pengumuman medalis ICPC-nya, ada pengumuman medalis untuk top 12 dari Indonesia yang gak masuk top 12. Ada beberapa tim UI juga yang masuk di sini, yey. Selanjutnya, aku cabut buat sholat, dan pas balik-balik foto bareng tim UI. Selain itu, aku juga ikut foto tim Binus, yang entah kenapa kulakuin dari tahun lalu.

UI!
Sumber: laman ICPC Regional Jakarta
Binus!
Sumber: laman ICPC Regional Jakarta
Aliansi Supir!
Sumber: FB Bu Yen Lina
Setelah foto-foto, ngurus perkara duit-duitan ($$$), lanjut ke bawah buat makan-makan. Makan-makannya lumayan enak, aku ada ngambil beberapa kali. Setelah makan-makan dan ngobrol-ngobrol, akhirnya yang dari UI balik lagi ke Fasilkom. Bersiap untuk menghadapi kuliah di esok hari. Aku sendiri harus ngerjain paper DAA yang udah kutunda-tunda dari minggu lalunya Dx

Aftermath


Sejujurnya, nggak expect kalo hasilnya bisa kayak gini :"D Dari aku sendiri gak ada target apa-apa buat ICPC tahun ini, tapi mungkin juga karena gak mikir apa-apa malah performanya jadi lebih baik. Selain itu, dari kontes ini juga jadi sadar lagi kalo pengalaman itu mayan penting, dalam hal ini karena ngebantu ngerjain soal C :"D Yha artinya emang kudu banyak latian untuk nge-expose diri dengan berbagai macam persoalan.

Pas ICPC Jakarta beres, aku udah gak terlalu mikir sih terkait ICPC-nya. Mungkin cuma mikir "duh harus latian lagi", sama berharap di Vietnam at least performanya kayak begini. Masih ada waktu juga untuk abuse Degol sama train Inigo, jadi sebisa mungkin di Vietnam performa >= yang sekarang.

Btw, terkait problemsetnya.. Aku lumayan suka soal B sama K. Sedih juga soal K udah pernah keluar yang mirip :""(( Oiya K aku udah nemu solusi buat masalah pathnya, cukup bikin sembarang spanning tree aja + sesuatu. Yang B masih ngebug cuma males debug, hehe. Overall aku mayan suka problemsetnya. Untuk solve soal gak terlalu harus ngoding capek-capek hehe. Paling ya.. aku cuma rada heran soal G. Kalo emang intended O(N3 log N) AC kenapa N-nya 500 ya :-? Soalnya kalo itung-itungan di kertas kayak TLE gitu, padahal ini jalannya lumayan kenceng. 

Terima kasih banyak juga buat panitia yang udah mempersiapkan regional yang keren :") Dari semua regional yang pernah kuikuti tetep aja yang Jakarta paling keren haha. Moga tahun depan bisa lebih keren lagi >.<

Udah sih, sekian, semoga aku gak terlalu malas nulis yang ICPC Hanoi, hehe.

Trivia


  • Pas kontes, ada balon yang pecah. Degol terus bilang, "Yah harus ngulang ngerjain soal lagi" (konteks: cerita soal F)
  • Beberapa minggu sebelumnya, Irvin sama Ammar ada streaming main Crash Bash. Ada minigame yang mecahin balon, dan aku komentar "mecahin balon, fun to play during ICPC". Itu Irvin harus nahan diri gak bilang kalo di ICPC bakal ada soal tentang mecahin balon :")))
  • Akhirnya aku ada dapet medali perak dalam hidupku :""))))) sebelum ini selalu antara perunggu sama emas
  • Semenjak kontes ini, pas latihan sama kontes Degol sering ngerjain soal A, hanya untuk mendapatkan WA atau menyadari soalnya susah
  • Ini pertama kalinya Regional Jakarta yang gak ada foto GGanteng, berhubung gak ada Agus :"
  • Sampe sekarang aku masih gak tau lagu Tayo yang asli itu kayak gimana. Aku cuma tau versi parodinya doang
  • Hasil akhirnya rada mirip ICPC Jakarta 2016 :)) AC 9, rank 5, university rank 4, terus di rank 7 AC 8 dengan penalty 888 :"))

Senin, 05 November 2018

Penyisihan Gemastik Pemrograman 2018

Beberapa minggu yang lalu aku ikut 2 cabang Gemastik, Pemrograman sama Keamanan Jaringan. CP sama CTF. Aku ikut karena biasanya fun dan lumayan objektif. Cuma tahun ini gak terlalu begitu rasanya. Aku bakal bahas yang pemrograman aja, secara aku ngerasa aku gak terlalu dalam di perkara CTF (tapi screencast 5 jam menurutku nggak jelas).

Oiya, aku gak lolos cabang apapun di Gemastik, jadinya nggak pergi ke Surabaya. Oke, fokus ke cabang pemrograman deh. I tried not to be angry, but I can't. Beberapa rant terkait penyisihan kemarin:

1. Server down

Server down 5 menit, 10 menit masih okelah. Ini sampai 2 jam down. Terus down-nya itu gak semuanya, kayak ada beberapa session yang bisa ngakses. Misal di timku, Anab bisa buka, sekalipun kacau banget. Aku sama Rakha selalu kena gateway time out. Jadinya ya nggak fair lah lombanya, gak semua bisa buka, dan sekalipun bisa buka juga lambat banget. Pemberitahuan dari panitia juga rada lambat, kalo menurutku. E-mail yang masuk (dan baru kubaca setelah lombanya selesai) kira-kira masuk 1 jam setelah kontes. Tidak membantu.

Masalah ginian emang jarang keprediksi sih. Aku juga masih gak tahu mitigasi yang baik itu kayak gimana. Ada baiknya kalo bikin semacam chat group atau apalah yang mempermudah komunikasi 2 arah panitia sama peserta, supaya kalo ada masalah ginian infonya bisa lebih cepat. Panitia juga ada baiknya "nutup" kontesnya dulu, biar lebih fair. Cuma kalo servernya down ya gabisa kan mau nutup. Tapi kalo misalnya bisa, kayaknya lebih baik.

Yaudah, solusi terbaiknya, semoga tahun depan udah ada server yang lebih bagus aja. Kayak gini udah kejadian di INC 2017, dan pada tahun ini udah gak down lagi, padahal kontestannya jauh lebih banyak. Intinya, jangan jatuh ke lubang yang sama.

2. Ganti aturan

IMHO, kalau servernya masalah dan sering kena internal error, paling bener itu nge-spam submission sampe keluar verdict non internal error. Gambling sih, soalnya bisa numpuk WA dan lain-lain. Cuma aku rasa setelah pro dan cons-nya, tetep mending spam aja.

Secara ajaib, habis penyisihan selesai, dapet e-mail dari panitia yang menyatakan aturannya diganti, penalty jadinya banyak attempt. Luar biasa. Aku gak tau itu sebenarnya diumumin atau nggak,  kalopun diumumin setelah servernya stabil juga rasanya udah rada telat.

Selain itu, jumlah finalis juga berubah. Sebelumnya 10, ini jadi 12. Habis ini tiap kali aku bikin lomba kutulis aja finalisnya 10, baru nanti ganti basisnya sesuai keperluan. Easy.

Anyway, kalo menurutku jangan ganti aturan secara mendadak gini atau pas lombanya sudah selesai. Nggak fair. Ngubah jumlah finalis itu juga sebenernya gak terlalu bijak. Mungkin sekarang jumlahnya tambah banyak bikin seneng, cuma itu berarti gak nutup kemungkinan kalo tahun depan jumlahnya bisa dikurangi (secara kita juga nggak tahu ini kenapa mendadak ditambah). Aku curiganya ini karena penalty-nya diganti, jadinya ada yang seri terus dilolosin, but who knows.

3. Soal

Wah, ada soal kombin keren. Kok susah ya. Coba generate solusi untuk N kecil, terus cari di google. Wih, ada di OEIS. Ada formulanya juga. Soalnya bagus banget buat penyisihan yang online dan bisa googling. Nyoba nurunin rumusnya itu nggak mudah lho buat soal itu.

Kalo mau ngambil top 5 scoreboard, menurutku set soal kemarin tidak terlalu membedakan. Kayak, 4 soal pertama itu untuk top 10-15 juga masih mudah. Sisanya tinggal ngerjain easy soal ke-5, atau solve hard-nya. Kalo gak solve hard-nya, jadinya cuma cepet-cepetan solve easy. In any case, penyisihan kemarin lebih banyak cepat-cepatannya. Karena aturannya diganti, jadinya sih bukan cepet-cepetan, ganti jadi akurat-akuratan.

Aku gak tau sih scoreboardnya setelah unfrozen gimana, mungkin aja top-5 itu emang AC semua soal. Cuma itu gak terlalu bikin problemset yang bagus juga. Lolos harus AC semua. Kalo bisa tahun depan ditingkatin juga kesulitannya, misal kayak Gemastik 2016-2017. Itu paling nggak masih keliatan bedanya antara yang lolos sama nggak.

Bikin soal yang sesuai emang nggak mudah. Mungkin C4T juga gak berhasil ngumpulin soal-soal yang sesuai. Mungkin bisa juga kontak langsung orang-orang yang biasa bikin soal. Tahun depan mungkin aku juga boleh dikontak. Cuma ingat, jangan sampai orang-orang yang berpotensi kontribusi soal marah.


Mungkin poin-poin pentingnya itu.

Anyway, aku gak pernah semarah ini dalam ikut kontes CP di tahun ini. Mungkin ini yang paling buruk di tahun ini, entahlah. Aku sampe bikin ginian:


Jangan sampai tahun depan masih kejadian kayak gini. Kasihan juga soalnya, secara ini bagian dari rangkaian Gemastik yang lumayan prestisius, tapi di penyelenggaraannya bikin peserta kecewa.

Semoga tahun depan bisa lebih baik lagi. Maaf apabila beberapa bagian terlalu kasar. Apabila ada yang ingin disampaikan, bisa lewat komentar di bawah.

Note: aku gak komentarin final karena aku gak punya hak melakukan itu (gak ngerasain masa ngomentarin :P), lagian aku juga gatau apa yang terjadi di final.

Kamis, 01 November 2018

Yang Seperti DP Matrix

idk why but i feel like writing tonight

Kali ini mau bahas trik yang kayak DP matrix, tapi bukan.


Kasusnya rada khusus, biasanya main di ngitung banyak sekuens (gak selalu sih). Tapi secara kompleksitas lebih kenceng, plus ngodingnya lebih gampang. Trik ini sendiri aku gak sengaja nemunya pas ngerjain soal SPOJ yang bakal kubahas di sini. Nggak banyak yang solve, cuma mungkin ini karena emang nyari soal di SPOJ repot.

Prerequisite

Secara konsep teknik ini harusnya nggak terlalu sulit asal ngerti DP sama fast modular exponentiation (perpangkatan dalam $O(\log N)$. Kalo ngerti DP matrix (matrix exponentiation) bagus, cuma akan tiba saatnya hal itu harus dilupakan terlebih dahulu.

Ide Utama - The Toy Store

Untuk ngejelasin idenya, aku rasa mending langsung liat soal yang bikin aku dapet trik ini. Tautan menuju soal: SPOJ DCEPC14F - The Toy Store

Abstrak soal: Dikasih array $A$ ukuran $N$, terus 3 bilangan $M, K, X$. Cari banyaknya sekuens $S$ berukuran $K$, yang mana $1 \leq S[i] \leq N$ dan $ \sum_{i=1}^{K} A[S[i]] \equiv X \pmod{M}$.

Coba dipikir dulu ya, sebelum lanjut ke bawah.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Oke, jadi kalo ngeliat soal ini mungkin kebayang modelin jadi graf. Misal $cnt[i]$ menyatakan banyak elemen di $A$ yang hasilnya dimodulo $M$ adalah $i$. Maka, kita bisa membuat graf dengan nomor 0 sampai $M-1$, yang mana terdapat $cnt[i]$ edge dari $y$ ke $(y + i) \mod M$ untuk tiap $0 \leq y \lt M$. 

Selanjutnya, pertanyaan tadi bisa diubah menjadi "ada berapa banyak jalan berbeda dari 0 ke $X$?" Tentunya, hal ini bisa didapat dengan matrix exponentiation. Buat adjacency matrix, lalu pangkatkan sebanyak $K$. Tinggal ambil entri $[0][X]$-nya.

Nah, masalahnya sampai kita bisa membajak time limit-nya jadi segede gaban, kita pasti bakal dapet TLE. Ada $T$  kasus uji, dan untuk tiap kasus uji kita butuh $O(M^3 \log K)$ operasi. Pas masukin kalkulator, pasti angkanya lumayan gede. Aku sendiri udah coba optimasi beberapa kali, TLE semua.

Optimization is fun, sampe akhirnya banting setir

Nah, bisa dilihat juga kalo dulu aku ninggalin soal ini lama, dan baru dapet inspirasi pas nyoba ngerjain lagi.

Pada tahap ini, tolong lupakan DP matrix dulu.

Jadi intinya: ini kan sekuens, kita bisa kan anggep dia sebagai penggabungan 2 sekuens lainnya? Dengan kata lain, misal banyak cara membuat sekuens dengan panjang $L$, dan hasil jumlahannya $Z$ dalam modulo $M$ kita nyatakan sebagai $ways(L, Z)$. Maka, kita bisa cari nilai tersebut dengan cara sebagai berikut:

$$ways(L, Z) = \sum_{i=0}^{M-1} ways(L', i) \times ways(L-L', (Z-i) \mod{M})$$

Dengan $L'$ menyatakan panjang sekuens pertama dari 2 sekuens.

Kenapa bisa begitu? Ingat kaidah perkalian dari SMP atau SMA. Kalau kita potong jadi 2 sekuens, masing-masing panjangnya $L'$ dan $L-L'$, banyak cara di 2 sekuens itu saling independen. Untuk menggabungkannya, kita harus mengalikannya. Apabila sekuens pertama memiliki hasil jumlahan $i$, agar menjadi $Z$ ketika digabung dengan sekuens kedua, maka sekuens kedua harus memiliki jumlahan $(Z-i)\mod M$. Ya, kurang lebih gitu.

Oiya, harusnya cukup jelas ya kalau $ways(1, Z) = cnt[Z]$. Lalu, $ways(0, 0) = 1$.

Selanjutnya, kita bisa mencari $ways(L, *)$ (* artinya dari 0 sampai $M-1$) dalam $O(M^2)$ apabila kita punya $ways(L', *)$ dan $ways(L-L', *)$. Ini sebenarnya bisa kita bawa ke ranah fast exponentiation. 

Karena kita punya $ways(1, *)$, maka kita bisa mendapatkan $ways(2, *)$ dengan "mengalikan" $ways(1, *)$ dengan dirinya sendiri. Selanjutnya, dapat dilihat bahwa kita bisa mendapatkan semua $ways(2^i, *)$ dengan mudah. "Kalikan" dengan $ways(2^i, *)$, hingga jumlahan panjangnya $K$, dan hasilnya bisa didapat di entri $X$. Kita hanya perlu $O(\log K)$ "perkalian", yang mana tiap "perkalian" hanya butuh $O(M^2)$ operasi. Maka, untuk tiap kasus uji kita hanya butuh $O(M^2 \log K)$, dan cukup untuk mendapatkan AC.

Contoh solusi:
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;

int A[N];
int n, m, k, x;

void read() {
  scanf("%d", &n);
  for (int i = 0 ; i < n ; i++) {
    scanf("%d", &A[i]);
  }
  scanf("%d %d %d", &m, &k, &x);
}

// "perkalian" untuk dapat ways(L, *)
vector<int> multiply(vector<int> a, vector<int> b) {
  vector<int> ret(m, 0);

  for (int Z = 0 ; Z < m ; Z++)
    for (int i = 0 ; i < m ; i++) {
      int j = (Z - i + m) % m;
      
      // jumlahan = i dari a, jumlahan = j dari b
      ret[Z] = (ret[Z] + 1ll * a[i] * b[j]) % MOD;
    }
  
  return ret;
}

vector<int> power(vector<int> base, int pwr) {
  // identitas; sekuens kosong jumlahannya 0
  vector<int> ret(m, 0);
  ret[0] = 1;

  while (pwr) {
    if (pwr & 1) ret = multiply(ret, base);
    base = multiply(base, base);
    pwr >>= 1;
  }

  return ret;
}

int work() {
  vector<int> cnt(m, 0);
  for (int i = 0 ; i < n ; i++) {
    cnt[A[i] % m]++;
  }

  cnt = power(cnt, k);
  return cnt[x];
}

int main() {
  int t; cin >> t;
  for (int tc = 1 ; tc <= t ; tc++) {
    read();
    printf("%d\n", work());
  }
  return 0;
}

Simple and clean. Tidak perlu nulis perkalian matriks dan lebih ngebut :P

Contoh Lain - Pasti Menang!

shamelessly using own problem for example again, lel

Tautan menuju soal: Final SCPC CompFest 9 - Pasti Menang!

Abstrak soal: Ada game, yang mana game-nya dimainkan di DAG, dengan tiap node-nya antara tidak ada bidak, atau mungkin ada >= 1 bidak. Total ada K bidak. Akan dilakukan permainan yang dilakukan oleh 2 orang, dengan gerakan tiap orang adalah memindahkan salah satu bidak ke node lain yang ada direct edge-nya. Pemain kalah kalau tidak bisa menggerakkan bidak. Kita mau bikin konfigurasi peletakan bidak sedemikian hingga kalau 2 orang ini mainnya optimal, pasti orang pertama yang menang. Tentuin banyak caranya.

Udah nyoba bikin abstrak tapi masih kurang ringkas kayaknya ;_; Maaf ya. Anyway, ini soal dulu pas lombanya nggak ada yang AC ;_; Harusnya dengan pengetahuan dari paragraf sebelumnya + sesuatu cukup sih untuk solve soal ini. Coba kerjain dulu ya, baru scroll ke bawah.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

Observasinya:

  • Kalau bidaknya udah diletakkan bakal jadi nim-game, yang berdasarkan Sprague-Grundy Theorem pemain pertama pasti menang jika dan hanya jika hasil xor dari nimber $K$ bidak itu bukan 0
  • Nimber maksimum dibatasi oleh $\sqrt M$, kasarannya maksimum ada sekitar 400. Artinya, hasil xor dari nimber $K$ bidak maksimum 511.
Kita bisa modelkan ini jadi permasalahan The Toy Store, tapi di sini kita pakainya xor. Contoh solusi yang kucomot dari githubku:

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 8;
const int N = 5e4 + 5;
const int MAX_GRUNDY = 512;

vector<int> multiply(vector<int> &a, vector<int> &b) {
    vector<int> ret(MAX_GRUNDY, 0);

    for(int i = 0 ; i < MAX_GRUNDY ; i++)
        for(int j = 0 ; j < MAX_GRUNDY ; j++)
            ret[i] = (ret[i] + 1ll * a[j] * b[i ^ j]) % MOD;

    return ret;
}

vector<int> power(vector<int> base, int po) {
    vector<int> ret(MAX_GRUNDY, 0);
    ret[0] = 1;

    while(po) {
        if(po & 1) {
            ret = multiply(ret, base);
        }

        base = multiply(base, base);
        po >>= 1;
    }

    return ret;
}

int grundy[N];
vector<int> adj[N];
int n, m, k;

void read() {
    scanf("%d %d %d", &n, &m, &k);

    for(int i = 0 ; i < m ; i++) {
        int u, v;
        scanf("%d %d", &u, &v);

        adj[u].push_back(v);
    }
}

void prepare() {
    for(int i = 1 ; i <= n ; i++) {
        set<int> s;

        for(int x : adj[i]) {
            s.insert(grundy[x]);
        }

        for(int j = 0 ; ; j++)
            if(!s.count(j)) {
                grundy[i] = j;
                break;
            }
    }
}

int solve() {
    vector<int> ret(MAX_GRUNDY, 0);

    for(int i = 1 ; i <= n ; i++) {
        ret[grundy[i]]++;
    }
    ret = power(ret, k);

    int ans = 0;
    for(int i = 1 ; i < MAX_GRUNDY ; i++) {
        ans = (ans + ret[i]) % MOD;
    }

    return ans;
}

void reset() {
    for(int i = 1 ; i <= n ; i++) {
        adj[i].clear();
    }
}

int main() {
    int t; 
    scanf("%d", &t);

    for(int tc = 1 ; tc <= t ; tc++) {
        read();
        prepare();
        printf("%d\n", solve());
        reset();
    }
    return 0;
}

Kompleksitas akhirnya per kasus uji adalah $O(M \log M + (\sqrt M)^2 \log K)$ = $O(M \log M + M \log K)$.

Soal Latihan

Aku gak terlalu tahu sih soal-soalnya, rasanya gak banyak yang emang harus banget pake ini. Beberapa yang bisa dipakai:



Penutup

Trik ini lumayan lucu sih, kalo menurutku. Terus ngodingnya juga nggak terlalu susah, nggak harus tau perkalian matriks (aku kadang rada pusing ngaliin matriks, tapi nggak akut kok). Mungkin rada spesifik kasusnya, tapi yaa lumayan berguna. Selain itu, walaupun dibahasnya tadi di ranah jumlah dan xor, aku sendiri yakin kalo bisa dengan operator lain juga, misal hasil kali. Oiya, untuk yang soal latihan terakhir, itu modelinnya rada beda, jadi itu bisa jadi latihan yang bagus :P

Akhir kata, semoga post ini bisa bermanfaat dalam menambah wawasan.