IOI 2016 – Kazan, Russia! (Part 1/2) [IDN]

Bagi yang belum tau IOI itu apa, IOI adalah singkatan dari International Olympiad in Informatics. IOI itu adalah salah satu dari International Science Olympiad dan IOI udah diadakan dari tahun 1989. Jadi untuk olimpiade komputer tingkat SMA, IOI udah kaya semacam level paling atasnya gitu(?) Tiap tahun negaranya ganti-ganti dan bisa dilihat di page wikipedianya (tahun 2018 di Jepang /nangis deres/ /pengen/). Cara ikutnya kalau di Indonesia harus melalui OSK – Olimpiade Sains Kota, dipilih 3 peserta per kota terus ke OSP – Olimpiade Sains Provinsi, dipilih 3(?) per provinsi untuk lolos ke OSN – Olimpiade Sains Nasional, terus diambil 30 medalis: 5 emas, 10 perak, 15 perunggu. Dari 30 medalis ini akan mengikuti pelatnas (pelatihan nasional) tingkat 1 yang biasanya diadakan di ITB, lalu 15-16 peserta lolos ke pelatnas tingkat 2 dan beberapa tahun ini diadakan di ITS, diambil 8 peserta untuk pelatnas tingkat 3 yang waktu tahun 2015-2016 diadakan di IPB, lalu akhirnya diambil 4 peserta saja yang lolos ke pelatnas tingkat 4 dan mewakili Indonesia di IOI. Terus TOKI itu singkatan dari Tim Olimpiade Komputer Indonesia, anggotanya peserta OSN, pelatnas, pembina, dll.

IOI kali ini adalah IOI keduaku, yang pertama IOI 2015 di Kazakhstan. IOI 2016 ini diikuti oleh 308 peserta dari 80 negara, dan kalau ga salah hitung jumlah peserta cewenya cuma ada 6, termasuk aku. Karena acaranya udah 3 bulan yang lalu, aku banyak lupa detail yang penting dan lebih banyak ingat detail-detail yang ga penting, jadi kayanya 2 post aja cukup :p

Day 0 & 1 – Berangkat dari Soekarno-Hatta + registrasi

Keberangkatan kali ini agak beda sama tahun lalu, soalnya dari pelatnas 4 langsung berangkat ke Russia. Kalau tahun 2015 habis pelatnas 4 pulang dulu 1-2 minggu, baru kumpul lagi di Jakarta buat keberangkatan.

Jadi tim Indonesia kali ini ada 10 orang yang ikut:

  • Pak Rully Soelaiman – team leader Indonesia, pembina TOKI
  • Ko Irvin (Jonathan Irvin Gunawan) – deputy leader
  • Sergio Vieri – peserta
  • Klungs (Kwee Lung Sin) – peserta
  • Ucup (Muhammad Yusuf Sholeh) – peserta
  • Me – peserta
  • Pak Fauzan Joko – pembina TOKI, guest
  • Pak Rosyid – diknas, guest
  • Bu Inggriani Liem – pembina TOKI, guest
  • Mamanya Sergio – guest

Total perjalanan Jakarta – Kazan sekitar 26 jam termasuk transit. Jadi pertama dari Jakarta – Doha 8 jam, Doha – Moscow sekitar 5 jam, dan Moscow – Kazan 1-2 jam. Waktu sampai di Kazan sekitar jam 2-3 subuh jam-nya Russia.

Di bandara Kazan, kita sudah ditunggu sama panitia IOI dan guide tim Indonesia, Rita. FYI, kalau di IOI masing-masing negara dikasih 1 guide buat nganterin ke tempat makan/lomba, buat kalo perlu ngomong sama orang lokal yang ga bisa bahasa Inggris, dll. Habis foto-foto bentar, kita langsung diantar ke tempat penginapan kita: The Universiade Village.

ioi_arrival

Foto di bandara Kazan. Photo taken from blog.ia-toki.org

screen-shot-2016-11-08-at-9-57-49-am

The Universiade Village. Photo taken from ioi2016.ru

Sebelum diantar ke kamar, kita diajak dulu ke main buildingnya untuk registrasi, dan dikasih merch-merch(?) keren ini:

merch_ioi_2016

Photo taken from twitternya Ko Irvin, warna hijau sebenarnya buat team/deputy leader. Buat peserta merch-nya sama, tapi warnanya biru semua.

