Akhir Tahun 2013

Tidak terasa waktu setahun telah berlalu, yang artinya saya sudah menulis blog ini selama setahun. Akhirnya wacana yang tersimpan selama bertahun-tahun dapat saya wujudkan, dan karena blog ini masih aktif, artinya saya cukup berhasil :)

Sejauh ini, sudah ada 25 post. Bisa dikatakan secara rata-rata saya menulis setiap sebulan dua kali. Jumlah yang tidak banyak, dibandingkan dengan target seminggu satu post. Apa dayanya, kadang-kadang saya harus mengerjakan tugas kuliah, mengurus organisasi, dan lain-lain. Bagaimanapun juga, saya akan terus berusaha untuk mengejar target tersebut.

Beberapa hal menarik yang saya alami selama menulis blog ini:

• Belajar menggunakan LaTeX untuk menulis rumus
• Belajar menulis yang mudah dimengerti orang lain
• Blog saya sering dikunjungi orang asing untuk melihat postingan ini. Sepertinya diskusi di internet benar-benar sangat jarang sehingga yang muncul di google adalah blog saya :D
• Menulis pembahasan untuk soal benar-benar menambah pemahaman terhadap solusi yang telah kita dapatkan!

Terlepas dari blogging, saya juga berhasil melewati tahun ini dengan baik. Pada tahun ini, selain berkuliah, saya juga memegang posisi:

1. PIC Competitive Programming CompFest (mudahnya: ketua bagian kompetisi pemrograman)
2. Ketua FPC (Fun Programming Club) di Ristek Fasilkom
3. Ketua Departemen Jumatan di KMBUI (Keluarga Mahasiswa Buddhis Universitas Indonesia), intinya mengadakan pertemuan setiap hari Jumat dengan anggota lainnya
4. Asisten dosen untuk kuliah struktur data dan algoritma, dengan segudang berkas yang perlu dikoreksi!

Pada awal tahun, saya mengatakan "kalo sampe bisa ngelewatin 1 tahun dengan 3 kepengurusan dan beberapa kerjaan lain gini, gua akan merasa ganteng". Ternyata memang saya ganteng :')

Banyak kejadian-kejadian yang saya alami dan pelajaran yang saya dapatkan, terutama dalam menjalankan kepengurusan itu. Saya belajar bagaimana mengurus banyak hal (tidak multi-tasking, saya lebih suka sekuensial), mengatur waktu, dan bertanggungjawab dalam melaksanakan berbagai pekerjaan. Benar-benar terasa bagaimana efeknya terhadap kehidupan kita, padahal sebelumnya saya kurang peduli terhadap kegiatan seperti itu. Ternyata memang benar kata orang bijak, "Jika ingin berkembang, keluarlah dari zona nyaman Anda".

Selain itu, saya juga mengikuti berbagai kompetisi. Mulai dari ITBPC, Gemastik, sampai ICPC. Dari sekian banyak kompetisi yang saya ikuti, yang berkesan bagi saya adalah pencapaian terbaik selama di tim Vidina 2.0, yaitu mendapat predikat best local team pada ACM-ICPC Asia Jakarta 2013. Benar-benar tidak menyangka bahwa kita bisa mendapatkannya :')

 

Foto oleh Pak Denny

Semoga di tahun 2014 saya dapat berkontribusi lebih banyak dalam kehidupan ini, khususnya dunia pemrograman di Indonesia dan TOKI.

UVa 10381 - The Rock

