August 2016

Beberapa waktu yang lalu, saya menyempatkan diri untuk ikut BNPCHS 2016. BNPCHS adalah singkatan dari Bina Nusantara Programming Contest for High School. Sesuai namanya, itu adalah sebuah kompetisi pemrograman untuk anak sekolah tingkat SMA yang diadakan oleh Binus University. Di tulisan kali ini saya akan memflashback / merecount pengalaman saya mengikuti BNPCHS tersebut.

Babak Penyisihan dilaksanakan tanggal 24 Juli 2016. Babak ini terdiri dari 5 soal, dengan waktu 4 jam, mulai jam 1 siang dan selesai jam 4 siang. Hanya sedikit yang saya ingat disini, yaitu saya telat mengerjakan soal karena mengira babak penyisihan di mulai jam 2. Lainnya seperti biasa, tidak ada yang menarik untuk diceritakan. Skip……… singkat cerita saya terpilih menjadi 70 peserta yang akan menjalani babak final di Kampus Anggrek Binus University.

Minggu, 8 Agustus 2014, saya bersama teman sekolah saya, berangkat pagi-pagi sekali dari Stasiun Depok Baru sekitar pukul 6.30 pagi. Berdasarkan google maps,waktu tempuh kami ke tempat tujuan adalah 1 jam 37 menit. Maka, kami tenang-tenang saja karena pendaftaran ulangnya masih dibuka sampai jam 8.30. Sampai di St. Manggarai, kami berpindah kereta ke kereta bertujuan akhir Tanah Abang. Di St. Manggarai, suasana yang saya kira akan sedikit sepi pada hari Minggu tidak terjadi. Jika pada hari kerja akan diisi oleh para pengejar gaji, maka pada hari Sabtu atau Minggu seperti ini, stasiun transit kereta terbesar di Jakarta ini didominasi oleh ibu-ibu yang bertujuan tidak lain adalah berbelanja Tanah Abang. Setelah menunggu sekitar 10 menit, akhirnya kereta yang ditunggu datang juga. Perjalanan dari Manggara ke Tanah Abang hanya melewati dua stasiun ( Sudirman dan Karet), lalu sekitar jam 7.55 kami pun sampai di Stasiun Tanah Abang.

Kampus Anggrek yang dituju.
Source : https://upload.wikimedia.org/wikipedia/commons/8/85/Anggrek_Campus_-_Bina_Nusantara_University.JPG

Suasana Minggu pagi di Tanah Abang, sedikit ramai, namun tetap proporsional. Saya pun melanjutkan perjalanan dengan angkot M11 jurusan Meruya-Tanah Abang. Ternyata jalanan agak macet karena harus melewati dua pasar. Jam tangan saya telah menunjukkan pukul 8.18. Hal ini ditambah buruk oleh munculnya penampakan SPBU di sebelah kiri angkot. Supir angkot saya pun langsung menggerakkan kemudi ke arah kiri dan angkot berhenti untuk mengisi bahan bakarnya. Jam menunjukkan pukul 8.24. Setelah sekitar 3 menit, angkot melanjutkan perjalanan. Saya sampai di tujuan pukul 8. 40. Segala pikiran buruk telah berkumpul di otak saya. Bagaimana jika pendaftaran ulang ditutup? Untuk apa perjalanan ini? Namun, pihak panitia memberikan toleransi untuk keterlambatan ini. Huhhhh… Lalu saya pun masuk ke hall utama tempat acara saat itu ( sambutan) berlangsung.

Pelajaran 1 : Saat acara sambutan berlangsung, diakhir sambutan tersebut panitia penyelenggara meminta para hadirin untuk berdiri untuk membaca doa sebelum kompetisi. Melihat semua competitor berdiri, saya pun ikut melakukannya. Namun, karena mayoritas di sini bukan Muslim, doa pun dilakukan bukan sebagaimana saya atau teman-teman Muslim berdoa. Saya pun sempat bingung duduk-berdiri-duduk lagi-berdiri lagi-duduk. Melihat beberapa peserta perempuan berjilbab duduk agak lama, saya pun ikut duduk. Saya mempelajari satu hal penting, begini toh rasanya jadi minoritas.