Habis itu, para peserta diantar ke kamar masing-masing, team leader/deputy diajak ke tempat penginapan mereka di gedung lain, dan yang guest di hotel yang tempatnya jauh dari Universiade Village. Selama 2 tahun aku ikut IOI, biasanya peserta yang dari negara sama pasti dijadiin 1 kamar, tapi karena tahun 2015 yang cewe cuma aku, jadi sekamar sama cewe Macau. Kamar di Russia ini lumayan luas, bentuknya kaya apartemen mini gitu. Jadi waktu masuk, ada area pantry kecil + kamar mandi, lalu ada 2 kamar tidur lagi di dalamnya. Karena waktu aku datang, 2 kamar itu masih kosong, aku langsung tanya ke Rita:

Me: “Sooo, who is my roommate?”
Rita: “What?”
Me: “Err, there are 2 bedrooms here, so somebody else will sleep here, right?”
Rita: “Oh, no no. This room is all yours. Girls’ luxury, you know 🙂 “

YES. KAMAR VIP.
Jadi setelah itu aku langsung ambil bantal di kamar satunya (kebiasaan orang indo, ga ada guling ga bisa tidur), lalu tidur sepuasnya~ (habis +- 24 jam ga bisa tidur di pesawat).

Karena hari 0-1 ini acaranya memang cuma kedatangan dan registrasi, dan karena kita udah registrasi waktu subuh itu, kerjaanku cuman tidur + makan + nonton anime dan ga ada yang menarik, jadi aku skip.

Note: karena cuma ada 2 ranjang di 1 kamar, yang cowo katanya dikasih 1 extra bed. Jadi kalau ga salah Ucup sekamar sama Lung Sin, terus Sergio tidur sendirian.

Day 2 – Practice Session & Opening Ceremony

