Monday, 21 August 2017

Struktur Data Range Tree

Terdapat permintaan untuk menuliskan tentang range tree, jadi kali ini saya akan membahasnya dari awal.
Anda perlu diharapkan memiliki pengetahuan tentang apa itu segment tree terlebih dahulu.

Range tree yang saya tulis ini mungkin berbeda dengan range tree pada ilmu komputer pada umumnya. Saya akan membahas untuk spesifik range tree yang sering digunakan pada kompetisi pemrograman.


Tentang Range Tree

Range tree adalah struktur data yang dapat melayani operasi-operasi pada suatu daerah berbentuk persegi panjang secara efisien. Untuk contoh pembahasan ini, kita akan menggunakan contoh soal berikut.

Pada suatu lahan, terdapat N titik yang mengandung sejumlah emas. Lahan ini dapat dianggap suatu bidang 2 dimensi. Titik ke-i memiliki koordinat (xi, yi). Tugas kita adalah menjawab sejumlah pertanyaan berupa:

"Pada daerah yang bermula di (x1, y1) sampai (x2, y2), ada berapa titik emasnya?"

Perhatikan gambar berikut.


Misalkan bulatan pada koordinat adalah titik yang mengandung sejumlah emas. Jawaban untuk banyaknya titik emas pada daerah yang bermula di (2, 2) sampai (8, 7) adalah 5.


Konstruksi Range Tree

Range tree sangat mirip dengan segment tree. Perbedaannya adalah setiap node pada range tree tidak menyimpan nilai agregat, melainkan data yang tercakup dalam range-nya.

Misalnya kita memiliki data koordinat sebagai berikut:
x: 1 2 4 5 6 7 8 9
y: 3 1 4 2 5 9 7 8
Untuk membuat range tree, kita akan membagi-bagi data tersebut ke dalam struktur yang mirip dengan segment tree, berdasarkan nilai sumbu x.


Kemudian urutkan setiap segmen berdasarkan nilai sumbu y. Hal ini mengakibatkan nilai sumbu-x pada setiap node berantakan, tetapi ini bukan masalah.


Selesailah pembuatan range tree. Konsepnya sangat sederhana.

Kompleksitas untuk membuat struktur yang mirip dengan segment tree adalah O(N log N).
Untuk setiap tingkat, total kompleksitas untuk mengurutkannya adalah O(N log N). Karena terdapat O(log N) ketinggian, maka kompleksitas pembangunan range tree adalah O(N log2 N).

Terdapat caranya supaya pembangunan range tree hanya O(N log N). Namun itu adalah cerita untuk lain hari.

Untuk memori, perhatikan bahwa tingkat pada range tree memiliki N elemen. Kembali lagi karena ketinggian dari tree adalah O(log N), didapatkan bahwa penggunaan memori range tree untuk N elemen adalah O(N log N).


Menghitung Titik dalam Persegi Panjang

Operasi menghitung banyaknya titik dalam (x1, y1) .. (x2, y2) dilakukan dengan mudah. Mulai penelusuran dari root range tree.

Untuk setiap penelusuran pada suatu node, terdapat 3 kasus:
  1. Node ini merepresentasikan segmen yang tidak bersentuhan dengan [x1, x2] pada sumbu x. Untuk kasus ini, hentikan penelusuran.
  2. Node ini merepresentasikan segmen yang bersentuhan [x1, x2] pada sumbu x, tetapi tidak berada di dalam [x1, x2]. Untuk kasus ini, telusuri kedua anak node ini.
  3. Kasus yang tersisa adalah node ini merepresentasikan segmen yang sepenuhnya berada di dalam [x1, x2] pada sumbu x. Untuk kasus ini, hitung banyaknya titik yang berada di dalam [y1, y2] pada sumbu y menggunakan binary search.

Perhatikan contoh berikut untuk mencari banyaknya titik dalam (2, 2) .. (8, 7). Warna merah menyatakan node yang memenuhi kasus ke-3, dan warna biru menyatakan data yang ditemukan dengan binary search. Ingat bahwa prosesnya adalah:
  1. Telusuri node-node (tree traversal) seperti pada segment tree.
  2. Untuk setiap node yang mencakup data bernilai sumbu-x di dalam [x1, x2], lakukan binary search.


