Final Arkavidia 4.0

Setelah lolos penyisihan CP sama CTF Arkavidia, sabtu kemarin aku ikut final lombanya. Ikut lomba yang mana? Well, dua-duanya. Jadi habis nanya panitia (Turfa), aku bisa ikut CP dulu, terus keluar tengah jalan pindah ke CTF, cuma gak boleh balik ke tempat CP lagi. Aku sendiri mutusin pindah kalo udah ada seenggaknya 2 kondisi berikut:

• Udah gak bisa dikejar lagi
• Soal yang tersisa nggak sesuai jalan ninjaku

Karena lombanya di Bandung, aku mikirnya buat sekalian ketemu kakakku yang kerja di Bandung. Pas cek jadwal lomba, duh mepet. Aha, ada jam istirahat dari jam 4-7. Aku jadi kontak kakakku buat ketemuan jam segitu. Rencananya juga malamnya mau nginep di tempat kakakku.

Jumat malam aku sama Ricky nginep di ruang Ristek, soalnya bakal berangkat sabtu pagi ke Bandung. Untung bisa bangun. Kami jalan ke tempat travel, terus ketemu Fahmi di situ. Reynaldo juga naik travel yang sama ternyata. Terus yaudah, cabut ke Bandung. Nyampe Bandungnya sekitar jam 9. Itu aku jadinya kontak Jauhar (PIC CP) kalau datangnya agak molor, karena udah ngerasain gak enaknya ngurus lomba yang pesertanya telat dateng registrasi :""" Maafkan saya panitia :"

Sampe di ITB, aku pisah sama Ricky Fahmi karena mau regis CP. Habis regis, dibawa ke ruangan yang dulu kalo gak salah dipake ngasih materi pas jamanku masih Pelatnas (dih udah tua). Sebelum lomba, ada sesi sama Bukalapak dulu, intinya ngenalin Bukalapak gitu. Habis itu kami dibawa ke lab yang dipake lomba, untuk bagi tempat sama briefing.

Baris tempatku ada 3 orang, paling kiri Degol, tengah aku, kanan Rafael. Ada kayak briefing, cuma rada gaje gitu. Walaupun mungkin penting sih, soalnya ada safety-nya. Cuma beberapa fakta di slidenya malah bikin serem.

Terus nyoba-nyoba kompinya.Yey Linux! Nyoba-nyoba compiler sama text editor lancar. Terus nyoba internet sama login ke DOMJudgenya. Internet lancar, DOMJudge-nya ee. Susah bedain l (l kecil) sama I (i besar) di password. Beberapa kali nyoba baru bisa login. Yang kocak, aku iseng buka google. Ternyata gak diblok :O :O :O buka github juga bisa :O Dari panitia cuma diperingatkan kalo bakal ketahuan seandainya buka yang kayak gitu. Oke deh, cuma masih prefer sekalian diblok aja sih. Terus karena masih ada yang belum bisa login, jadinya bebas gitu. Panitia juga bolehin ngetik-ngetik dulu, mo ngetik template juga boleh. Hmm... kurang sreg tapi yaudahlah. Aku gak ngoding template karena emang gak punya. Sebenernya bisa aja ngopas isi citsit, cuma males.

Setelah semua udah beres, nunggu 5 menit buat kontes mulai. Kemudian, kontes dimulai! Karena dikasih versi cetak soalnya, aku buka aja amplop isi soalnya, terus baca. Lebih enak baca di kertas daripada baca di komputer :P Skimming:

• A: Duh, sort BigInteger. Oh ada constraint X[i] + Y[i] = C untuk tiap i. Bisa lah pake itu. cuma mager
• B: Dih jorok. skip
• C: Kayaknya ada hubungannya sama upper hull. skip
• D: Terlihat DP-ish. Gak langsung keliatan solusinya. skip
• E: Bentar ini kenapa sample-nya gini? Kayaknya salah ngerti soal. skip
• F: (liat gambar lingkaran) skip
• G: Wah math. Kayaknya bakal ribet. skip
• H: Oh BIT 2D, harus kompres. mager. skip
• I: loh soalnya sampe H doang

.

.

.

INI GAK ADA SOAL BONUS GITU YA?

Dari semua soal, yang keliatannya paling gampang A. Cuma, kalo itu yang paling mudah, udah kerasa kalo ini kontes bakal berdarah-darah. Aku jadinya mulai dari A. Intinya, dia minta sort berdasarkan X[i] * Y[i], terus X[i] + Y[i] = C untuk suatu C. Awalnya mau hajar Java BigInteger aja, cuma rasanya bakal TLE. Yaudah aku coba mikir C++ aja. Aku mikirnya misal X[i] < Y[i], bisa sort berdasarkan Y[i] - X[i]. Jadinya, aku bikin supaya X[i] sama Y[i] di-pad dengan 0 di depan, terus lakuin pengurangan BigInteger. Ngodingnya gitu aja, cuma ya, hih. Submit. Nunggu. Nunggu. Lama, bisa bikin kopi dulu. Nunggu. Wrong Answer. Ee.

Habis itu, aku coba baca soal lain dulu. Akhirnya, aku ngerti maksud soal E: dikasih array S[i] sama D[i], ada Q query yang isinya hitung max(T * D[i] + S[i]) untuk $L \le i \le R$ . Pas awal baca aku kira hitungnya jumlah, bukan max :s Palingan solusinya Segment Tree isi Convex Hull Trick. Aku jadinya balik ke A lagi. Hmm, gak ada yang keliatan salah. Terus aku baru nyadar kalo di suatu tempat ada yang salah, kutulis '-' bukannya '+'. Habis ganti itu, tes sample, bener. Submit. Nunggu. Nunggu. Accepted. A - Mengurutkan Bilangan AC! Pas itu jadinya rank 3. FYI, setengah jam baru max. AC 1 dari 8 soal. Fix berdarah-darah ini bakalan.

Karena yang saat ini kepikiran E sama H, terus H rasanya lebih capek, aku ngoding E dulu. Aku cukup pede ngerjain E gara-gara beberapa minggu lalu rada sering ngerjain soal pake CH Trick di Kattis. Setelah beres, tes sample, OK. Submit. Nunggu. Nunggu. Wrong Answer.

Kampret ini salah di mana. Terus pas baca kodingan, ternyata ada 2 bug fatal. Salah bikin komparasi untuk nge-pop stack sama ada variabel yang lupa ditambah :"" Jadinya aku coba cek isi semua convex hull-nya dulu. Habis ngerasa yakin, submit. Nunggu. Lama pisan. Accepted. E - Meretas Password Wifi AC!

Habis itu aku baca D sekilas lagi, masih gak dapet ide. Inti D itu gini: Dikasih rooted tree ukuran N dan bilangan X, bikin supaya tiap node nilainya non-negatif, jumlahnya X, dan nilai parent harus lebih kecil atau sama dengan nilai anaknya. Terus yaudah, aku nyicil ngoding H. Pas nyicil ngoding, tiba-tiba kepikiran sesuatu buat D: bisa anggap nambah di suatu node itu sebagai nambah di subtree-nya, dan ini akan mempertahankan kondisi terakhir. Jadi yaudah, aku pindah ke D.

Solusiku rada aneh gitu sih jadinya. DP, tapi ada kombin sama loop harmonic-nya. Harusnya $O(NX \log X)$. Untungnya ngetes kasus terburuknya mudah, bikin chain, terus N = 5000 dan X = 5000. Pas dicoba di local sekitar 0.98 s. TL 2s. Hajar aja dah. Submit. Nunggu. Nunggu. Lama. Accepted. D - Hari Gajian AC!

Pas liat scoreboard, beneran berdarah-darah. Itu aku rank 1 dengan AC 3, peringkat 2 sampe berapa gitu AC 1. Masih banyak yang AC 0. Brutal.

Aku terus lanjut ngoding H. Gara-gara jaman Pelatnas dulu sering ngerjain soal DS 2D gini jadi udah lumayan kebiasa. Yey, kelar. Pas mau ngambil sample di DOMJudge, loh gak dimasukin. Yaudah aku ketik manual. Coba run. Hmm, gak nampilin apa-apa. Hmm, ini kok komputernya tambah lemot.

.

.

.

.

.

Rapidly smashing CTRL+C in panic

Gara-gara kebiasaan ada memory jebol, pasti ini ada yang bikin nambah memory terus-menerus. Kayaknya ada logic kompresinya yang ngawur. Bener aja, ada yang pas dicari indeks-nya malah dapet 0. Ya loop BIT-nya gak bakal berhenti. Habis benerin bagian itu, tes sample lagi. Hmm, terlihat benar. Bodo amat, submit aja. Nunggu. Nunggu. Mau bikin kopi dulu. Nunggu. Accepted. H - Kotak Coklat AC!

Kembali lagi liat scoreboard. Pas menit 100an, akhirnya ada yang AC 2. Degol dapet soal B. Gap-nya udah jauh sih, tapi masih bisa dikejar, masih lama soalnya. Cuma aku gak mau ngerjain B. Jadinya aku nyoba liat soal C sama G.

Pas ngoret soal G, setelah nanganin kasus p = 0 dan p = 1 sendiri, aku udah berhasil ngerjain sampe tinggal nyari k terkecil sehingga $p^{k} \equiv y \pmod{m}$. Cuma gak nemu. Di citsit juga gak ada yang keliatan ngebantu. Coba bikin rumus, cuma rasanya kalo bisa bikin rumus bisa bikin paper (ini ngawur sih). Terus aku coba baca C. Intinya gimana cara memelihara upper hull. Bau-bau pake Mo's Algorithm, cuma gak tau cara nge-restore upper hull kalo ada yang dibuang. Rasanya bisa pake Linked List gitu, cuma semakin dipikir semakin pusing.

Karena dah waktunya sholat, aku turun dulu buat sholat. Pas wudhu, mikir. G. Tiba-tiba dapet inspirasi: k pasti kurang dari m, terus sebenernya bisa lakuin meet-in-the-middle buat nyari k-nya. Bagi bit, jadi bit 0-15 di awal, 16-30 di akhir. Brute force, terus MITM. Terlihat OK. Pas kepikiran rasanya: Eureka! Eureka!

Habis sholat, aku lari ke lab buat ngoding. Ngos-ngosan. Anjir, ini badan emang kurang olahraga. Setelah beberapa saat, mulai ngoding. Kodingannya gak panjang-panjang banget, cuma math yang biasa kepake. Coba sample, loh kok salah. Aha, ada bug. Benerin lagi. Yey, lolos sample. Cuma rasanya ada yang aneh. Asik, ada bug lagi. Habis ditambal, udah cukup yakin kalo itu bener. Submit. Nunggu. Nunggu. Nunggu. Nunggu. Krik. Krik. Accepted. G - Random Generator AC! Yay! Secara gak sadar bilang "yes" sambil ngepalin tangan. Berpotensi mengintimidasi yang melihat.

Pas AC G, liat scoreboard lagi. Rank 1 AC 5. Rank 2-5 AC 2. Rank 6-15 AC 1. Sisanya AC 0. Well...

Habis itu, kerjaanku malah nontonin Christo yang duduk di depanku ngoding. Dia pas itu AC 2, masih berpotensi nyusul. Aku liat jam. Hmm, masih 1 jam 35 menit lagi. Yaudah nontonin Christo dulu. Kalo Christo nambah pindah ke CTF-nya diundur. Kalo gak nambah yaudah pindah ke CTF. Sampe sisa 1 jam 20 menit dia gak nambah, yaudah aku bawa tas terus pindah ke CTF.

Sesampainya di sana, Ricky sama Fahmi lagi ngerjain Forensic sama Web. Aku langsung ngerjain Pwn-nya. Wew, soalnya ada pre-requisite-nya gitu. Auth1 - Auth4 1 program, alurnya urut. Kalo gak solve 1 gak bisa dapet lanjutnya. Aku mulai dari Auth1 dulu. Pas lagi baca assembly-nya, Fahmi dapet Forensic yang 100. Yey, kami gak 0 :""))) Aku baca lagi Auth1, intinya ada ngecek input dengan suatu nilai hasil rand(). Cuma, ternyata seed-nya sama gak di-set. Jadinya harusnya nilainya sama terus. Yaudah, aku coba, eh dapet flag :")) Yey bisa berkontribusi 40 poin :"))

Habis itu aku udah puyeng banget. Dah jam 4, loh kok lombanya belom kelar. Kata Ricky lombanya mulainya molor, tadi mulainya dari jam 1. Selesainya jam 6. Anjir. Karena CTF rada bebas, aku buka FB terus kontak kakakku, bilangin masalah ini. Habis itu aku coba Auth2, gak dapet ide. Mikirnya gimana caranya biar open() bisa masukin path dev/urandom, tapi yang dibuka dev/zero. Gak dapet ide. Sampe 10 menit terakhir, baru nyadar kalo di servicenya bisa nambahin file di tmp/ :"""" Jadinya bikin tmp/dev/urandom, terus Auth2 ngerjainnya buka file itu. Dapet flag Auth2 :"""))) Habis itu lombanya beres. Total akhir 180, rekt parah :")) Timnya Wira, Rakha, Aldi (Arkavidia 9) kayaknya bakal menang, sebelum freeze 505 poin.