Besok paginya, kita diajak makan dulu sama Rita. Di Russia kali ini makannya di cafetaria yang besar banget. Biasanya pilihannya buat breakfast rata-rata kaya gini: beberapa jenis yoghurt Danone, roti, sereal, keju, ham, kaya bubur (1), kaya bubur (2) tapi warnanya agak kemerahan (I’ll reveal what this is later), sosis, omelette, sama beberapa jenis cake dan British pancake. Sosis sama omelettenya enak banget, telurnya bisa fluffy gitu. Serealnya ada corn flakes sama koko krunch tapi bentuknya bulat (di indo ga pernah makan sereal tapi kayanya koko krunch normal ga kaya gini kan bentuknya? Tahun waktu aku di Kazakhstan koko krunchnya bentuknya juga gini #random). Terus aku beberapa hari pertama ambil yang kaya bubur (1), terus waktu dicoba, ternyata buburnya manis banget, jadi masih ga tau itu sebenarnya apa. Habis makan, kita selalu taruh tray kotornya di tempat yang kaya ini, dan bisa dijadiin challenge gaje siapa yang bisa naruh di deretan yang paling atas tanpa mecahin apapun.

Habis makan acaranya practice session, dan gedungnya sama dengan tempat cafetaria, jadi kita tinggal naik eskalator saja ke tempatnya. Tempat lomba IOI 2016 di lapangan indoor, terus diatasnya dihiasi bendera semua negara peserta.

competition_env

Photo taken from ioi2016.ru

Di practice session ada 4 soal, yang jauh sebelum berangkat ke Russia sudah bisa dikerjakan dan disubmit sama peserta, jadi waktu practice session on-site sebenarnya cuma kerjanya membiasakan diri dengan environment(keyboard, monitor, dll). Di sesi ini kita juga harus meninggalkan barang-barang yang akan kita pakai untuk kontes selama 2 hari, jadi barang-barang seperti alat tulis, maskot kecil, atau keyboard harus dibawa pada sesi ini, dan waktu sesi kontes tidak boleh bawa barang apapun. Terus biasanya di practice session ini juga dijadikan kesempatan buat “ngancurin” grader. Jadi tes buat time limit, stack limit (dulu aku kira ini banyak-banyakan isi STL stack, ternyata bukan, ini sepengetahuanku kaya tes depth dari dfs gitu), dan memori limit. Waktu sesi ini team leader sama deputy boleh masuk ruangan buat lihat-lihat juga. Dan waktu nulis ini aku baru sadar di web-nya IOI ga ada practice task-nya, dan aku lupa soalnya. Damn. Kalau ga salah ingat 2 ad-hoc, 2 trivial banget sih. . . edit: sudah ada soal practice session di web IOI, bisa dilihat di sini.

Habis sesi selesai, makan siang, terus ke auditorium buat opening ceremony yang bisa dilihat di sini. Opening ceremony-nya menurutku meriah banget, banyak tarian dan nyanyian tradisional dan modern dari Russia, terus banyak rok dancer cewenya yang bisa terbang-terbang waktu muter-muter (<<ini random). Yang keren itu bagian waktu setelah sambutan-sambutan, orang yang pidato itu kaya disuruh ke podium yang ada tombol(?), terus waktu di pencet di screen-nya bisa muncul kaya "fingerprint detected", terus muncul fotonya mereka, etc yang bagi orang 'ndeso' kaya aku itu keren lol, pokoknya kaya yang di film-film gitu, dan lumayan mengingatkan aku sama awalan lagu opening Nico-Nico Music Party 2015 part Vocaloid (minus musik dan hologramnya lol). Habis opening ceremony, kita free time kalau ga salah kerjaannya tunggu leader general assembly buat peraturan-peraturan lomba besoknya. Waktu menunggu, aku juga di-interview sama wartawan, dan di beberapa hari seterusnya aku juga di-interview sekitar 3-4 kali di kesempatan berbeda. “Stacia kenapa eksis banget?” Alasannya simpel.
"I can't find any girls here, so you'll do ahaha" – wartawan.

Setelah itu team leader memberi tahu kita peraturan-peraturan buat lomba besok, dan ada 1 peraturan yang tidak jadi diberlakukan karena ambigu, yaitu peraturan yang tidak memperbolehkan peserta untuk memanfaatkan umpan balik dari grader untuk reverse-engineer (mendapatkan informasi dari) test case yang diberikan. Kita lalu diantar untuk makan malam, terus ke kamar masing-masing untuk karantina, dan para team leader men-translate soal untuk hari pertama.

Untuk makan siang dan malam di Russia ini rata-rata menu makannya: beberapa jenis salad, suatu juice yang ga tau isinya apa (“A kind of healthy juice,” – Rita), beberapa jenis sup, beberapa jenis cake, kadang ada roti isi bawang yang enak banget, terus pilihan karbohidrat (mashed/boiled potatoes, spaghetti, nasi), protein (daging, ayam/ikan di bake dan dikasih keju di atasnya, kadang ada ikan mackerel yang dimasak saus tomat), dan jeruk/pisang. Katanya orang-orang nasinya kaya nasi yang ga matang, tapi karena saya ga tau nasi ga matang itu rasanya gimana, saya oke-oke saja waktu makan itu orz.

Waktu karantina ini para peserta tidak boleh meninggalkan kamar masing-masing, dan akan ada panitia yang ngecek tiap kamar peserta. Lalu Wi-Fi gedung itu juga dimatikan, jadi tidak ada akses internet sama sekali, dan aku diberitahu cowo-cowo, katanya Ucup dan Sergio juga tidak bisa main game yang membutuhkan akses bluetooth, jadi sepertinya segala bentuk sinyal di gedung tempat peserta tinggal di-jammed (ini keren banget). Untuk menghabiskan waktu karantina, aku review algo-algo kaya segment tree, max flow, dll, terus hafalin algo yang jarang dipakai, kaya bridge articulation point (iya, waktu IOI ini aku belum hafal :p ), dll. Terus sekitar jam 9 malam, aku pakai strategi kebiasaanku H-1 sebelum menghadapi tes atau lomba penting: nonton anime yang ga traumatis. Jadi kalau ga salah waktu itu aku re-watch Gekkan Shoujo Nozaki-Kun (<< recommended) sama Aldnoah Zero, terus tidur jam 10-10.30an.

Day 3 – Contest Day 1

To skip the contest, click here.

Sistem lombanya seperti biasa, dalam 5 jam diberi 3 soal, skor maksimal 100/soal. Kontes dimulai jam 9.00 dan selesai jam 14.05. Ada tambahan waktu 5 menit soalnya waktu kontes berlangsung, sekitar 15 menit terakhir gradernya pending.

3 soal di hari pertama ini adalah: Detecting Molecules, Roller Coaster Railroad, dan Shortcut.

Waktu diberi soal, karena Detecting Molecules ada di halaman pertama, aku baca itu dulu. Singkat cerita, dalam soal itu kita dikasih 1 array yang isinya berat-berat molekul, lower bound, dan upper bound. Kita harus mencari 1 subset apa pun (jika ada) supaya jumlah berat dalam subset yang kita pilih itu berada di range lower bound dan upper bound tersebut. Selain itu juga ada constraint kalau selisih dari upper bound dan lower bound pasti ≥ selisih berat maksimum dan minimum dalam input.

Pikir 5 menit, coret-coret beberapa test case, lihat ada observasi khusus ga, dan sayangnya masih ga dapat ide apa-apa. Terus entah kenapa ada pikiran kaya gini: “Dulu waktu pelatnas bukannya ada soal entah apa yang solusinya value-value dimasukkin ke priority queue, terus kalo melebihi upper bound, tinggal greedy keluarin value yang paling besar aja?”. Tanpa ada pembuktian apapun, aku langsung coba koding seperti ini: untuk setiap berat molekul, aku masukkin priority queue, kalau melebihi upper bound, aku keluarin weight yang paling besar, dan kalau sudah diantara lower bound dan upper bound, langsung return isi priority queuenya. Kalau udah iterasi sampai akhir dan ga ada yang memenuhi, langsung return array kosong.
Submit.
Dapat 19.
Damn.
Mikir lagi, ga ketemu ide lain. Terus baca lagi kodinganku, dan akhirnya baru sadar lupa sorting weightnya dulu. Tambahin sort array input sebelum iterasi array >> submit = 100. YES. AC dalam 20 menit pertama! Awalnya aku ga percaya, bolak balik cek tab submission, dan ada ketakutan tersendiri ada masalah sama test casenya dan di pertengahan lomba bakal diganti terus nilaiku jadi 0 (<< trauma waktu pelatnas), karena aku sama sekali ga punya prove kenapa algoku ini benar (dan kalau belum sadar, akan aku tulis ketololan algoku ini di bawah).

Setelah menghabiskan 5 menit untuk meyakinkan diri soal Detecting Molecules memang benar dapat 100, aku baca soal kedua, yaitu Roller Coaster Railroad. Di soal ini, dalam rel roller coaster, kita diberi n ‘special sections’ yang masing-masing punya batas maksimum awal masuk special section dan kecepatan kereta waktu keluar dari special section tsb. Jadi misal dalam special section ke-i punya batas awal masuk s dan kecepatan waktu keluar t, untuk masuk ke special section ini roller coaster harus punya kecepatan ≤ s, dan waktu keluar dari special section ini roller coaster pasti mempunyai kecepatan t. Di antara special section ini juga ada section ‘biasa’, di mana kalau roller coaster melewati section ini kecepatannya akan berkurang 1 km/h. Jadi tugas kita adalah menyusun n special section tadi supaya panjang total rel roller coaster minimum.
Karena waktu coba subtask paling akhir selama 1 jam aku ga ada ide yang benar, aku coding subtask 1 dan 2 yang constraint n-nya cuma sampai 16, jadi bisa pakai DP bitmask, lalu pindah ke soal ke-3.

Di soal shortcut, kita dikasih N stasiun dan stasiun ke-i dan i-1 dihubungkan dengan rel primer yang memiliki panjang berbeda. Selain itu juga ada rel sekunder yang menghubungkan stasiun di rel primer dengan stasiun baru yang lain, dan untuk setiap stasiun di rel primer hanya ada maksimal 1 rel sekunder. Tugas kita adalah taruh 1 rel shortcut dengan panjang x yang menghubungkan 2 stasiun yang berada di rel primer (jadi pilih 2 diantara N stasiun tersebut), supaya diameter dari graph tersebut minimum. Diameter dari graph adalah jarak terjauh dari setiap pasangan stasiun. Habis baca soal ini, aku ada feeling ini aku pasti tidak bisa dapat full score, jadi strategiku kerja dari subtask paling kecil. Lihat constraint subtask pertama N-nya cuma 10, aku langsung koding solusinya: brute force pasangan yang dipilih, lalu untuk setiap kemungkinan cari diameternya. Terus aku coba pikir untuk subtask 2 yang N-nya sampai 100 dan observasi trivial sebelum dikasih rel shortcut pasti bentuk graph-nya tree. Sayangnya karena aku tidak ingat observasi apa saja waktu di sana, dan ternyata aku salah copy solusi untuk dibawa pulang setelah lomba, aku ga ingat solusiku untuk subtask 2 bagaimana (maaf 😥 ). Tapi kalau tidak salah ada LCA-nya.

Setelah receh di soal B dan C, aku alternate kerja B dan C: sekitar 30-50 menit kerja di B, terus pindah ke C, dst. Entah ini strategi yang baik atau tidak, tapi setelah dapat nilai yang di atas itu, sampai akhir kontes nilaku tidak bertambah lagi :’)