Soal ini sudah pernah saya baca sejak tahun 2010, yaitu ketika saya bertekad untuk menyelesaikan soal-soal UVa di chapter 103. Sayangnya, berhari-hari telah saya gunakan untuk memikirkan solusinya dan tidak juga ditemukan :(. Ingin mencari diskusinya di internet pun sumbernya sangat sedikit. Akhirnya pada tahun 2013, saya kembali menantang soal ini dan setelah diskusi dengan Ashar, kami berhasil menyelesaikannya!

Untuk menyelesaikan soal ini, perlu dipahami bahwa soal ini dapat dimodelkan sebagai permainan 2 pemain: satu orang berusaha berjalan sampai pintu keluar (sebut saja A), dan satu orang berusaha memblokir jalan (sebut saja B). Terdapat perbedaan peran yang mana B hanya memiliki kesempatan satu kali memblokir dan dapat dilaksanakan kapan saja. Lalu setelah diblokir, permainan dapat dianggap berakhir karena si pemain yang satunya pasti memilih jalur terpendek. Pertanyaannya adalah: jika keduanya bermain optimal, berapa langkah minimal yang dibutuhkan oleh pemain yang berjalan?

Struktur Data Treap

Sebagai alternatif AVL Tree, Red Black Tree, dan Splay Tree

Bila Anda sering berkecimpung dalam soal dynamic range query, tidak jarang Anda akan menemukan soal yang membutuhkan Balanced Binary Search Tree (BBST) untuk menyelesaikannya. Biasanya, persoalan tersebut melibatkan:

• Dynamic Order Statistic, yaitu diberikan informasi nilai-nilai yang bisa berubah-ubah, lalu sering ditanyakan "Bila nilai-nilai diurutkan dari yang terbesar, siapa yang berada di posisi ke-i?", atau
• Penambahan dan penghapusan objek yang rentang nilainya bisa sangat besar (sehingga array tidak cukup), dan tidak dapat dilakukan grid compression (pemetaan koordinat menjadi yang hanya dibutuhkan saja), dan terdapat query lain yang tidak dapat dilayani oleh STL set atau map pada C++ secara efisien.

Untuk mengatasi kedua hal tersebut, biasanya orang akan menggunakan BBST. Untuk competitive programming, BBST yang populer adalah AVL Tree dan Red-Black Tree. Lalu apakah masalah selesai sampai di sini?

Ada masalah utama dari AVL Tree dan Red-Black Tree, yaitu sulit untuk menulis implementasinya. Sekalipun kompetisi itu berbentuk ICPC dan Anda memiliki catatan implementasinya, Anda masih harus berhadapan dengan panjang dan rumitnya implementasi tersebut (AVL Tree yang saya implementasikan ada 200 baris). Banyaknya baris kode yang Anda tulis akan meningkatkan peluang terjadinya kesalahan, dan sekalinya ada bug, sulit untuk mendeteksi di mana bug itu berada!

Nah karena masalah tersebut, terdapat varian BBST yang lebih ramah dalam hal implementasi: treap. Struktur data ini merupakan "gabungan" dari struktur Binary Search Tree dan heap. Bentuknya berupa binary tree yang tidak harus complete. Setiap node pada treap mengandung dua nilai, yaitu priority dan key. Perlu diperhatikan nilai priority di sini sifatnya sebagai pembantu dalam menyeimbangkan struktur tree, sehingga nilainya tidak berkaitan dengan nilai sebenarnya yang ingin Anda simpan. Bahkan dalam implementasinya, nilai priority didapatkan dengan random. Oleh karena itu treap juga dikenal sebagai randomized data structure, dan memiliki kompleksitas operasi penambahan, penghapusan, dan pencarian dalam expected O(log N). Menurut sumber-sumber yang saya baca, konstanta dari struktur data ini kecil, sehingga expected O(log N) yang dimiliki sangat ringan dan cepat!

ACM ICPC Regional Harbin 2010 - Cross the Wall

Sebuah perkenalan kepada DP Convex Hull... 

Satu lagi soal dari ICPC Regional Harbin 2010 yang sedikit sekali diskusinya, yaitu Cross the Wall. Soal ini sangat menarik karena memerlukan observasi yang mendalam.

Inti dari persoalannya sederhana:

• Diberikan N persegi panjang dengan berbagai ukuran panjang dan lebar.
• Anda boleh membuat maksimal K buah lubang persegi panjang pada sebuah bidang (tembok) sedemikian sehingga setiap persegi panjang dapat melewati bidang tembok tanpa dirotasi.
• Lubang yang dibuat tidak boleh bersentuhan dengan lubang lainnya yang sudah pernah dibuat.
• Persegi panjang yang panjang dan lebarnya lebih kecil atau sama dengan panjang dan lebar lubang bisa melewati lubang tersebut.
• Biaya membuat sebuah lubang persegi panjang dengan panjang P dan lebar L adalah P &times L.
• Seluruh persegi panjang yang dibicarakan di sini memiliki sisi yang paralel dengan sumbu x atau y.
• Tentukan total biaya minimum untuk membuat setiap persegi panjang dapat melewati bidang tembok!

Batasan pentingnya:

• 1 ≤ N ≤ 50.000
• 1 ≤ K ≤ 100
• Panjang dan lebar setiap persegi panjang adalah bilangan bulat positif tidak lebih dari 1.000.000