Sekitar pukul 9.20 para finalist sudah memasuki ruangan perlombaan. Pikiran pertama untuk ruangan ini adalah ….. dingiin… Di meja saya, telah disediakan komputer beserta perangkat pheriperalnya, kertas putih 2 lembar, serta amplop coklat berisi berkas soal yang saya kira berisi sertifikat finalis. Lalu diadakan sesi pemanasan. Sesi pemanasan atau warming up session ialah sesi yang dapat digunakan oleh semua peserta untuk mengecek spesifikasi komputer, berapa operasi perdetik, dan mengetahui lebih jauh environment komputer.

Suasana Ruang Kompetisi BNPCHS

Jam 10.00 kompetisi yang sebenarnya dimulai. Ada 10 soal yang tersedia dengan waktu mengerjakan 5 jam. Para peserta mulai mengerjakan soal. Saya pun mulai membuka amplop coklat tersebut dan mulai memilih soal.

Menggunakan prinsip “Cari soal dengan ilustrasi terpendek, variable tersedikit” pilihan soal atau problem pertama saya jatuh pada problem I, “Membagi Permen”. Vina punya M permen, dia pingin membagikan M permen tersebut secara merata ke semua orang. Setelah dia bagi, ternyata bersisi N permen. Cari berapa jumlah kemunginan orangnya yang dibagikan. Solusinya adalah “banyak factor dari (M-N)”. Karena waktu masih sangat panjang, saya ingin bereksperimen sedikit, pure brute force. “for (i=1; i<=M; i++) if (M % i==N) ans++;. Ternyata nembus, AC. Aneh. LOL. -_-

Problem kedua yang saya kerjakan, F, “Utak Atik Lampu”. Rumah Sitomo memiliki N lampu. Ada saklar aneh, yang kalau di tekan pada hari ke-i, bakal invers-in(matiin atau hidupin) lampu-lampu pada kelipatan ke-i. Pertanyaan, berapa lampu yang hidup pada hari ke-X? Solusinya adalah banyak bilangan dari 1 sampai N yang punya factor dari 1 sampai X yang banyaknya ganjil. Skip. AC.

Problem berikutnya, A, “Lama Menonton”. Jingga nonton streaming dari pukul AA:BB. Format 24 jam. Namun, karena buffer ia harus menunggu selama Y menit, sebelum bisa menonton selama X menit. Hal ini terus berulang selama durasi film tersebut. Proses buffer tidak terjadi pada X menit pertama. Pertanyaan, berapa lama Jingga menonton termasuk proses buffer yang dialaminya? Cukup simulasikan prosesnya aja. Sekaligus tau cara mengubah dari format jam ke menit. Ingat, 24 jam = 1440 menit. Jadi, mulainya jam 23:59 dan lama prosesnya 5 menit, ya harus di mod 1440 dulu. Hal, yang agak menjengkelkan di sini saya bermasalah waktu ngehandle input yang ada “:” (titik duanya). Tapi, tidak terlalu lama. AC.

Jam menunjukkan pukul 13:00. Setelah menyelasaikan 3 soal ini, saya melihat scoreboard. Ternyata masih jauh di peringkat 21. Namun, melihat penalty yang saya terima agak sedikit dibanding beberapa orang yang sudah AC 4, membuat semangat untuk menembus minimal peringkat 10. Malangnya, petaka konyol pun dimulai.

Sedang berpikir(?)

Problem H, “Lucky Sequence”. Permainan Lucky Draw, sejenis Super Deal 2 Miliar yang sempat ada di salah satu stasiun televise Indonesia. Terdapat N buah kotak, 1,2,3, sampai N. Setiap kotak dapat berisi hadiah yang ditandai dengan 1, ataupun 0 yang berarti zonk. Namun, Lanea ingin permainannya menarik. Para pemain akan memilih 2 buah angka L dan R. (1<=L<=R<=N) dan akan mendapatkan hadiah yang terdapat pada kotak dari L sampai R. Pertanyaan, dengan semua kombinasi nilai L dan R, berapa rata-rata banyak kotak tidak Zonk yang diambil pemain dari semua kemungkinan pengambilan yang ada?

Contoh:

N=3

1 0 1

Jawaban = 1.000

Penjelasan, ada 6 kemungkinan L dan R yang bisa dipilih dari 1..3.

