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.

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).

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(log² 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.