Parallel Binary Search

Kembali lagi ke postingan tentang algo \ :v /
Jadi, kali ini saya mau ngebahas salah satu teknik yang jarang dipake dan mungkin tidak terlalu berguna, namun karena menarik dan lucu (?) jadinya pengen saya bahas :3

Sooo.. dari judul kan bilangnya Parallel Binary Search?  Itu apaan? Binser pake multi-threading? Sebenarnya, nggak ada term yang bener-bener umum dipake untuk strategi ini. Cuma karena kalo di CF biasanya nyebutnya begini, yaudah saya sebut begini juga. Atau enakan binser berjamaah?

Biasanya, teknik ini dipake untuk soal yang di-solve secara offline. Ada kan soal-soal query yang perlu di-solve secara offline kayak pake Mo's Algorithm. Gampangnya, ini Mo's yang O(log N), bukan O(sqrt N). Terus, ketika saya mengatakan binser berjamaah, saya tidak terlalu becanda. Memang, di teknik ini, kita melakukan semua binary search sekaligus. Biar mudah, lihat contoh soal ya. Connecting Graph

Kalo males baca, intinya gini. Ada N vertex dan M operasi, dimana operasinya itu:

1. Bikin jalan antara u dan v
2. Nanya kapan vertex u dan v pertama kali terhubung, baik langsung maupun tidak langsung. Jawab sesuai kondisi graf saat ini (bisa aja u dan v kehubung nantinya, tapi kalo sekarang belum, -1).

Ada solusi yang pake sparse table, bahkan kata Anthony bisa O(N log N) secara online. Tapi, biar sesuai dengan post ini, ayo dibahas dengan parallel binary search :3

Jika sudah tau disjoint set, maka solusi O(M log M) per query cukup trivial. Kita bisa binary search jawabannya, dan lakukan penggabungan dalam O(M) menggunakan disjoint set. Kemudian, cek keterhubungan bisa O(1). Cuma, pasti TLE. Bagaimana mengakalinya?

Sebenarnya, apa perlu kita ngelakuin semua itu untuk tiap pertanyaan masing-masing sekali? Apa nggak bisa kita ngelakuin semuanya bersamaan? Jawabannya: Bisa!

Ide utamanya, untuk tiap pertanyaan kita simpen low dan high dari binary searchnya. Kemudian, kita buat O(M) vector untuk menyimpan proses. Jadi, misalnya:

• Query ke-1 memiliki low = 2, high = 5, mid = 3
• Query ke-2 memiliki low = 3, high = 10, mid = 6
• Query ke-3 memiliki low = 3, high = 4, mid = 3

Maka, isi vectornya:

• vector[3] berisi {1,3}
• vector[6] berisi {2}

Jadi, tiap isi vector[x] menyatakan query-query yang memiliki nilai mid senilai x. Nah, selanjutnya bagaimana?

Binary search akan berhenti ketika low == high. Itu akan diterapkan di sini. Kurang lebih, algonya:

1. Cek apakah low == high untuk semua query
2. Jika iya, berhenti. 
3. Jika tidak, ke langkah 4
4. Lakukan loop untuk "mengulang" semua proses update dari awal
5. Ketika di proses ke-i, cek untuk tiap isi vector[i]
6. Update low dan high untuk setiap isi vector[i], sekalian masukkan ke tempat barunya jika low < high
7. Kembali ke langkah 1

Aneh? emang. 

Untuk mempermudah, kita bisa kembali ke soal tadi. Pertama, kita tahu untuk update dan mengecek keterhubungan, kita bisa menggunakan disjoint set. Selanjutnya, kita tinggal mengimplementasikan algo di atas. Contoh solusi:

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

vector<int> proc[N];
int lo[N], hi[N], pos[N];
int pset[N];
int n,m,ask;

int tipe[N], a[N], b[N];

// inisialisasi disjoint set
void reset() {
  for(int i = 1 ; i <= n ; i++)
    pset[i] = i;
}

// cari root disjoint set
int finds(int x) {
  return x == pset[x] ? x : pset[x] = finds(pset[x]);
}

// menggabungkan disjoint set
void join(int u,int v) {
  u = finds(u); v = finds(v);
  pset[u] = v;
}

// baca input
void read() {
  scanf("%d %d",&n,&m);
  for(int i = 1 ; i <= m ; i++)
    scanf("%d %d %d",tipe + i,a + i,b + i);
}