Iya, nama timku sama timnya Wira emang ngajak gelut. Dua-duanya reference ke CompFest.

Pas lombanya beres, aku mau ketemu kakakku, cuma kakakku bilang waktunya mepet Gala Dinner Arkavidia, jadi bilangnya ketemunya nanti aja habis Gala Dinner. Jadinya aku bareng peserta CTF lainnya aja habis itu. Btw, si Fahmi udah balik duluan ke Jakarta/Depok, gak tau kenapa pengen langsung pulang gitu. Kami ke Masjid Salman buat sholat, terus jalan ke aula timur untuk Gala Dinner.

Yang CTF sampe aula timur duluan dari CP. Pas yang CP dateng, aku ngobrol-ngobrol sama FJ + Degol tentang kontes tadi. Degol tetep di AC 2, terus kata FJ Binus juga paling banyak AC 2. Wew. Soal-soalnya tadi susah, tapi rasanya terlalu gak balance. Ketika kemaren CompFest udah brutal, masih ada yang bisa lebih ganas :| Komentar tentang lombanya nanti di bawah deh.

Pas Gala Dinner, udah ngerasa ini bakal lama. Aku dikontak mamaku, intinya mending kakakku balik aja kalo gak ada kepastian gini, kasian soalnya udah nunggu dari jam 4. Jadinya aku chat kakakku, bilang kalo ketemuannya mungkin besok aja sebelum aku balik ke Depok, terus kakakku balik ke apartemennya. Still feeling guilty for this :'(

