Sponsor di Find IT! UGM 2019

Perkenalkan, aku Dicky Novanto, IF 15 ITB :”)), ingin berbagi cerita tentang lomba yang kami (aku, Tony, dan Yonas Adiel) ikuti, yaitu Competitive Programming Find IT! Universitas Gadjah Mada (UGM). Di sini, aku cerita finalnya aja ya.

Prelude

Kami ikut lomba ini berkat skill stalking Tony yang sangat kuat untuk memantau seluruh (lawan jenis dan) pergerakan kontes di Indonesia. Kami memutuskan untuk mendaftar, toh tidak ada ruginya juga, siapa tau bisa juara. Jadilah kami bertiga lolos penyisihan dan berangkat ke Jogja dengan nama tim Sponsor.

Bagi yang belum tahu, Competitive Programming (selanjutnya disingkat CP) adalah lomba di mana peserta diberi sebuah problem untuk diselesaikan dengan program yang mampu menerima masukan dan memberikan jawaban sebelum batas time limit dan tidak melebihi batas memory limit.

Pre-contest

Kami berangkat dari tempat yang berbeda-beda. Tony dari Bandung, sedangkan aku dan Yonas dari Tangerang setelah ikut lomba final onsite Ngoding Seru. Kami bertemu di stasiun sekitar pukul 04.30 dan berangkat ke UGM.

