Pak Dengklek Cari Masalah Di Palembang (OSN 2016) (Part 1)

Halo semuanya pembaca setia blog ini (ditujukan ke tidak ada) . Setelah sekian lama blog ini tidak pernah diapdet karena emang gk tau apa yang harus di apdet akhirnya saya memutuskan untuk kembali mengapdet blog ini. Mumupung osn baru sekitaran 2 minggu yang lalu jadi masih banyak yang hal teringat. Dan untuk post ini sendiri , saya bingung antara harus menulis persiapan saya sebelum OSN atau langsung menulis pengalaman saya di OSN taun ini dan akhirnya keputusan saya adalah memilih langsung menulis pengalaman saya di OSN taun ini karena malas ngetik panjang panjang :v . Saya juga lagi belajar membuat tulisan blog yang enak dibaca . Silahkan dinikmati ceritanya :) kalo ada kesalahan dan kekurangan pada tulisan kali ini , maafkan la .

OSN 2016 Day 1 (15 Mei 2016)


Pesawat ke Palembang berangkat jam 5an . Kami disuruh kumpul di hotel tempat panitia menginap sekitar jam 12 siang . Pas tiba di sana dikasih uang buat OSP yang menurut saya lumayan gede (?) (saya gk tau uang OSP prov lain berapa) . Diberi baju batik daerah kami dll. Yang kumpul di hotel sana cuma 7 orang dari 12 orang , 4 orang udh di Palembang (miss communication) , 1 orang malah gk diboleh pergi ama orangtuanya (kasiah banget :' , masa osn gk dibolehin pergi).  Tiba di bandara dan saat penungguan pesawat datang , kami liat  di ruang tunggu kok ada anak riau. Kami bingung, dan ak kira mungkin anak kepri (?) tapi kok tulisannya Riau , dan beberapa hari setelahnya ak baru tau kalo ternyataa gk ada pesawat dari Riau Ke Palembang jadi harus transit lewat Batam dulu..


Tiba di Palembang sekitar jam 6 an . Udh malam dan sampai disana dapat kabar kalo anak kontingan Bali juga baru tiba disana . Niatnya kucariin tapi mereka udh duluan pergi. Setelah ngambil bagasi , kami nyari bus dan nunggu lumayan lama sih karna emang banyak yang nunggu. Setelah dapat bus kami langsung menuju Hotel dengan urutan  Hotel Grand Duta -> Hotel Duta Syariah -> Hotel Daira (hotel anak komp) -> Hotel Imara.

Pas tiba di Hotel Grand Duta , Mataku dengan autofokusnya meliat ada KFC di seberang jalan , padahal perasaan taun lalu Hotel anak Math dekat dengan KFC , taun ini masih aja dekat dengan KFC lagi :' .

Tiba di Hotel Daira , langsung melakukan registrasi disana , dan ternyata anak kontingen bali juga sudah pada sampai. Setelah Registrasi , dapat Tas yang kata banyak orang itu tas cewek (?) . Dan juga nametagnya semuanya warna kuning . Yang membedakan hanya  tali pada nametagnya. Setelah itu ngambil kamar dapat kamar 702 , kamar taun ini gk bisa dipilih , jadi tiap kontingen pun pisah orang orangnya , dan 1 kamar jadi 3 orang . Aku sekamar dengan Rozaqi (Jateng) dan Mahfi (NTB) . Ak tiba di kamar itu sekitaran jam 8 setelah makan malam yang enak (?) (salah satu tujuan ikut OSN adalah makan enak :v) . Dan akhirnya setelah mandi , aku memilih tidur .


OSN 2016 Day 2 (16 Mei 2016)
Hari ini pake baju batik daerah untuk pembukaan OSN 2016. Aku bangun lumayan telat , kalo gk salah jam 6 udh harus makan semestinya , tapi ak bangun sekitar 6.20 dan siap mandi dll steleah 6.40 , ternyata ada yang lebih telat dari ak jadi ya gpp menurutku dan juga busnya jam 7 baru berangkat.

Setelah tiba di PSCC (Palembang sport & convention center) yang menjadi tempat pembukaan serta tempat penutupan OSN 2016 , kami disuruh duduk berdasarkan bidang , dan tiap bidang dapat tribun masing-masing. Tapi pada akhirnya ak campur ama anak kepri (atau lebih tepatnya mereka campur ama aku , karna ak duduk di bagian komp). Sebelah kiriku itu anak DKI , M. Fairuzi T. Untuk pembukaan taun ini menurutku lumayan buruk sih . Gk ada Dokumenter Rekam Jejak. Dan tribun tribunnya kasian , agak susah liatnya . Yang menurutku kerennya yaitu pas pembukaan secara resminya lumayan keren , keren karna alaynya :v , ceritanya Pak Anies dkk disuruh menempelkan jarinya pada suatu layar yang disediakan , kayak mau mengaktifakn nuklir dengan menempalkan tangan di layar (kayak yang di pilem pilem barat itu) lalu di layar panggung (layar yang ditujukan untuk penonton) di buat alay alay seperti suatu data yang sedang melewati kabel kabel dan keluarlah Tulisan OSN 2016.


Setelah Pembukaan , Anak Bidang Komp disuruh ke bus untuk dilanjutkan ke tempat tes dimana taun ini bertempat di Kampus MDP , disana disambut dengan sangat baik . Untuk awalnya kami diberikan sesi briefing + tanya jawab .Salah satu pertanyaan saya adalah. "Apakah ada Soal Kreatif Untuk Taun ini ? " Jawabannya adalah , "Tidak Tau." Setelah itu kami dibagikan ruangan, untuk taun ini ak dapat ruang pertama, yeee.... karna menurutku aku pembagian ruang itu sepertinya ditujukan pada skorbord.. dan entah kenaap day 0 kok bisa dapat ruang 1 :' , nomor meja 12,  Sesi day 0 kali ini agak berbeda dengan taun lalu dimana diberikan 4 soal , soal 1 itu soal bonus yaitu "Halo Dunia!"

Jadi untuk sesi day 0 , kita hanya bisa mengerjakan soal satu persatu jadi pertama kita cuma bisa kerjakan soal Halo dunia untuk mengecek apakah bisa disubmit atau tidak . Setelah beberap menit soal kedua diunlock Gunting kertas baru soal ketiga (lupa judulnya mungkin ada yang mau ingatin) soal ke 4 empek empek.


Kurang lebih urutannya

Pertama Kerjakan Soal Halo Dunia , langsung ac -__- , lalu karna soal ke2 masih ke lock , jadi ak coba ngetest banyak operasi 1 detik (Dan kalo gk salah cek) 1 detik > 10^9 operasi. entah ak salah ngecek atau gmana kok kaykanya besar banget ya :'v .

Setelah itu , soal ke 2 telah di buka... Ini soal interaktif judulnya "Gunting Kertas" inti dari soal ini
dikasih kertas yang teridiri dari N x M kotak , tiap putaran kita dapat menggunting kertas menjadi
A x M atau jadi N x B (dimana 1 <= A < N , dan 1 <= B < M) dan siapa yang memotong kertas menjadi 1 x 1 duluan dialah pemenangnya.. (Input yang diberikan selalu memiliki solusi)  Mikir soal ini sekitar setengah jam dan akhirnya ketemu idenya kalo kita harus mengubahnya menjadi NxN (jika M > N) dan M x M (jika M < N) , submit ac ,ternyata soal ketiga belum ke unlock jadi ak cari minesweeper dlu dan ternyata gk ada :'(

Mana janji manisnya kak (?) :(

Karena gk ada Minesweeper maka ak coba liat soal C dan D bikin codenya dlu baru entar di submit pas udh bisa di submit , saat itu kalo gk salah , id tlx dikasih yang baru karna ada yang gk bsa login ,

Soal C soal output only
diberikan Matriks NxM , NxM matriks itu diisi dengan (NxM)/2 angka 1 dan (NxM)/2 angka 0 lalu di kasih N buah bilangan yang merupakan hasil XOR dari setiap bilangan yang ada di baris tersebut dan M buah blangan yang merupakan Hasil XOR dari setiap bilangan yang ada  di kolom tersebut.. Saya kepikiran bruteforce dan langsung saja saya buat ..

Soal D Soal Empek Empek

Soal ini diberikan 1string yang terdiri dari bilangan 1,2,3 , untuk tentukan banyaknya kemungkinan pempek yang harus dibeli kalo pempek 1 harus dibeli sebelum pempek 2 dan pempek2 harus dibeli sebelum pempek 3

contoh TC kalo kurang jelas
In

7

1121332
Out
4
Penjelasan
    Toko ke-1, toko ke-3, lalu toko ke-5.

    Toko ke-1, toko ke-3, lalu toko ke-6.

    Toko ke-2, toko ke-3, lalu toko ke-5.

    Toko ke-2, toko ke-3, lalu toko ke-6.

Pertama kali liat soal ini kirain dp , tapi setelah mikir mikir ternyata ini soal preffix sum(Eh... prefix itu termasuk dp ya ? )  dan langsung aja saya koding , dan AC... Prefixnya itu pertama cari kalo misalnya ada pempek jenis 2 maka ada berapa pempek jenis 3 di belakang pempek jenis 2 ,itu di prefix kan  , lalu untuk setiap pempek jenis 1 cek ada berapa banyak pempek jenis jenis 3 dibelakangnya dengan cara setiap ketemu pempek jenis 2 maka tinggal ditambah aja ada berapa pempek jenis 3 saat itu

Contoh
1121332
Prefix1(buat nyari ada berapa angka3) setelah angka 2
2220000
Prefix2 (buat nyari ada berapa angka3) setelah angka1
2200000
baru tinggal dijumlahkan setiap yang ada angka 1
2+2+0 = 4

Setelah soal 3 bisa kebuka , ak baru sadar kalo ternyata salah ngitung kompleksitas ,  jadi soal C gk dapat 2 subtask terakhir , tapi bisa di manual hingga akhirnya daapt 87
dan saat soal D kebuka akhirnya AC

mau nyoba cari soal c dengan manual ternyata gk sempat ya. (padahal awalnya nyari minesweeper ,sekarang malah gk sempat :v )

Scoreboard Day 0 , abaikan Messengernya :v

 Sama Seperti taun sebelumnya , dapat nilai tertinggi setelah fullscore :', kutunga Fullscore tetap menghantuiku . Setelah itu ak tanya mereka AC in soal C gmana , ada yang bilang manual , dan ada yang bilang juga pake random cuma ak masih belum ngerti random :v .
Setelah itu tiba di hotel makan dan tidur..

OSN 2016 Day 3 (17 Mei 2016)
Hari Ini day 1 nya OSN Komp , dan semestinya juga semua bidang.. Setelah tiba di kampus , aku dapat urutan kursi no 7 ,dan itu letaknya tepat di depan kursi no 12 . Langsung saja tanpa basa basi ke soalnya.

List Soal
Pasar 16 Ilir (Recursive backtracking + binser (?))
Menjinakkan Bom (interaktif)
Pos Wisata Sungai (ada subsoal yang pake DP dan ada yang pake Math)

Pertama liat soal 16Ilir keliatan susah , jadi diskip langsung ke soal B yang interaktif , dan kayaknya seru.. Setelah memainkan gamenya dapat subtask 1 ama 2 , mikir lalu tau kalo subtask 3 nya itu bruteforce , di game yang diberikan ternyata di bagian coba cobanya ada kesalahan jadi sambil menunggu bagian itu diperbaiki , ak liat soal C , dan keliatannya soal susah make karna ada Xor  Xornya . Coba ngebruteforce soal A dan ternyata dapat 78 Poin , aku kirain gk bakal dapat sebanyak itu.. Lalu lanjut soal b karena ternyata coba cobanya telah difix . Akhirnya ak kepikiran solusi Untuk soal b untuk subsoal yang R = 0. Dengan Math (?)

solusinya
 menekan tombol dari 1 Sampai N , dimana tombol akan  berbunyi pada saat X+K = A
lalu menekan tombol dari N Sampai 1 dimana tombol akan berbunyi (diitung sejak bilangan N pertama dipencent menuju ke 1 ) setelah N-1-a +k =  B (kalo gk salah)

diturunkan dengan eliminasi menjadi
2X  =   A - ( B - (N+1) )
dapat X baru X ditekan terus menerus hingga bom berahasil dijinakkan

Beralih Ke Soal C

Mikir mikir akhirnya sadar kalo ini adalah fungsi perpangkatan

Jadi Setiap langkah Selain menuju ke final itu merupakan hasil dari kombinasi (M,0) +... (M,M) dipankat N-1 baru dikali kombinasi (M,K)

tapi awalanya ak belum mikir mathnya dan hanya kepikiran menggunakan segitiga pascal untuk menyetor hasil hasil kombinasinya ...

Setelah itu tembus sebelum 2 subtask terakhir karna emang algoku m^2 ... dan akhirnya waktu sisa 1 jam scoreboard udh di freeze dan akhirnya ketemu rumus sebenarnya yaitu

((2^M)^N-1) * Kombinasi (M,K)  , dimana karna K <= 2 maka dimanualkan aja untuk pembagiannya (ini sebenarnya ak ada ngebug karna ak lupa kalo kali  dlu baru mod baru bagi baru mod dan ternyata gk bsa harus pake Modular Multiplicative Inverse.. ) jadi aku manualkan , misalnya M %2  == 0 maka m/2 , (M-1) % 3 == 0 maka M-1 dibagi 3 baru akhrinya dikali , M* M-1 * M-2 dan setelah itu AC

dan waktu berakhirr

Skorbord day 1saat di freeze  , sori kalo gk jelas , bisa di cek di OSN2016.ia-toki.org

 
Setelah itu kami dikumpulkan untuk penjelasan akhirnya ak baru sadar kalo A itu tinggal di binser , aku lewatin A karna ak sendiri kaget kenapa gk tle jadi gk berani ku otak atik lagi... dan katanya ada suatu saat scoreboardnya gk ke freeze , alias freeze lepas dan ternyata ak peringkat 6 saat freezenya dipelas :' .. lumayan la..