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

Oh ya, sebenarnya soal ini adalah penyederhanaan dari soal SPOJ HORRIBLE.


Penggunaan Lazy Propagation?

Dengan struktur BIT, penggunaan lazy propagation agak sulit dilakukan. Alasannya karena untuk melakukan "propagate", diperlukan kompleksitas O(log N). Sebab banyaknya segmen yang berada di bawah suatu segmen pada BIT adalah O(log N). Bandingkan dengan segment tree yang operasi "propagate" dapat dilakukan dalam O(1), berhubung banyaknya segmen di bawah suatu segmen selalu 2.

Terdapat suatu cara untuk menggunakan lazy propagation di BIT, yaitu dengan membuat BIT 1 lagi untuk mengisi "keompongan" struktur BIT (lihat bagian bonus pada pembahasan BIT). Hari ini saya tidak membahas teknik ini.

Strategi penyelesaian yang akan dibahas tidak menggunakan lazy propagation, melainkan dengan permodelan BIT untuk penjumlahan fungsi.


Solusi dengan 2 BIT

Secara umum, solusi ini dapat digunakan apabila:
  1. Elemen ke-i pada array dapat dinyatakan dalam f(i), dengan f(x) = kxxp untuk suatu nilai p yang tetap dan variabel kx.
  2. Operasi yang diperlukan adalah:
    1. Penambahan/pengurangan nilai variabel ka, ka+1, ka+2, ..., kb dengan suatu konstanta v, untuk suatu a dan b.
    2. Pencarian nilai f(1)+f(2)+...+f(x), untuk suatu x.
Soal yang kita hadapi memenuhi syarat-syarat tersebut. Dalam kasus ini, p dapat dianggap 0. Jadi f(x) = kx, yang mana nilai kx sewaktu-waktu ditambah/dikurangi dengan operasi add(a, b, v). Juga dilakukan pencarian f(1)+f(2)+...+f(x), yang merupakan operasi sum(x).

Solusi ini menggunakan 2 struktur array, akan saya sebut arrK dan arrN. arrK akan menyimpan nilai k, dan arrN menyimpan konstanta normalisasi.

Sebagai contoh, perhatikan apa yang terjadi ketika dilakukan add(a, b, v):



Struktur ini dapat diuraikan menjadi 2 grafik:



Pada kasus tersebut, arrK akan bernilai:
  • 0, jika x < a
  • v, jika a ≤ x ≤ b. Perhatikan bahwa yang disimpan adalah "gradien", jadi nilainya selalu v.
  • 0, jika x > b
Sementara itu arrN akan bernilai:
  • 0, jika x < a
  • -(a-1)*v, jika a ≤ x ≤ b
  • b*v - (a-1)*v, jika x > b
Untuk mencari sum(x), caranya adalah: arrK[x]*x + arrN[x].

Sampai saat ini, sangat semuanya terlihat tidak masuk akal. Untuk memahami bagaimana cara kerjanya, perhatikan 3 kasus yang mungkin untuk nilai x. Asumsikan sebelumnya telah dilakukan satu kali add(a, b, v).
  1. Jika x < a, maka sum(x) = 0
  2. Jika a ≤ x ≤ b, maka sum(x) = x*v - (a-1)*v
  3. Jika x > b, maka sum(x) = b*v - (a-1)*v
Penjelasan untuk masing-masing kasus dapat dilihat pada ilustrasi berikut:



Lalu bagaimana apabila telah dilakukan beberapa kali operasi add(a, b, v)? Pada kenyataannya, operasi-operasi add tidak mempengaruhi satu sama lain. Kita tetap dapat mencari sum(x) dengan arrK[x]*x + arrN[x].

Memang jika hanya diperhatikan dari sisi arrK, nilai yang kita miliki tidak masuk akal. Namun ingat bahwa semua operasi yang dilakukan pada indeks sebelum x telah "dinormaisasi" oleh arrN.

Anda dapat menganggap bahwa arrK menyimpan nilai k yang aktif, dan arrN menyimpan konstanta normalisasi untuk operasi-operasi add yang telah dilakukan.

Untuk mengimplementasikan solusi ini pada BIT, kita dapat membuat 2 BIT yang masing-masing merepresentasikan nilai arrK dan arrN. Sebut saja bitK dan bitN adalah kedua BIT tersebut.

Jadi untuk setiap add(a, b, v), lakukan:
  1. update(bitK, a, v)
  2. update(bitK, b+1, -v)
  3. update(bitN, a, (a-1)*v)
  4. update(bitN, b+1, b*v)
Kemudian setiap query(x) dapat dijawab dengan: query(bitK, x)*x + query(bitN, x).


Implementasi

Seperti biasa, implementasi dengan BIT ini sangat mudah ditulis. Berikut adalah solusi untuk soal SPOJ HORRIBLE. Perhatikan bahwa query sum pada soal ini adalah pencarian jumlahan dari suatu rentang a sampai b, yang tentunya dapat dengan mudah didapatkan dengan sum(b)-sum(a-1).



Generalisasi