L=1 dan R=1, maka 1 kotak tidak Zonk.

L=1 dan R=2, maka 1 kotak tidak Zonk.

L=1 dan R=3, maka 2 kotak tidak Zonk.

L=2 dan R=2, maka 0 kotak tidak Zonk.

L=2 dan R=3, maka 1 kotak tidak Zonk.

L=3 dan R=3, maka 1 kotak tidak Zonk.

Sehingga rata-ratanya adalah (1+1+2+0+1+1)/6=1.000.

Solusi saya, pertama kita bikin prefix sum. F(x)=banyaknya kemungkinan dari 1 sampai F(x). Jadi, jika ingin mencari kemungkinan dari L sampai R, adalah F(R)-F(L-1).

Percobaan pertama, brute force, hitung semua kemungkinan tidak Zonk pada semua kombinasi L dan R, bagi dengan banyaknya kombinasi L dan R. Hasil, TLE. Jelas. Kompleksitas O(n^2)

Percobaan kedua, sedikit pruning, ternyata pada percobaan awal saya, terlalu banyak overlapping subproblem. Ternyata, jawabannya bisa dicari dengan 1*f(1)+2*f(2)+3*f(3)….+N*f(n) – 1 *f(N) – 2*f(N-1)-3*f(N-2)-……-N*f(1). Kompleksitas O(n). Submit. Hasil, WA.

Ternyata, berdasarkan testcase contoh saja, saya sudah salah. Saya mengeluarkan “1” instead of “1.000”. Saya mengecek bagian akhir kode saya. Sudah benar(menurut saya waktu itu). cout<<”Kasus #”<<tc<<setprecision(3)<<”: “<<ans<<endl;. Sampai sekitar setengah jam kemudian, saya melihat-lihat soal yang lain dulu sembari mencoba mengingat. Setelah frustasi, akhirnya saya koding ulang dengan pascal. Dengan sedikit macet gara-gara sudah lama tidak memakai pascal akhirnya selesai dan submit. AC. Sayangnya, jam telah turun melewati angka 2 yang artinya scoreboard sudah di freeze. Saya tidak bisa melihat perubahan rank saya.

Di tengah-tengah pertandingan tadi saya juga mencoba soal G, “Rivalitas”. Ada N jenis makanan. Andri selalu makan tepat lebih banyak daripada Phi. Hitung kemungkinan makanannya! Solusinya adalah (N,0)(N,1)+(N,1)(N,2)+(N,3)(N,4)…..+(N,a)(N,a+1) dengan a+a+1=N. *(O,P)=kombinasi O diambil P unsur. Masalahnya ada pada implementasi. Dengan N dapat mencapai 1000000 menggunakan array 2 dimensi tentu tidak mungkin. Akhirnya, karena saya lupa STL yang dapat menghandle masalah ini, saya skip.

Sampai akhir kompetisi pada jam 15.00, hanya 4 soal ini yang berhasil saya kerjakan dari 10 soal yang tersedia. Setelah mengambil tas, makanan, solat, para peserta dikumpulkan kembali di hall utama tempat menyelenggarakan sambutan tadi sekitar jam 15.30.

Penantian

Setelah mendengarkan pembahasan soal yang tidak kelihatan dibahas sama sekali. Acara selanjutnya, seperti yang sudah ditebak, pengumuman yang ditunggu-tunggu diundur paling belakang. Saatnya promosi!!! Hufft…. Sekitar 1 ½ jam kemudian akhirnya pengumuman lomba pun dimulai dengan urutan IT Competition, Game Development dan yang terakhir BNPCHS. Para juara adalah orang-orang yang tidak asing lagi. Jam 17:30, penutupan dengan doa mengisyaratkan berakhirnya Beefest 2016. Selanjutnya, pengambilan sertifikat finalis dan juara, dan pulang. Tamat!

Fakta dan pelajaran :

-cout<<”Kasus #”<<tc<<setprecision(3)<<fixed<<”: “<<ans<<endl;

-Jangan lupa bawa buku c++ selain buku CP

-Stasiun Tanah Abang di Hari Minggu lebih ramai daripada stasiun Manggarai di Hari Kerja

-Saya ketemu Dekan Game Development Binus waktu sholat Magrib di stasiun Tanah Abang