~end of contest~

Note: fyi, di IOI scoreboard peserta dibuka ke publik secara online (tapi peserta waktu lomba tidak bisa lihat) dan ada range-range medali emas – perunggu, jadi waktu lomba jika ada orang tua/umum yang mau lihat scoreboard dan ingin tahu peserta X di range medali apa dan dapat poin berapa bisa lihat di webnya. Terbuka banget kan? Jadi olimpiade komputer terjamin banget kredibilitas, kejujuran, dan keaslian nilainya karena setiap kali peserta submit jawabannya bisa langsung dilihat semua poin yang didapat berapa dan yang cek jawaban peserta itu mesin, *cough*ga kaya mapel lain*cough* (<< i'm just joking. please don't take this too seriously 😀 ). Peserta hanya bisa lihat scoreboard ini setelah kontes.

Di hari pertama ini, aku dapat nilai total 157/300, dan berada di peringkat 74 (posisi perak), Lung Sin di range perunggu, Ucup dan Sergio di range no medal.

Malamnya sebenarnya ada ekskursi ke Kazan Kremlin yang menurut fotonya bagus banget, tapi karena udah capek dan mau simpan energi buat kontes day 2, aku ga ikut pergi, dan ternyata cowo-cowo yang lain juga ga ikut juga.

screen-shot-2016-11-08-at-10-12-38-am