// jawab-jawabin query
void solve() {
  ask = 0;
  // inisialisasi low dan high
  for(int i = 1 ; i <= m ; i++)
    if(tipe[i] == 2) {
      lo[ask] = 1;
      hi[ask] = i + 1;
      pos[ask] = i;

      proc[(i + 2) / 2].push_back(ask);
      ask++;
    }

  bool change = 1;
  // O(log M)
  while(change) {
    change = 0;
    reset();

    // O(M)
    for(int i = 1 ; i <= m ; i++) {
      // O(1)
      if(tipe[i] == 1) join(a[i],b[i]);

      // proses semua query yang mid-nya sekarang di i
      while(!proc[i].empty()) {
        int posisi = proc[i].back();
        int idx = pos[posisi];
        proc[i].pop_back();

        int u = a[idx];
        int v = b[idx];

        // O(1)
        if(finds(u) == finds(v)) {
          hi[posisi] = i;
        }
        else {
          lo[posisi] = i+1;
        }

        // masih ada yang belum selesai
        if(lo[posisi] < hi[posisi]) {
          proc[(lo[posisi] + hi[posisi]) / 2].push_back(posisi);
          change = 1;
        }
      }
    }
  }

  // output semua jawaban
  for(int i = 0 ; i < ask ; i++) {
    int ret = -1;
    if(lo[i] <= pos[i]) ret = lo[i];
    printf("%d\n",ret);
  } 
}

int main() {
  int t; scanf("%d",&t);
  for(int tc = 1 ; tc <= t ; tc++) {
    read();
    solve();
  }
  return 0;
}

Kompleksitasnya bisa dilihat dari atas. Kita hitung per-update dan query:

• Update: Ada O(log M) phase, dan tiap phase ada O(M) update yang masing-masing O(1). Total: O(M log M)
• Query: Ada O(log M) phase, dan tiap phase ada O(M) query yang masing-masing O(1). Total: O(M log M)
• Totalnya: O(M log M)

Cukup buat AC.

Nah, tapi kalo gitu doang kan kurang berasa. Makanya, kita lanjut ke soal yang bikin saya kenal strategi ini, SPOJ - METEORS

(Males jelasin soalnya, baca sendiri ya)

Jadi, untuk update, kan dibutuhkan range update. Sebenarnya, bisa pakai BIT yang range update point query. Nah, itu juga bisa dibuat pakai segment tree? Nah, kenapa saya sebut segment tree?

Salah satu strategi yang bisa dipakai adalah persistent segment tree. Kalau gak tahu, persistent segment tree itu segment tree yang nyimpen banyak versi selama dia di-update, hanya dengan tambahan O(log N) memory. Total memory yang dia butuhkan adalah O(N log N).

Nah, aplikasinya gimana? Kita bisa bikin dulu persistent segment tree-nya, terus untuk mencari tau pendapatan di suatu waktu bisa O(banyak_sector * log(M)), dengan nge-query di segment tree versi kesekian.

Cuma, katanya solusi ini MLE.
Nah, di sini kita bisa ngeliat "power" dari parallel binary search: Dia bisa ngegantiin persistent segment tree untuk kasus ini! Lebih tepatnya, dari segi memory. Persistent segment tree membutuhkan O(N log N) memory untuk N versi dan data. Sedangkan, dalam menjalankan parallel binary search, yang dibutuhkan hanya O(N) memory!

Jadi, kita bisa menyelesaikan soal METEORS dengan parallel binary search. Update-nya cukup menggunakan BIT, dan query-nya tinggal panggil query di BIT. Analisis kompleksitasnya?

• Ingat, ada O(log K) phase, karena binary search dimulai dengan low = 1 dan high = k atau k+1 untuk mempermudah
• Update: Tiap phase, ada O(K) operasi, masing-masing O(log M). Total untuk update: O(K log M log K) 
• Query: Total, ada M sector yang dihitung nilainya (total dari N state). Untuk satu sector, mengecek nilainya O(log M) karena BIT. Total untuk query: O(M log M log K)
• Sehingga, totalnya O((M + K) log M log K)

Cukup untuk mendapatkan AC. Saya menyarankan mengerjakan soal ini karena memang bagus. Namun, in case stres, contoh solusi bisa dilihat di sini

Soalnya memang gak banyak, soal yang bisa dipakai latihan:

Connecting Graph (dibahas di post ini)
SPOJ - METEORS (dibahas di post ini)
CF - Sign on Fence

Sekian dulu ya :v