Sabtu, 25 Oktober 2014

Manipulasi Segmen pada BIT & Segment Tree

Kali ini saya akan berbagi suatu teknik yang lucu, yaitu mengoprek "jeroan" segment tree dan BIT. Kadang-kadang, dengan mengetahui struktur dalam suatu objek dan langsung memanipulasinya, kita bisa melakukan berbagai hal dengan lebih efisien. Misalnya kalau Anda paham struktur dalam televisi, mungkin Anda bisa mengatur supaya televisinya otomatis mati pada jam-jam tertentu.

Saya akan memberikan beberapa contoh yang umum.

Contoh umum

Misalkan diberikan soal:
Terdapat sebuah array A yang awalnya kosong dan N operasi, yang bisa berupa:
  1. tambah x, artinya tambahkan x ke dalam array A. Dijamin tidak nilai-nilai di dalam array A akan selalu unik
  2. tanya k, artinya cetak bilangan terkecil ke-k di dalam array A pada saat itu
Batasan:
  1. 1 ≤ N ≤ 100.000
  2. Pada setiap operasi tambah, 1 ≤ x ≤ N
  3. Pada setiap operasi tanya, 1 ≤ k ≤ N
Salah satu cara yang mungkin langsung terpikir adalah dengan BST. Namun BST relatif sulit untuk di-coding, lagipula tidak ada operasi menghapus. Oleh karena itu, marilah kita coba kerjakan dengan segment tree.

Kamis, 16 Oktober 2014

IOI 2011 - Pattaya, Thailand (Bagian 1)

Akhirnya tiba saatnya untuk menyelesaikan "perjalanan akhir" yang dimulai sejak OSK. Sudah bertahun-tahun berlalu, tetapi ingatan saya akan IOI ini masih melekat.

Tulisan ini akan membahas hari-hari saya di Thailand saat IOI 2011. Untuk foto-foto, saya tidak banyak mengambil momen karena masih belum sadar bertapa pentingnya momen tersebut :') oleh karena itu saya mengumpulkan foto dari berbagai pembina TOKI, Brian, Jessica, guide di sana, dan foto saya sendiri. Dengan tulisan ini, lengkaplah tulisan IOI 2011 dari sudut pandang empat besar TOKI 2011, karena saya yang terakhir menulis tentang ini.

Keadaan

Anggota tim yang berangkat:
  • Bu Inge - delegation leader
  • Pak Rully - deputy leader
  • Gang of Four (GoF) - contestant (termasuk saya)
  • Brian - guest (membantu anggota delegasi)

IOI 2011 - Pattaya, Thailand (Bagian 2)

Hari 4

Hari kontes kedua telah tiba. Paginya saya makan biasa saja, dan sedikit minum. Untungnya tidak ada masalah apapun untuk masuk ke dalam ruangan kontes. Sesaat sebelum kontes dimulai, "contestants, please shake hand with the the other contestant". Saya dan teman-teman sebangku saling menatap bingung satu sama lain, lalu mulai bersalaman. Rasanya saya lebih percaya diri, dan merasa mampu mengerjakan soal hari kedua ini. Oh ya, apapun yang saya kerjakan hari ini toh tidak akan merubah hasil di hari pertama saya.

Saya mulai kontes dengan mengemut cokelat 99% cocoa, lalu membaca soal dengan tenang. Soal hari ini adalah parrot, elephant, dan crocodile. Saya mulai memikirkan solusi crocodile. Selama 2 jam, akhirnya saya berhasil mengerjakannya sampai sebelum 1 subtask terakhir. Karena sudah 2 jam, maka saya pindah ke soal lain, parrot. Untuk soal ini, nilai saya juga lumayan bagus. Saya sudah memikirkan berbagai macam cara, dan tidak bisa meningkatkan nilai itu lagi. Hingga akhirnya tinggal 1 jam terakhir, saya gunakan untuk mengerjakan elephant. Sisa waktu saya gunakan lagi untuk mengejar solusi soal crocodile. Oh ya, selama hampir 3 jam pertama, cokelat yang saya emut itu tetap di mulut (tidak tertelan atau meleleh!), dan menjaga konsentrasi saya.

IOI 2011 - Pattaya, Thailand (Bagian 3)

Hari 6

Pagi ini kami diajak Yura dan Yegar untuk mengikuti kegiatan "variety for fun" (waktunya panitia hiperaktif beraksi). Kali ini, peserta dipisahkan menjadi sekitar 4 grup. Kami GoF mendapati di tim kuning. Ada seorang panitia hiperaktif yang menjadi provokator sekaligus pemimpin grup kuning. Dia membawa pengeras suara dan memanas-manasi seluruh peserta. Tidak lama kemudian kita diajari yel-yel, dan mulai bermain.

Provokasi (foto oleh Yegar)!

Sabtu, 11 Oktober 2014

Kisah Perjalanan di TOKI: Persiapan IOI

Masa Rehat

Kembali dari Pelatnas, saya menghadiri acara kelulusan sekolah. Secara tidak menyangka pula saya mendapatkan nilai ujian yang memuaskan, setelah berjuang belajar kilat selama dua minggu seusai Pelatnas 2. Saya juga dikejutkan dengan pengumuman SNMPTN undangan bahwa saya TIDAK DITERIMA. Oke, saya harus belajar untuk SNMPTN tertulis :'(

Saya mulai membeli buku sejenis kumpulan soal untuk SNMPTN dan belajar kembali, padahal dikira sesudah ujian nasional, bisa fokus IOI. Saya juga mengikuti kompetisi lokal yang segera dilaksanakan seperti COMPFEST 2011, tetapi akhirnya tidak masuk ke final karena saat penyisihan perut saya sakit dan tidak sempat menyelesaikan satu soal lagi :(

Namun untungnya, saya menerima email dari humas Fasilkom UI bahwa pihak Fasilkom menawarkan beasiswa untuk peraih medali OSN. Namun, masih diperlukan seleksi. Jelas saya senang dengan informasi ini. Sebenarnya masih ada keraguan juga pada diri saya, mau kuliah di mana. Akhirnya setelah melalui pemikiran panjang, saya memutuskan untuk mendaftarkan diri ke UI lewat jalur masuk peraih medali OSN tersebut.

Kamis, 09 Oktober 2014

OSN 2014 - Mataram, Lombok

Lima tahun telah berlalu sejak saya mengikuti OSN 2009. Saya yang dulu duduk sebagai peserta, kini duduk sebagai juri. Lebih tepatnya, saya berada di bawah SC (Scientific Committee), yaitu panitia yang mengurus segala hal yang berkaitan dengan soal. Sungguh suatu kehormatan besar saya bisa menjadi juri bagi OSN komputer/informatika 2014.


Lima tahun berlalu

Kegiatan sebagai juri sudah dimulai sejak lama sebelum OSN. Kami mulai mengumpulkan soal, menyeleksi soal, dan memproses soal hingga dijadikan soal yang siap pakai. Apakah hanya itu? Tidak! Kami juga mengurus sebagian kecil PJJ dan open OSN. Kebetulan tahun ini (2014), Open OSN akan dibuka untuk kalangan internasional. Banyaknya yang harus dikerjakan menjadi mengganda. Untungnya selalu ada pembina TOKI yang siap menasihati dan membantu.

Saya lebih menceritakan tentang apa yang terjadi saat OSN secara garis besar. Sehingga tulisan berikut akan dimulai dari hari pertama OSN.