Struktur Data Range Tree Bagian 2: RMQ

Tulisan ini adalah kelanjutan dari bagian pertama tentang pengenalan range tree.

Kini kita mampu menghitung banyaknya elemen di suatu daerah persegi panjang. Operasi lainnya yang sering dibutuhkan adalah pencarian nilai terbesar, terkecil, atau bahkan jumlahan elemennya. 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), dan memiliki kandungan emas sebanyak vi kg. Tugas kita adalah menjawab sejumlah pertanyaan berupa:

"Pada daerah yang bermula di (x1, y1) sampai (x2, y2), berapa kandungan emas terbanyak yang ada pada suatu titik di daerah tersebut?"

---

Ide Penyelesaian

Dengan ide pada tulisan sebelumnya, kita dapat membagi-bagi daerah berdasarkan sumbu x. Kemudian untuk setiap suatu rentang x, kita bagi berdasarkan sumbu y.

Untuk mendapatkan nilai terbesar di suatu daerah persegi panjang, lakukan query range tree seperti cara sebelumnya. Nilai terbesar sebenarnya sesederhana nilai terbesar dari tiap-tiap nilai terbesar di setiap daerah yang kita cari. Dengan struktur yang telah kita pelajari, pencarian nilai terbesar di suatu node range tree perlu dilakukan melalui linear search, sehingga kompleksitasnya O(N) dan kurang efisien.

Sebetulnya pencarian nilai terbesar di suatu node range tree ini mengingatkan kita pada masalah klasik, yaitu mencari nilai terbesar dari subbarisan di array alias RMQ (Range Maximum Query).

Strategi Kontes ICPC

Sepanjang berkompetisi ICPC, saya menyadari bahwa dinamika antar anggota tim penting untuk memaksimalkan performa tim. Maksimal di sini berarti berkompetisi sebaik mungkin, sehingga apapun hasil yang didapatkan, tidak ada kekecewaan. Tulisan ini akan membagikan pengalaman saya sepanjang 4 tahun berkompetisi di ACM ICPC.

Perlu diingat bahwa tulisan ini sangat subjektif, yaitu berdasarkan pengalaman saya. Yang Anda alami mungkin berbeda, dan yang saya tuliskan hanya sebagai referensi saja.

---

Komposisi Tim

Tim yang ideal adalah tim yang anggotanya saling melengkapi. Ada anggota yang mampu mengerjakan soal tipe X, ada yang mengerjakan soal tipe Y, dan sebagainya. Namun setiap anggota sebaiknya menguasai seluruh ilmu dasar.

Storm, earth, dan fire dari warcraft (https://blizzardwatch.com)

Ilmu yang setidaknya harus dimiliki setiap anggota adalah coding. Jelas bahwa setiap anggota pasti sudah bisa coding, tetapi yang saya maksud di sini adalah setiap anggota mampu menuliskan kode dengan lancar, minim bug, dan mudah dibaca anggota lainnya. Bila tim membebankan pekerjaan coding ke seorang anggota, maka ia kemungkinan besar akan jenuh, lelah, dan hanya berperan sebagai kuli. Tanpa berperan dalam berpikir mencari solusi, anggota ini bisa saja merasa tidak dihargai...

Buku Pemrograman Kompetitif Dasar Dirilis!

Seperti yang sudah saya sempat bocorkan sebelumnya, saya dan teman-teman dari IA TOKI mempersiapkan materi pembelajaran yang baru.

Materi ini adalah buku yang berjudul "Pemrograman Kompetitif Dasar", atau disingkat PKD.

PKD ini dibuat dengan bahan dasar berupa slide-slide materi di TLX Training Gate yang sebelumnya telah ditulis. Slide-slide ini tidak hanya sekedar dibukukan, sebab banyak bagian yang sebelumnya sulit dipaparkan lewat slide kini dijelaskan lebih mendalam lewat narasi. Terdapat pula 2 bab tambahan, yaitu struktur data nonlinear dan algoritma graf.

 

Tampilan dalam PKD

Buku ini sekarang tersedia dalam bentuk elektronik, Anda dapat mengunduhnya secara gratis di link pada akhir tulisan. Apakah akan ada versi cetaknya? Saya belum tahu. Untuk hal itu mungkin perlu menanti perkembangan yang lebih lanjut, berhubung mencetak dan mendistribusikan buku terlihat seperti pekerjaan yang tidak mudah.

Bagi kalian yang haus akan ilmu dan sedang dalam persiapan OSN komputer, silakan membaca buku ini dan jangan lupa untuk disebarluaskan kepada siapapun yang juga membutuhkan buku ini. Semoga bermanfaat!

[baca selengkapnya di sini]

Riset Belajar OSN Komputer

Beberapa bulan yang lalu, saya sempat kembali aktif menulis. Namun kemudian saya kembali menghilang. Sebenarnya selama saya menghilang, banyak yang saya kerjakan berkaitan dengan competitive programming.

Jadi sekitar bulan September, saya menjadi panitia Gemastik 2017 bagian lomba pemrograman, yang kala itu tuan rumahnya di Universitas Indonesia. Tahun 2016 juga tuan rumahnya UI, tetapi saya sedang mengerjakan proyek dan sibuk membantu seleksi tim inti ACM-ICPC untuk UI. Jadilah saya tidak membantu. Tahun 2017, berhubung saya sudah lebih luang dan sekaligus balas budi kepada UI, saya ikutlah menjadi panitia.

Setelah Gemastik berakhir, saya diajak Aji yang tiba-tiba mau mengurus konten untuk TOKI. Sejauh ini konten TOKI yang saya kerjakan adalah materi TLX Training Gate, yang sudah dimulai sejak 2014. Aji mengajak saya untuk melakukan riset apakah sebenarnya materi dan soal latihan TLX Training Gate ini benar-benar bermanfaat. Sebelumnya saya tidak pernah terpikirkan tentang aspek ini, jadi hanya sekedar menulis saja.

Setelah mendapat hasil kuesioner di grup Facebook Olimpiade Informatika Indonesia, kami menyimpulkan bahwa masih banyak orang yang tidak tahu tentang pembelajaran pemrograman kompetitif di Indonesia. Solusinya adalah dengan membuat 1 halaman situs berisi kumpulan informasi pembelajaran yang singkat, padat, jelas, dan sistematis.

Bersama-sama dengan Mamat dan Fairuzi, kami akhirnya membuat:

https://osn.toki.id/

Seperti yang telah dijelaskan, situs ini adalah 1 halaman berisi kumpulan informasi untuk mulai belajar menuju OSN komputer. Belajar ini maksudnya mulai dari OSK, OSP, sampai OSN komputer. Yang terpenting adalah tulisannya disusun dengan sistematis, jadi tidak bingung dengan sumber pembelajaran yang saat ini berceceran. Seluruh sumber pembelajaran yang dicantumkan dapat diakses secara gratis.

Selain pembuatan situs itu, kami juga menyiapkan konten baru untuk pembelajaran OSN. Konten ini disesuaikan juga dengan hasil riset sebelumnya. Informasi lebih lanjut akan saya berikan ketika konten ini sudah selesai.

Selamat memulai belajar menuju OSN komputer!

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.

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.

Range Update 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 Update

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.

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 ≤ 10⁹

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.

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.

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.