Setelah bagian memilah-milah segmen berdasarkan sumbu x, dijamin terdapat O(log N) segmen yang dipilih (seperti pada segment tree). Kemudian untuk setiap segmen dipilih, dilakukan binary search O(log N) pada titik-titik di dalamnya berdasarkan sumbu y. Sehingga kompleksitas untuk sekali menghitung banyaknya titik dalam daerah persegi panjang adalah O(log2 N).


Implementasi Range Tree

Pada ilmu pemrograman, terdapat konsep bernama "encapsulation". Konsep ini kurang lebih menyatakan bahwa:

"Pecah program besar menjadi beberapa komponen lebih kecil yang saling berinteraksi. Setiap komponen tidak perlu tahu implementasi komponen lainnya secara mendalam. Bila hal-hal tersebut dipenuhi, maka sakit kepala dapat dihindari".

Contoh untuk soal ini, ketika kita sedang berurusan dengan komponen x, kita tidak perlu peduli apa yang terjadi pada komponen y. Demikian juga kita tidak perlu peduli dengan nilai sumbu x ketika melakukan binary search. Hal ini membantu otak kita untuk fokus pada setiap komponen, ketimbang membuat program besar yang langsung mempertimbangkan seluruh komponen, yang mungkin mengakibatkan sakit kepala muncul.

Dalam rangka mendukung konsep "encapsulation", saya menganjurkan untuk mengimplementasikan node range tree menggunakan class atau struct pada C++, atau hal serupa pada bahasa pemrograman Anda. Saya akan menggunakan class pada C++ untuk tulisan ini.

Untuk keperluan implementasi, asumsikan kita memiliki struktur berikut:

Untuk node range tree, definisikan sebuah class yang menyimpan vector untuk menampung semua nilai y pada suatu node.

Kemudian definisikan beberapa variabel global:

Untuk tahap pertama, tampung dulu semua kemungkinan koordinat yang ada, kemudian lakukan kompresi pada sumbu-x.
Kompresi ini sebenarnya sesederhana mengurutkan seluruh sumbu x yang mungkin, lalu membuang nilai yang tidak unik. Hal ini akan mempermudah kita dalam membuat struktur range tree yang seimbang, hemat memori, dan bebas sakit kepala karena elemen yang tidak unik.

Setelah tahap kompresi, kita dapat memulai bagian membuat range tree. Definisikan fungsi untuk memasukkan data ke dalam range tree:

Selebihnya cukup masukkan semua data ke dalam range tree, dan urutkan tiap segmen.

Bagian menjawab pertanyaan, ikuti pembagian kasus yang telah dijelaskan pada bagian sebelumnya.

Perhatikan bahwa fungsi getCount didefinisikan dalam class RTreeNode. Dengan konsep encapsulation, kita membuat kode lebih mudah dibaca dan modular. Pada C++, Anda dapat menggunakan fungsi lower_bound dan upper_bound dari include algorithm:
  • lower_bound(arr.begin(), arr.end(), x): mengembalikan iterator pada arr yang menunjuk ke elemen pertama yang >= x
  • upper_bound(arr.begin(), arr.end(), x): mengembalikan iterator pada arr yang menunjuk ke elemen pertama yang > x
Hafalkan kegunaan kedua fungsi tersebut, karena dapat menghemat penulisan binary search. Jangan sampai tertukar!

Selesailah implementasi range tree untuk soal ini. Berikut kode lengkapnya:

Catatan Implementasi

Pada penjelasan dan gambar-gambar yang saya berikan, tidak ada dua titik dengan nilai sumbu-x yang sama. Ini sekedar untuk mempermudah penjelasan.

Apabila terdapat beberapa titik dengan nilai sumbu-x yang sama, cukup ikuti algoritma yang sama. Artinya, setiap node pada range tree yang memiliki kedalaman sama mungkin memiliki banyaknya elemen berbeda. Meskipun terlihat "berat sebelah", hal ini tidak menjadi masalah, sebab operasi di dalam node tersebut adalah binary search O(log N) yang sangat cepat. Kompleksitas akhir selalu O(log2 N) untuk operasi pencarian.