Setelah sampai di UGM, kami melakukan registrasi ulang dan …….. ga dapet baju :(( (baru pertama kali ikut final CP tapi ga dapet baju finalis). Setelah itu kami ditempatkan di aula, acara pembukaan, dan akhirnya jam 8.30 kami diantar ke ruang kontesnya.

Setelah sampai di ruang kontes, ada tim lain dari UI tanya ke panitia. “Ada hardcopy soal ga kak?”, dijawab “tidak”. Kami tanya juga, “Bisa print source code ga?”, “tidak”. Ok.. feeling agak buruk. Ternyata, sama seperti penyisihan, lomba final ini dilakukan di platform SPOJ. Setelah itu, kami baru sadar kalau kami belum diberi informasi login, padahal akun final berbeda dengan akun penyisihan. Lomba dimulai jam 09.00, dan kami baru berhasil login jam 08.59 -___-.

Kontes

Kontes dimulai, ada 6 soal untuk diselesaikan dalam 3 jam. Kami mulai mengerjakan soal dengan membuka 2 tab sekaligus.

Aku dan Yonas membaca soal A , Tony membaca soal D. Sementara aku dan Yonas ga paham soal A, Tony jelasin kalau soal D intinya menghitung berapa banyak karakter yang perlu ditambahkan ke sebuah string S (3 ≤ |S| ≤ 5.000) agar terbentuk string baru yang palindrom. Loh, ini kan soalnya sama seperti soal yg pernah ada di latihan komunitas CP, jadi Yonas langsung koding LCS (Longest Common Subsequence) dan soal D: Palindrome solved pada menit ke-18.

Meanwhile, aku akhirnya paham soal A dan inti soalnya adalah ditanya nilai (1⁵ + 2⁵ + 3⁵ + … + N⁵) mod 10⁹, tapi N-nya bisa sampai 10⁹, sehingga solusi iteratif tidak bisa menembus time limit. Untungnya di cheatsheet kami ada rumus itu (terima kasih, cheatsheet AingeWF) dan rumusnya adalah:

Nah masalahnya, hasil akhir perlu dimodulo 10⁹ yang mana bukan prima sehingga tidak bisa dilakukan modulo inverse secara langsung. Tony sebagai buruh soal math, langsung mengerjakan dan soal A: Kelereng solved pada menit ke-25.

Aku dan Yonas baca soal B. Pada soal B, diberi persamaan

x = b (s(x)^a )+c

dengan s(x) adalah sebuah fungsi untuk menjumlahkan digit-digit dari x (misal x = 1234, jadi s(x) = 1 + 2 + 3 + 4 = 10), 1≤ a ≤ 5, 2 ≤ b ≤ 10⁵, -10⁵ ≤ c ≤ 10⁵, dan 1 < x < 10⁹, dan ditanyakan berapa saja nilai x yang memenuhi persamaan itu. Jika kita melakukan bruteforce untuk semua kemungkinan x, pasti akan melewati batas time limit. Observasi yang penting adalah nilai s(x) maksimal adalah 81 (karena maksimal x = 999.999.999), sehingga kita dapat melakukan bruteforce nilai dari 1 hingga 81 dan mengecek apakah ada x yang sesuai. Yonas koding soal ini dan soal B: Menghitung solved pada menit ke-32.

Pada saat ini, tim kami berada pada peringkat 1 dengan time penalty kecil karena tidak ada solusi yang mendapat verdict Wrong Answer (WA). Tersisa 3 soal, kita semua fokus mengerjakan masing-masing 1 soal dan kadang saling bahas.

Soal C: Movie Sort. Di soal ini, diberikan N judul film, tahun rilisnya, dan prequel-nya, lalu diminta menuliskan kembali judul film sesuai dengan kriteria tertentu. Namun, diperlukan string parsing yang menjijikkan (handling spasi dan kasus tertentu). Selain itu, ada banyak yang ambigu di soal ini. Kita mau melakukan klarifikasi, namun ternyata klarifikasi hanya dibuka 1 jam pertama. Sampai selesai kontes, soal ini tidak mampu kami solved.

Soal E: Ranting Kayu. Di soal ini, kita diminta membuat array A berisi permutasi 1 hingga N (1≤ 2000 ≤ N) dengan syarat untuk setiap pasangan i dan j (1 ≤ i < j ≤ |A|), tidak boleh ada bilangan (A[i] + A[j]) / 2 di antara indeks i dan j. Sampai dengan akhir kontes, kami tidak beruntung mendapatkan polanya.

Ketika tim lain mulai ada yang solve lebih dari 3 soal, kami masih stuck. Tapi scoreboard di-freeze satu jam terakhir, jadi seolah-olah kami masih di peringkat pertama.

Sampai akhirnya 30 menit terakhir, Yonas lelah dengan soal C dan dia mencoba memikirkan soal F. Di soal F, diberikan string yang terdiri dari karakter S atau M. Kita dapat mengubah karakter S menjadi M apabila di sebelahnya terdapat karakter M, vice versa. Ditanyakan berapa banyak cara untuk mengubah string menjadi S semua dan M semua, dimodulo 10⁹ + 4. Yonas menemukan rumusnya, lalu dikoding Tony, tapi mendapat WA setelah disubmit. Tony baru sadar ada bug, submit lagi dan masih WA. Kita mulai panik dan aku mencoba bantu bug fixing, dan menyadari kalau lupa dimodulo. Submit lagi, WA lagi. Lihat-lihat lagi source code-nya, curiga ada char s[2000], langsung aku bilang, “Ton, panjang string input berapa”, “oh ternyata 10.000”. Lalu submit lagi, dan akhirnya soal F: Marcel Sang Ketua solved pada menit ke-169 (yup, 10 menit sebelum selesai kontes).

Post-Contest

Setelah kontes, kami merasa sedih karena hanya menambah solved 1 soal dan banyak tim lain yang solved 4 soal. Bahkan ada yang solve 6 soal. Karena kami lama solve soal F, kami kira penalty kami akan jauh lebih besar sehingga tertinggal jauh dari tim lain.

Akhirnya, kami memutuskan untuk pergi ke Jogja City Mall karena setelah kontes jam 12 siang, kami diminta untuk berkumpul lagi jam 4 sore. Pada saat perjalanan, kami diskusi tentang kemungkinan kami bisa juara. Lalu Tony iseng mencoba login dan ternyata scoreboard sudah di-unfreeze. Tony langsung bilang kalau kita peringkat 3. Yonas tidak percaya, “SERIUS TON??? SERIUSS?? SERIUS?”. Ya kami senang walaupun kurang puas juga karena kami berekspektasi lebih (mengingat sampai 1 jam terakhir kami masih peringkat 1).

Winner Announcement

Setelah jalan-jalan di Jogja City Mall, kami kembali ke UGM. Ketika pengumuman, sudah tidak surprise lagi karena sudah tau sejak di mobil. Dan ga sia-sia bikin nama tim “Sponsor”, host-nya sedikit bingung waktu mengumumkan, “Juara 3 dari …. Sponsor …. maksudnya sponsor dari ITB, …. nama timnya memang sponsor, bukan sponsor acara”.

Aku dan Yonas pakai kaos karena mengira akan ada baju finalis

Momen Unik

Ada beberapa momen unik terkait ini dan setelah kontes:

1. Pertama kali kontes tingkat nasional tapi kontesnya di SPOJ
2. Kontes Find IT! ini kontes paling simpel yang pernah aku ikuti, mulai dari ga diberi kaos, pakai SPOJ, dll.
3. Aku di-tease terus gara-gara ga solve apa-apa :( .
4. Ini pertama kali aku dan Tony dapet juara lomba CP
5. Tony masih niat ngerjain Google Code Jam Round 1B jam 23.00 di kereta, dan besoknya UAS PBD jam 7 pagi, padahal kereta kita sampe di Bandung jam 5.15.

Ya jadi sekian sharing pengalaman kami selama final FindIT, semoga ITB dapat semakin bersinar lagi di lomba CP dan bersaing ketat dengan universitas lain. Terima kasih.