Kazan Kremlin. Photo taken from ioi2016.ru

Ketololan algo Detecting Molecules-ku:
Waktu selesai lomba, aku baru sadar. Itu array weight setelah di-sort, buat apa dimasukkin ke priority queue lagi =w=’

Day 4 – (Not) Sport Excursion & Sabantui Festival

Di pagi hari keempat ini sebenarnya ada Sport Excursion, tapi karena waktu pertama kali lihat jadwal dan melihat kata ””sport”” di sana aku udah anti banget, jadi aku ga ikut ekskursi di pagi ini (yang cowo tim indo juga ga ada yang ikut lol). Dan setelah acara itu selesai aku baru diberi tahu kalau “sport excursion” sebenarnya ga ada olahraganya sama sekali, tapi cuma mengunjungi tempatnya doang.

sanbantui

Sanbantui Festival. Photo taken from ioi2016.ru

Terus sekitar jam 2, kita pergi ke Sabantui Festival, yang ternyata tempatnya cuma di depan gedung kontesnya doang. Di sana udah banyak kaya pos-pos game tradisionalnya Russia, yang beberapa mirip sama mainan tradisionalnya Indo, kaya lomba balap karung, lomba lari tim 2 orang yang salah satu kakinya diikat, terus kalau ga salah ada yang kaya lomba balap kuda lumping juga. Kalau menang bakal dikasih beberapa tiket, kalau kalah juga dikasih tapi jumlahnya lebih sedikit. Di akhir acaranya, peserta yang punya tiket paling banyak bakal dapat suvenir gitu. Di acara ini aku cuman ikut lomba balap yang kakinya diiket itu sama Bu Inge, terus kalo yang cowo ikut lomba balap pikul ember penuh air, terus lomba yang mirip whack the watermelon tapi watermelonnya diganti pot tanah liat, dan beberapa mainan lainnya. Waktu festival itu kita juga dikenalkan sama mahasiswa Indonesia yang berkuliah di Kazan Federal University (host IOI tahun ini). Setelah itu harusnya makan malam, tapi tim Indonesia sama Pak Fauzan diajak pergi ke salah satu supermarket untuk beli oleh-oleh, di mana aku beli sekitar 3 kg cokelat yang surprisingly total harganya cuma 100 ribuan rupiah saja. Malam harinya diisi karantina, sama seperti day 2.

~To Be Continued~

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s