Untuk soal yang lebih dekat dengan Alien Abduction Again, kini operasi yang ada dimodifikasi menjadi:
  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. (tidak ada perubahan)
  2. sum(x), artinya cari nilai 1*A[1]+2*A[2]+3*A[3]+...+x*A[x].

Terlihat jelas bahwa elemen ke-i pada array tersebut dapat dinyatakan dalam f(i), dengan f(x) = kxx1. Perhatikan apa yang terjadi ketika dilakukan add(a, b, v):


Struktur ini dapat diuraikan menjadi 2 grafik:



Pada kasus tersebut, arrK akan bernilai:
  • 0, jika x < a
  • v, jika a ≤ x ≤ b
  • 0, jika x > b
Sementara itu arrN akan bernilai:
  • 0, jika x < a
  • -(12v + 22v + 32v + ... + (a-1)2v), jika a ≤ x ≤ b
  • (12v + 22v + 32v + ... + b2v) - (12v + 22v + 32v + ... + (a-1)2v), jika x > b
Untuk mencari sum(x), caranya adalah: arrK[x]*(12 + 22 + 32 + ... + x2) + arrN[x].

Coba pahami penguraian grafik pada gambar di atas untuk memahami bagaimana strategi ini bisa benar.

Cara ini juga bekerja untuk sembarang nilai p. Mari kita modifikasi operasi sum menjadi:
sum(x), artinya cari nilai 12A[1]+22A[2]+32A[3]+...+x2A[x].

Kali ini elemen ke-i pada array tersebut dapat dinyatakan dalam f(i), dengan f(x) = kxx2. Ketika dilakukan add(a, b, v), arrK akan bernilai:
  • 0, jika x < a
  • v, jika a ≤ x ≤ b
  • 0, jika x > b
Sementara itu arrN akan bernilai:
  • 0, jika x < a
  • -(13v + 23v + 33v + ... + (a-1)3v), jika a ≤ x ≤ b
  • (13v + 23v + 33v + ... + b3v) - (13v + 23v + 33v + ... + (a-1)3v), jika x > b
Untuk mencari sum(x), caranya adalah: arrK[x]*(13 + 23 + 33 + ... + x3) + arrN[x].


Generalisasi Tingkat Tinggi

Lebih jauh lagi, solusi ini dapat digunakan untuk sembarang fungsi. Tidak harus memenuhi bentuk f(x) = kxxp, melainkan dapat berupa f(x) = kxg(x), dengan g(x) adalah sembarang fungsi dengan parameter x.

Ketika dilakukan add(a, b, v), arrK akan bernilai:
  • 0, jika x < a
  • v, jika a ≤ x ≤ b
  • 0, jika x > b
Sementara itu arrN akan bernilai:
  • 0, jika x < a
  • -(g(1)v + g(2)v + g(3)v + ... + g(a-1)v), jika a ≤ x ≤ b
  • (g(1)v + g(2)v + g(3)v + ... + g(b)v) - (g(1)v + g(2)v + g(3)v + ... + g(a-1)v), jika x > b
Untuk mencari sum(x), caranya adalah: arrK[x]*(g(1) + g(2) + g(3) + ... + g(x)) + arrN[x].

Supaya lebih ringkas, saya akan menuliskannya dalam notasi sigma.

Ketika dilakukan add(a, b, v), \(arrK\) akan bernilai:

  • \(0\), jika \(x \lt a\)
  • \(v\), jika \(a \le x \le b\)
  • \(0\), jika \(x \gt b\)
Sementara itu \(arrN\) akan bernilai:

  • \(0\), jika \(x \lt a\)
  • \(\displaystyle -v\sum_{i=1}^{a-1} g(i)\), jika \(a \le x \le b\)
  • \(\displaystyle v\sum_{i=1}^{b} g(i)-v\sum_{i=1}^{a-1} g(i)\), jika \(x \gt b\)
Untuk mencari sum(x), caranya adalah: \(\displaystyle arrK[x]\left(\sum_{i=1}^{a-1} g(i)\right) + arrN[x]\).

Inilah yang disebut Aji sebagai "Magic BIT". Bagian \(\displaystyle \sum_{i} g(i) \) ia sebut sebagai "konstanta magic". Konstanta ini dapat di-precompute, karena hanya ada O(N) kemungkinan nilai.

Semua ini memang sangat gila, tetapi masuk di akal apabila dicerna. Pengalaman saya sendiri, memahaminya dengan menganalisis grafik yang telah diuraikan membantu dalam pemahaman.


Latihan

Seluruh ilmu ini harus diterapkan pada latihan, supaya terasa dan teruji pemahamannya.


Penutup

Tidak perlu terburu-buru dalam memahami semua ini. Coba dicerna sedikit demi sedikit, sampai Anda mendapatkan intinya.

Memahami teknik ini mungkin tidak seberapa berharga, dan kecil kemungkinan soal sejenis ini akan dikeluarkan lagi. Tapi siapa tahu? ACM ICPC adalah hutan hujan yang gelap, entah hewan buas apa yang ada di depan nantinya. Semoga bermanfaat!

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: