OSN 2014 : Contest Days

*Sebenarnya karena suatu alasan saya inginnya nulis ini setelah soalnya dimasukin ke TLC, tapi yasudah biarin aja deh :v

So, day 1 has arrived! Paginya saya terbangun seperti biasa ketika bepergian. Funny things, jam di tubuh saya berbeda ketika di Bontang dan ketika bepergian. Ketika bepergian, pagi adalah jam 5 waktu setempat. Pas di Bontang, pagi adalah saat saya bisa bangun, silahkan diterka kira-kira jam berapa :v

Setelah sudah siap, sekitar jam setengah 7 saya gedor kamar Agus, ngajak sarapan, dan karena takut dengan recordnya Agus yang sering sulit bangun pagi pas Pelatnas. Untungnya, mereka udah pada bangun, dan Agus katanya bangun jam 4 :O Habis itu makan, terus leyeh-leyeh sampe udah deket sama waktu mau dimulai, baru cabut ke tempat kontes yang ada di hotel juga (yeah, cuma komputer keknya yang gak cabut ke mana-mana..)

Habis itu pembagian ruangan. Saya kedapetan di ruang paling kiri (lupa Gili air/meno/trawangan namanya). Depan Wynne, temen Pelatnas tahun lalu, kiri Anab, temen sekamar. Kanan.. gak merhatiin, udah beda meja. Siap-siapin beberapa hal, berdoa, lalu kontes dimulai! Soal-soalnya:

1. Pelontar Bebek (DP + Greedy Observation)
2. Reduksi String (Prefix Sum / Compress + Binary Search)
3. Perang Dunia Ketiga (Brute Force + Prefix Sum)
4. Cat Rumah (Kreatif)

Strategi saya masih sama seperti biasa : baca soal, baru coba serang soal yang paling mudah dulu berdasar intuisi. Setelah baca semua soal (dan cuma gagal mahamin Cat Rumah), saya yakin kalau Reduksi String soal easy hari ini. Setelah ngoding beberapa saat, tes dengan TC sample dan.. hasilnya salah. Ouch, ada case yang kelupaan. Habis diedit, 100

Setelah itu, saya coba lari ke Pelontar Bebek. Awalnya, saya kira itu soal semacam geometri gak jelas (trauma dengan sin dan cos). Setelah saya pikir lagi, sebenarnya kita bisa melakukan seperti ini : sort dulu berdasarkan V, lalu kita iterasi semua kemungkinan. Untuk setiap indeks, lakukan DP knapsack pada sudutnya agar dicapai hasil abs(sin*cos) yang maksimal. Solusi ini cukup untuk dapet 79, saya masih tidak dapat ide agar dapat subtask terakhir.

Habis itu, karena soal kreatifnya bukan output-only yang kadang butuh waktu ekstra, saya nyoba kerjain Perang Dunia Ketiga. Saya sadar kalau untuk mempersingkat, kita bisa menggunakan semua bilangan ganjil saja untuk dasarnya. Tapi, saya gak dapat ide untuk mereducenya lagi. Alhasil, saya code brute-forcenya dulu yang cuma dapat 53. Setelah itu iseng nyoba ternary search, dapet cuma 7. Pas dicek, baru nyadar kalo bentuk fungsinya gak bisa diternary search :| Firasat saya ada hubungannya sama prefix sum, cuma gak saya pikir lebih lanjut lagi.

Daripada nganggur, saya nyoba ngerjain soal Cat Rumah. Awalnya, butuh waktu yang cukup lama untuk ngerti cara kerja soalnya :| karena gak kepikiran solusi yang cukup baik, saya bergantung pada The Greatest Force in The Universe : Luck. Saya cuma ngerandom warna, selalu nambahin dengan kuantitas 10, dan pindah warna kalau hasilnya menurun. Solusi ginian dapet 57 entah bagaimana caranya :|

Dengan menipisnya waktu, saya tahu kalau saya bakal sulit nambah poin di Cat Rumah. Alhasil saya gonta-ganti mikir di Pelontar Bebek dan Perang Dunia Ketiga. Di saat-saat akhir saya mau nyoba sesuatu yang rada haram di Pelontar Bebek. Dan hasilnya.. 45 :p Setelah itu kontes day 1 berakhir.

Pas keluar, pada ramai ngerubungin TV yang ada di luar ruang sidang kontes. Ow, ada scoreboard sebelum difreeze :

Look mom, i was in the first place