Acaranya akhirnya mulai, terus habis sambutan atau apapun itu yang gak pernah kuperhatiin, akhirnya ada makan-makan. Udah laper banget, jadinya langsung ngantri. Apesnya, antrian yang kuambil itu yang sering diselip-selipin orang penting, jadinya aku ngantrinya mayan lama. Dari dulu udah kebiasa ngantri dapet antrian yang paling lama, entah kenapa ini selalu terjadi padaku :"")))

Akhirnya ada pengumuman juara! Untuk CP, juaranya dari 1-3 + 1 HM. Juaranya:

1. Muhammad Ayaz Dzulfikar
2. Degoldie Sonny
3. Christopher Samuel
4. Andreas Martin

Hasil akhir selama masih up bisa dilihat di https://scoreboard-arkavidia.cf/

Untuk CTF, Arkavidia 9 juga juara 1!

Scoreboard akhir

buat lucu-lucuan aja, pegang gabus CTF

Jingga Boyz

Setelah penutupan dan foto-foto, kami lalu pergi ke penginapan yang disediain panitia. Tidur, terus besoknya balik ke Depok. Aku akhirnya gak jadi ketemuan sama kakakku btw, kakakku gak bisa ke tempat travelnya pas besok paginya :"

Udah lama gak lomba yang perorangan, mayan juga ada ginian. Ternyata aku masih nggak sekaratan itu haha :") Moga aja sebelum pensiun masih bisa dapet sesuatu lagi ._.v

Trivia:

• Degol: "Lu keluar di satu jam pertama juga bisa menang Yaz", dan emang iya AC 2 di menit ke-45 harusnya udah menang
• Pertama kalinya euy ikut dua kontes onsite bersamaan

Notes

Btw, ini komentar tentang kontes CP-nya. Mungkin bisa untuk feedback. Aku gak bermaksud menyinggung siapa-siapa di sini ._. Bisa skip bagian ini kalo males baca hehe.

Problemsetnya aku rasa susah. Mungkin kesulitannya mirip CompFest. Cuma, mungkin kurang seimbang? Di CompFest selama 2 tahun terakhir aku mastiin biar peserta bisa AC seengaknya 1-2. Ini di akhir ada yang gak AC sama sekali T_T Jadi kayak bonus gitu gak ada. Terus ini kontesnya perorangan, jadi mayan susah gitu. Di ICPC, biasanya bisa bagi-bagi kerjaan. Kebetulan aja, E sama H itu soal yang kalo di ICPC pasti dilempar ke aku, makanya aku (harus) lancar ngerjainnya. Cuma buat kebanyakan peserta pasti susah. Kalo habis ngobrol sama FJ + Degol, "E sama H itu idenya simple tapi ngodingnya males"

Sama rada penasaran masalah difficulty. Ini rasanya:

• Easy: A
• Medium: B, D
• Medium-Hard: E, H (implementation hell)
• Hard: C, F, G

Tapi spike difficulty-nya loncat banget. Dan aku aslinya gak bakal bilang A easy sih...

Mungkin untuk CP Arkavidia tahun depan bisa dibikin lebih balanced lagi, sama naikin jumlah AC pesertanya :")) Sama kalo bisa cari server yang cepetan, sebelum refresh button-nya rusak :"")) Pertahankan yang bagus dari tahun ini (soal menantang, editorial) dan perbagus lagi untuk tahun mendatang!

Overall, dari penyisihan-final, aku suka soal D, E dari penyisihan sama D, G dari final. G dari final keren, walaupun aku gak tau itu di editorial baby-step (baby shark?) giant-step apaan, kayaknya teknik yang gak pernah aku baca. 

Catatan gak penting, kalo inget netijen:

Netijen: "Emangnya lu bisa bikin kontes ?!?!?!?!?"

Me: "Bisa"