Gambar berikut menunjukkan range tree dengan beberapa titik dengan komponen x dan y yang sama. Untuk kejelasan, perhatikan informasi tentang rentang x setiap node pada tulisan merah.


Latihan

SPOJ MKTHNUM
Petunjuk: soal ini bukan soal range tree "straight-forward". Namun Anda hanya butuh sebuah observasi untuk dapat mengubah soal ini menjadi "straight-forward". Sorot teks di bawah ini untuk spoiler:
Spoiler 1: lakukan binary search the answer. Coba tebak jawabannya, lalu cek berapa banyak elemen yang berada di dalam indeks yang diberikan, dan lebih kecil dari angka yang Anda tebak.
Spoiler 2: jika elemen ke-i bernilai vi, maka elemen tersebut dapat direpresentasikan sebagai titik di koordinat (i, vi).

UVa 12345 - Dynamic len(set(a[L:R]))

Spoiler 1: jika elemen ke-i dan ke-j memiliki nilai yang sama, dan tidak ada elemen di antaranya yang bernilai sama juga, maka tambahkan titik bernilai (i ,j) ke dalam range tree.
Spoiler 2: Banyaknya elemen unik pada suatu rentang a..b adalah seluruh elemen pada rentang tersebut, dikurangi titik-titik pada daerah (a,?)..(?,b).


Penutup

Pembahasan tentang range tree ini masih di bagian permukaannya. Kita belum memasuki bagian membuat segment tree di dalam range tree. Tulisan yang akan datang akan membahas tentang hal tersebut. Semoga bermanfaat!

Wednesday, 16 August 2017

Pelatih Basket Gendut

(sesekali menulis yang tidak berkaitan dengan pemrograman)

Jika Anda pernah menonton film Slam Dunk, maka Anda mengenal Pak Anzai.