Habis itu ngobrol sama Agus, katanya scorenya habis freeze > 300 :| terus kami makan. Pas makan, Agus ngejelasin kalo ada observasi yang bisa ngereduce kompleksitas di Pelontar Bebek secara drastis :| Dan yang membuat saya sedikit kecewa adalah, observasi itu sebenernya you-don't-say kalo dipikir :| Tapi yaudahlah. Karena habis itu free time, saya main ke kamarnya Agus, sambil ngeliat kalau anak DKI ada ngumpul dulu di tempat lain untuk "ditebas". Terus saya main DoTA sama Agus. Habis main, saya ada mikir kalo score saya masih belum aman untuk target saya. Tapi ya udahlah, mending main lagi :v

Habis itu MW ada main ke kamarnya Agus, diajak main, gak mau, mungkin pengaruh "ditebas" ._. Anyway, malam itu berlalu kayak biasa, yang beda cuma mood makan saya semakin menurun ._. Selesai itu, balik ke kamar, terus istirahat buat besoknya.

Besoknya, setelah siap-siap, jam setengah 6 saya ke kamarnya Agus, buat sekalian ngecharge HP di situ karena saya lebih sering di kamarnya daripada kamar saya sendiri ._. Saya pikir aman aja, soalnya kemaren Agus bangun jam 4 pagi. Ternyata salah. Masih pada tewas semua, dan saya dikira gila karena datang kepagian, maaf cuy ._. Terus sementara mereka ngumpulin nyawa, saya nyoba mikir Perang Dunia Ketiga. Pas saya ngerasa dapet solusi yang dapet subtask n <= 10^5, Ervin cerita kalo MW AC soal itu. Idenya Brute Force pake dasar bilangan ganjil sama prefix sum. Setelah saya pikir lagi, emang bener cara gitu kompleksitasnya O(MAXX log MAXX) (My bad, harusnya O(MAXX) ), yang masih cukup buat MAXX=10^6, dan dapet 100. Kecewa^2.

Habis makan, leyeh-leyeh, cabut ke tempat kontes. Pas pembagian ruangan, awalnya nyantai-nyantai aja. Terus selesai pembagian ruangan ke-2, udah terasa gak enak. Saya, Agus, MW seruangan. Belum lagi yang sangar-sangar pas day 1 juga di ruangan ke-3. Aura perangnya kerasa banget bakalan. Anyway, depan saya.. lupa. Kanan tembok. Kiri Jonathan anak DKI. Persiapan, lalu kontes dimulai! Soal-soalnya :

1. Komunikasi Bebek (DP,but somehow my BF passed)
2. Suten (Interactive, berhubungan dengan tree)
3. Sang Pelompat (Flood Fill + BFS)
4. Hiasan Dinding (DP k-th lexicographical, combinatorics)

Seperti biasa, baca soal. Saya tidak ada masalah dengan deskripsinya, jadi langsung aja ngerjain Sang Pelompat, yang menurut saya cukup straight-forward. Awalnya ada 2 hal yang saya takutkan : banyak set batu dan apakah hartanya pasti cuma 1. Untuk hal pertama ternyata saya kurang teliti membaca, terus untuk hal kedua.. YOLO. Submit dulu baru kalo kenapa-napa nanya. Untungnya sih gak ada, 100.

Habis itu saya nyoba ngerjain Suten. Mikir bentar, saya dapet observasi yang menurut saya kritis : kita bisa buat banyak set yang isinya 3 kelompok, yang menunjukkan relasi menang-kalah melalui cycle. Setelah itu, pass hanya akan kita lakukan jika yang ditanya berada di 2 set berbeda. Jika itu terjadi, maka setelah pass kita merge kedua set itu tergantung hasil dari judge. Selain itu, maka kita pasti tahu hasil pertandingannya melalui posisi mereka di cycle. Karena lagi pengen keren, saya ngoding disjoint-set. Terus ngebug, dapet 47. Karena bingung ngebug di mana, akhirnya saya lepas disjoint-set, jadi pake vector dan mergenya O(N). Ngebug lagi. Habis ngutak-ngatik di mana-mana, bug pun bermunculan satu demi satu. Terus dapet 59 di disjoint-set. Sudah desperate, saya perbaikin yang versi vector. Alhamdulillah, 100. Tapi ini sudah membuang waktu saya selama 2 jam :'( Btw, saya gak ngeprove dulu lo sebelumnya kalo cara ini paling optimal, untungnya AC ._.v