Pak Anzai dari cerita Slam Dunk
(dari http://annelialady.blogspot.com)

Pak Anzai, adalah pelatih bola basket pada film tersebut. Dulunya adalah seorang pemain, lalu sekarang sudah tua, gendut, dan pensiun. Saya mulai merasa diri saya seperti itu.

Sekarang saya sudah pensiun untuk competitive programming. Meskipun demikian, saya akan tetap menuliskan pengetahuan yang saya miliki, baik pada blog ini atau media lainnya.

Sunday, 13 August 2017

Range Query BIT

... atau disebut juga magic BIT

Pada akhir semester ganjil tahun 2014, Pak Denny mengadakan inisiatif untuk latihan ICPC yang kita sebut sebagai latihan FURIOUS. Alasannya karena klub programming di UI disebutnya Fun Programming Club (FPC), dan kali ini kami ingin serius, sehingga namanya menjadi FURIOUS Programming Club (FPC). "IT IS NOT FUN ANYMORE" kata Aji.

Pada salah satu sesi latihan ini, kami mengerjakan soal Alien Abduction Again (LA 6443). Pada saat ICPC Jakarta 2013, tim saya (Vidina 2.0) berhasil menyelesaikan soal ini dengan segment tree yang konstantanya dioptimisasi habis-habisan. Menurut pembuat soal (Felix Halim), solusi yang diharapkan adalah menggunakan Binary Indexed Tree (BIT). Meskipun sama-sama O(log N) untuk setiap operasi, penggunaan BIT jauh lebih cepat dari segment tree dalam hal konstanta.

Dalam sesi latihan ini, kami berusaha mengerjakannya dengan BIT. Waktu itu ada saya, Ashar, Aji, dan Soko, yang berpikir habis-habisan dalam mencari tahu bagaimana solusinya dengan BIT. Yang kami tahu adalah dapat digunakan 2 BIT untuk suatu range query/update sum. Akhirnya kami berhasil memahami cara kerjanya, melakukan generalisasi untuk kasus umum, dan AC untuk soal tersebut. Aji menyebutnya dengan nama "magic BIT". Sejak saat itu saya pun ikut menyebutnya magic BIT.


Permasalahan Range Query

Terdapat sebuah array A berukuran N, yang terdefinisi dari indeks 1 sampai dengan N. Terdapat sejumlah operasi yang masing-masing bisa berupa salah satu dari:
  1. add(a, b, v), artinya tambahkan seluruh elemen A dengan indeks antara a sampai b dengan v. Dengan kata lain, A[a..b] += v.
  2. sum(x), artinya cari nilai A[1]+A[2]+A[3]+...+A[x].

Soal ini jelas dapat diselesaikan dengan segment tree dengan lazy propagation. Seperti biasa, mari kita coba selesaikan dengan BIT.

Saturday, 5 August 2017

Grid Compression

Seperti judulnya, kali ini saya akan bercerita tentang grid compression. Sebelumnya ada suatu kisah.

Suatu ketika saat Pelatnas 2 TOKI 2011, terdapat soal yang menyeramkan. Saya tidak berhasil menemukan soal tersebut, tapi intinya seperti ini:
  1. Terdapat ruang 2 dimensi
  2. Akan dibangun sebuah gambar, dapat didekomposisi menjadi N persegi panjang
  3. Persegi panjang ke-i terletak di koordinat (xi1, yi1) sampai dengan (xi2, yi2)
  4. Beberapa persegi panjang boleh saja saling tumpang tindih
  5. Wujud gabungan dari seluruh persegi panjang ini adalah gambar yang dimaksud
  6. Cari keliling dan luas dari gambar ini!

Batasan:
  • N ≤ 50
  • 0 ≤ nilai seluruh koordinat ≤ 109

Saya berpikir seharian, dan tidak menemukan bagaimana cara menyelesaikannya. Kemudian kami diberikan contoh solusi soal tersebut dalam bentuk kode. Saya menghabiskan semalaman untuk memahami kode tersebut, dan akhirnya mengerti penyelesaian solusinya.

Saturday, 29 July 2017

Hercules, Konstanta Marshal, dan Hybrid


Masa-masa saya Pelatnas, terdapat beberapa teknik yang sering digunakan oleh peserta. Tahun-tahun ketika saya mulai mengurus Pelatnas, teknik ini mulai jarang digunakan. Supaya tidak hilang ditelan waktu, saya memutuskan untuk menuliskan teknik tersebut, yaitu Hercules Algorithm, Konstanta Marshal, dan Hybrid Algorithm.


Hercules Algorithm

Biasa cukup dengan disebut "Hercules" saja. Pertama kali saya menyadari adanya teknik ini adalah pada saat OSN 2009.

Friday, 21 July 2017

Struktur Data Binary Indexed Tree (BIT)

Dikenal juga sebagai struktur data Fenwick Tree

Saya sering menyebutkan struktur data ini pada tulisan-tulisan saya yang sebelumnya. Biasanya saya mencantumkan link ke halaman tutorial Fun Programming Club Ristek Fasilkom UI (organisasi semacam "klub programming"). Namun kini webnya sudah berubah, dan tulisan yang lama sudah menghilang. Untuk itu saya akan menuliskannya di blog ini.

Struktur data ini memiliki kegunaan yang mirip dengan segment tree. Hal yang dapat dikerjakan BIT, dapat dikerjakan segment tree, tetapi belum tentu sebaliknya. Mari kita mulai dengan persoalan motivasi.


Persoalan Motivasi

Diberikan sebuah array A yang berisi N bilangan. Array A terdefinisi untuk A[1..N] (one-based). Terdapat sejumlah perintah yang masing-masing dapat berbentuk:
  1. update(x, v), artinya tambah nilai di indeks x sebanyak v.
  2. query(x), artinya cari nilai A[1] + A[2] + ... + A[x].
Tentunya, kita dapat menyelesaikan persoalan ini dengan cara naif, update O(1) dan query O(N). Sayangnya cara ini terlalu lambat.

Segment tree dapat dengan mudah menyelesaikan masalah ini, dengan update O(log N) dan query O(log N). Namun mari kita coba bahas dengan BIT.

Saturday, 15 July 2017

Radix Sort

Bahasan kali ini bukan sesuatu yang berat, yaitu sekedar radix sort.

Orang-orang yang telah menguasai algoritma pengurutan tingkat lanjut pasti tahu tentang jenis pengurutan ini. Algoritmanya sendiri memiliki konsep yang sederhana. Namun di balik konsep sederhana itu, implementasinya mungkin tidak semudah yang dibayangkan. Alasan saya menulis topik ini adalah memperkenalkan implementasinya, yang ternyata menggunakan stable counting sort.

Pengurutan ini cukup unik, untuk mengurutkan N angka yang memiliki paling banyak d digit, kompleksitasnya adalah O(Nd). Untuk nilai d yang kurang dari log N, algoritma ini lebih cepat dari pengurutan O(N log N).

Saturday, 8 July 2017

Binary Search pada Sparse Table

Terdapat suatu teknik optimisasi yang dapat digunakan pada binary search. Biasanya teknik ini akan membuang faktor sebesar O(log N). Jadi kalau tadinya algoritma berjalan dalam O(log2 N), sekarang menjadi O(log N) saja.

Teknik dapat digunakan pada binary search yang dilakukan pada Sparse Table.


Persoalan Motivasi

Misalnya dimiliki N batu pijakan di danau, yang strukturnya seperti lingkaran. Batu-batu dinomori dari 0 sampai dengan N-1. Berhubung bentuknya siklik, batu i bertetangga dengan batu (i-1) dan (i+1). Tentunya batu 0 bertetangga dengan batu N-1 dan 1. Diketahui pula bahwa apabila seseorang berdiri di batu ke-i, maka dia hanya dapat berpindah tempat ke batu (i+t[i]) mod N. Pertanyaannya adalah, apabila seseorang bediri di suatu posisi x, berapa banyak aktivitas berpindah tempat minimal yang perlu ia lakukan supaya ia memutari satu lingkaran?

Misalnya untuk ilustrasi berikut, banyaknya berpindah tempat yang perlu dilakukan adalah 6 kali. Supaya mudah, saya memodelkan setiap posisi (i+t[i]) mod N sebagai anak panah.

Friday, 30 June 2017

SPOJ QMAX3VN - BST Sebagai Segment Tree

Berikut adalah kelanjutan dari tulisan saya tentang penggunaan BST untuk menjawab dynamic range query. Soal yang dibahas adalah SPOJ QMAX3VN.


Ide solusi

Soal ini merupakan implementasi langsung dari konsep BST sebagai "segment tree" yang saya bahas sebelumnya. Pilihlah suatu jenis BBST yang Anda sukai, baik itu AVL Tree, Red Black Tree, Treap, atau Splay Tree.

Nilai agregat pada soal ini jelas adalah nilai terbesar yang ada pada suatu subtree. Anda juga perlu menyimpan banyaknya elemen yang ada pada suatu subtree, supaya dapat menentukan apakah suatu node/subtree berada dalam rentang query.

Tips untuk mengimplementasikannya:
  1. Definisikan fungsi updateAggregate untuk melakukan update pada nilai agregat suatu node, menggunakan data dari anak kiri dan anak kanannya. Aktivitas updateAggregate akan digunakan di banyak tempat, sehingga mendefinisikannya sebagai fungsi akan mempermudah penulisan kode. Pastikan kompleksitasnya O(1).
  2. Jika BST Anda menggunakan rotasi, pastikan pemanggilan updateAggregate sesuai urutannya, yaitu dari node anak-anak dulu, baru ke orang tuanya.
  3. Definisikan fungsi getMax dan getCount untuk mendapatkan nilai terbesar dan banyaknya node pada suatu subtree, yang mampu menangani kasus ketika node yang diberikan adalah null. Pendefinisian fungsi ini sangat membantu dalam mengeliminasi if statement untuk null di banyak tempat. Pastikan juga kompleksitasnya O(1).

Saturday, 24 June 2017

BST Sebagai Segment Tree

Tahukah Anda bahwa BST dapat digunakan untuk menjawab dynamic range query, seperti mencari nilai terkecil/terbesar dari suatu rentang array? Atau juga hal-hal lebih kompleks lainnya seperti mencari subarray dengan jumlahan terbesar. Tulisan ini akan menjelaskan konsep membuat BST yang mampu melayani query tersebut, lalu menjelaskan kenapa kita membutuhkannya.

Sebagai catatan, BST yang saya maksud di sini adalah Binary Search Tree yang balanced, alias BBST.


Konsep Dasar

Terdapat beberapa konsep tentang BST yang perlu dipahami terlebih dahulu. Simak penjelasannya satu per satu.

Saturday, 17 June 2017

Rumus Dynamic Programming

Awal Perjumpaan

Malam hari saat pertama kali ikut OSN 2009, saya membaca buku TOKI News. Ada beberapa pembahasan soal di sana, dan sepertinya cocok untuk memanaskan diri sebelum kompetisi.

Kemudian yang saya lihat adalah rumus ajaib yang tiba-tiba muncul setelah kata-kata "Dynamic Programming" disebut:
Berhubung saya waktu itu tidak mengerti, saya lompat ke pembahasan soal lainnya. Buka-buka halaman di belakang, baca soalnya, lalu pembahasannya. Kemudian yang saya temui adalah ini:

Saturday, 10 June 2017

Mengenal Expected Value (Nilai Harapan)

Dulu ketika zamannya saya ikut SRM top coder, kalau dapat soal dengan kalimat perintah "Find the expected value of ...", saya langsung merasa seram. Alasannya karena saya tidak tahu apa itu expected number. Belum lagi tiba-tiba contoh keluaran yang ada adalah angka pecahan yang misterius, contohnya:
1.12938104018102
Kemudian suatu ketika saya mendapatkan pencerahan, bahwa ternyata expected value adalah nilai harapan. Seketika saya langsung bisa mengerjakan soal-soal dasar tentang expected value.

Tulisan ini akan menjelaskan apa itu expected value, supaya kalian para pembaca tidak merasa seram seperti saya dulunya.

Sunday, 28 May 2017

Struktur Data Sparse Table

Kali ini saya membahas tentang struktur data yang menurut saya jarang diajarkan secara formal. Selama ini saya mempelajarinya sebagai bagian dari suatu algoritma lebih besar, seperti pencarian LCA (Lowest Common Ancestor) atau RMQ (Range Minimum Query).


Permasalahan Motivasi

Terdapat N orang di sebuah ruangan. Terdapat sebuah bola panas, yang awalnya diberikan pada seseorang. Ketika orang ke-i menerima bola panas ini, ia akan mengoper bola panas itu ke orang ke-p[i]. Proses menerima bola dan mengopernya terjadi dalam satu periode yang disebut satu putaran.

Kemudian Anda diberikan banyak pertanyaan berbunyi:
Ditentukan suatu angka X dan Y. Bila awalnya orang yang menerima bola panas adalah orang ke-X, maka dalam Y putaran berikutnya, di mana bola panas itu berada?

Asumsikan X dan Y tidak lebih dari N.

Thursday, 25 May 2017

Amortized Analysis

Jika Anda belajar library bernama "vector" di C++, maka mungkin Anda pernah mendengar bahwa kompleksitas push_back adalah amortized O(1). Apa yang dimaksud dengan amortized?

Penerjemahan langsung ke Bahasa Indonesia agak lucu, yaitu "dilunasi dengan angsuran". Untuk lebih memahaminya, lebih baik kita membahas contoh soalnya, yaitu push_back pada vector.

Permasalahan

Anda ingin membuat array, tetapi tidak mengetahui banyaknya elemen maksimal yang mungkin ditampung dalam suatu waktu. Salah satu cara yang dapat dilakukan adalah menggunakan "resize-able array".

Pertama mulai dengan sebuah array yang maksimal dapat menampung X elemen. Misalkan X kita beri nilai 10. Operasi menambahkan elemen di paling belakang awalnya array dapat dilakukan dengan cara kira-kira seperti ini:

Saturday, 25 February 2017

Panduan Menulis Kaget

Apakah Anda orang yang tiba-tiba:
  • Hendak mengarang untuk tugas sekolah/kuliah?
  • Hendak menulis soal untuk kontes?
  • Harus menulis skripsi karena deadline menulis tinggal beberapa hari?
  • Ditunjuk untuk menulis materi/pembahasan?
Jika ya, maka Anda mungkin mendapat manfaat dari membaca panduan menulis kaget berikut. Saya sebut kaget karena tulisan ini bersifat tiba-tiba, seperti pasar kaget.

Ilmu menulis saya didapatkan dari senior-senior TOKI dan dosen yang sudah ahli dalam menulis soal atau dokumen resmi. Pengaruh paling besar yang saya dapatkan adalah dari Ashar. Berterima kasih lah pada Ashar.

Saya bukan ahli bahasa. Saya hanya orang yang entah kenapa sering menulis.