Otak saya panas setelah ngerjain Suten. Habis itu saya nyoba Komunikasi Bebek. Karena masih pusing dan niat ngais poin dulu, jadi saya bikin BF yang bener-bener BF. Kompleksitasnya sekitaran O(N * 5000 log 5000). Expectednya bisa sampe subtask kedua terakhir lah. Terus pas submit, dapet 0. Bingung kenapa, saya download (for the first time!) subtask yang bisa didownload. Pas ngeliat, oh, ternyata emang ada yang salah. Habis dibenahin, submit lagi. Udah gak terlalu expect bagus juga sih. Pas ditoken, 100! :O Ini saya yang salah ngitung kompleksitas atau TC yang kurang kuat? :|

Habis itu, daripada nganggur saya mikir untuk soal Hiasan Dinding. Pas baca, saya tahu kalau ini bakal jadi decider problemnya day 2. Untuk nyari banyaknya ordering, saya tahu kalau bisa menggunakan dp :
dp(now) = dp(now->left) * dp(now->right) * (size_now)C(size_now->left)
*Mungkin saya harusnya pakai LaTeX..
 Tapi, saya masih tidak punya ide menggunakannya pada soal ini. Alhasil, saya ngais 49 poin dulu, untuk k=1 dan n<=8. Setelah itu, saya mikir, karena gak dapet secara matematis saya cari polanya. Kemudian saya dapet sesuatu yang gak jelas, yang sesuai sama pattern kecil yang saya buat. Tapi waktunya udah tipis. Terus diumumin kalo ada extra time gara-gara judge bermasalah. Jadinya saya buru-buru ngoding, tapi hasilnya tetep nihil :| meanwhile, 10 menit terakhir :

Agus menghembuskan nafas, angkat tangan.
Agus ke WC.
Balik main Minesweeper.
Kampret, pasti udah 400.

Setelah itu, day 2 berakhir! Saya sudah tidak terlalu memikirkan lagi masalah poin, toh udah gak bisa diubah. Seperti biasa, peserta langsung ngerubungin TV :

Look mom, i was in the first place again

Note : scoreboard day 2 masih bisa diakses di sini

Setelah itu, seperti dibilang sebelumnya, mau ada TOKI Gathering, jadi kami disuruh siap-siap dulu. Mengenai TOKI Gathering dan Excursion bakal saya tulis di post selanjutnya :v

Some random fact :

• Jika tidak ada extra time, maka posisi saya,MW, dan Agus ditentukan oleh score day 1.
• Selama 3 hari, saya seruangan sama Agus. Jodoh.
• Nampaknya soal Sang Pelompat banyak menjebak DFS user.
• Solusi random Agus untuk Cat Rumah menggenerate warna secara random, jumlah random, dan punya batas tertentu di mana programnya bakal berhenti. Selain itu, seednya menggunakan namanya. Terus dapet 77.
• Komunikasi Bebek mungkin soal kedua yang Irvin set yang saya jebol dengan cara tak diharapkan :p
• Capek, frustrasi membuat otak tidak jelas. File Komunikasi Bebek saya save komunis.cpp :v 
• First place pada scoreboard sebelum freeze membuat saya merasa seperti artis, walau saya tahu tiap difreeze saya digusur :v
• Jika kontesnya 4 jam mungkin saya yang menang, tapi masih ada banyak faktor lain sih :v
• Karena masalah freeze, orang di Bontang mengira saya sudah rank 1. Padahal, itu sebelum freeze.
• Saya suka dengan problemset tahun ini. Distribusi difficultynya sudah lumayan bagus, tapi kayaknya masih mengikuti pola tahun sebelumnya, di mana day 2 nampaknya lebih sulit dari day 1, bahkan untuk ngereceh :|
• Behubungan dengan di atas, saya senang dengan Pelontar Bebek dan Perang Dunia Ketiga. Untuk mendapat 100, diperlukan observasi tambahan yang masing-masing sebenarnya tidak terlalu ribet, tapi ya saya sendiri gak AC sih :|
• Soal favorit saya Suten. Format soal yang berbentuk game menurut saya sangat jauh dengan dasar pemikiran solusinya yang dihubungkan dengan graph, dan walaupun menyiksa saya, menurut saya soalnya tetap paling menyenangkan :v

Fact di atas bisa berubah sewaktu-waktu, kalau ternyata ada yang kurang tepat atau ada sesuatu yang saya ingat :p Btw, jika nanti ada yang ingin ditanyakan mengenai soalnya, bisa ditanya di ask.fm saya, selain Hiasan Dinding dan Cat Rumah Insya Allah bisa saya jawab. Sebenarnya udah diceritain solusi Hiasan Dinding sama Agus, cuma mau saya tes dulu ntar :p