Yang Seperti DP Matrix ~ Baca Kalau Mau Baca

idk why but i feel like writing tonight

Kali ini mau bahas trik yang kayak DP matrix, tapi bukan.

Kasusnya rada khusus, biasanya main di ngitung banyak sekuens (gak selalu sih). Tapi secara kompleksitas lebih kenceng, plus ngodingnya lebih gampang. Trik ini sendiri aku gak sengaja nemunya pas ngerjain soal SPOJ yang bakal kubahas di sini. Nggak banyak yang solve, cuma mungkin ini karena emang nyari soal di SPOJ repot.

Prerequisite

Secara konsep teknik ini harusnya nggak terlalu sulit asal ngerti DP sama fast modular exponentiation (perpangkatan dalam $O(\log N)$. Kalo ngerti DP matrix (matrix exponentiation) bagus, cuma akan tiba saatnya hal itu harus dilupakan terlebih dahulu.

Ide Utama - The Toy Store

Untuk ngejelasin idenya, aku rasa mending langsung liat soal yang bikin aku dapet trik ini. Tautan menuju soal: SPOJ DCEPC14F - The Toy Store

Abstrak soal: Dikasih array $A$ ukuran $N$, terus 3 bilangan $M, K, X$. Cari banyaknya sekuens $S$ berukuran $K$, yang mana $1 \leq S[i] \leq N$ dan $ \sum_{i=1}^{K} A[S[i]] \equiv X \pmod{M}$.

Coba dipikir dulu ya, sebelum lanjut ke bawah.

Oke, jadi kalo ngeliat soal ini mungkin kebayang modelin jadi graf. Misal $cnt[i]$ menyatakan banyak elemen di $A$ yang hasilnya dimodulo $M$ adalah $i$. Maka, kita bisa membuat graf dengan nomor 0 sampai $M-1$, yang mana terdapat $cnt[i]$ edge dari $y$ ke $(y + i) \mod M$ untuk tiap $0 \leq y \lt M$.

Selanjutnya, pertanyaan tadi bisa diubah menjadi "ada berapa banyak jalan berbeda dari 0 ke $X$?" Tentunya, hal ini bisa didapat dengan matrix exponentiation. Buat adjacency matrix, lalu pangkatkan sebanyak $K$. Tinggal ambil entri $[0][X]$-nya.

Nah, masalahnya sampai kita bisa membajak time limit-nya jadi segede gaban, kita pasti bakal dapet TLE. Ada $T$ kasus uji, dan untuk tiap kasus uji kita butuh $O(M^3 \log K)$ operasi. Pas masukin kalkulator, pasti angkanya lumayan gede. Aku sendiri udah coba optimasi beberapa kali, TLE semua.

Optimization is fun, sampe akhirnya banting setir

Nah, bisa dilihat juga kalo dulu aku ninggalin soal ini lama, dan baru dapet inspirasi pas nyoba ngerjain lagi.

Pada tahap ini, tolong lupakan DP matrix dulu.

Jadi intinya: ini kan sekuens, kita bisa kan anggep dia sebagai penggabungan 2 sekuens lainnya? Dengan kata lain, misal banyak cara membuat sekuens dengan panjang $L$, dan hasil jumlahannya $Z$ dalam modulo $M$ kita nyatakan sebagai $ways(L, Z)$. Maka, kita bisa cari nilai tersebut dengan cara sebagai berikut:

$$ways(L, Z) = \sum_{i=0}^{M-1} ways(L', i) \times ways(L-L', (Z-i) \mod{M})$$

Dengan $L'$ menyatakan panjang sekuens pertama dari 2 sekuens.

Kenapa bisa begitu? Ingat kaidah perkalian dari SMP atau SMA. Kalau kita potong jadi 2 sekuens, masing-masing panjangnya $L'$ dan $L-L'$, banyak cara di 2 sekuens itu saling independen. Untuk menggabungkannya, kita harus mengalikannya. Apabila sekuens pertama memiliki hasil jumlahan $i$, agar menjadi $Z$ ketika digabung dengan sekuens kedua, maka sekuens kedua harus memiliki jumlahan $(Z-i)\mod M$. Ya, kurang lebih gitu.

Oiya, harusnya cukup jelas ya kalau $ways(1, Z) = cnt[Z]$. Lalu, $ways(0, 0) = 1$.

Selanjutnya, kita bisa mencari $ways(L, *)$ (* artinya dari 0 sampai $M-1$) dalam $O(M^2)$ apabila kita punya $ways(L', *)$ dan $ways(L-L', *)$. Ini sebenarnya bisa kita bawa ke ranah fast exponentiation.

Karena kita punya $ways(1, *)$, maka kita bisa mendapatkan $ways(2, *)$ dengan "mengalikan" $ways(1, *)$ dengan dirinya sendiri. Selanjutnya, dapat dilihat bahwa kita bisa mendapatkan semua $ways(2^i, *)$ dengan mudah. "Kalikan" dengan $ways(2^i, *)$, hingga jumlahan panjangnya $K$, dan hasilnya bisa didapat di entri $X$. Kita hanya perlu $O(\log K)$ "perkalian", yang mana tiap "perkalian" hanya butuh $O(M^2)$ operasi. Maka, untuk tiap kasus uji kita hanya butuh $O(M^2 \log K)$, dan cukup untuk mendapatkan AC.

Contoh solusi:

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

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;

int A[N];
int n, m, k, x;

void read() {
  scanf("%d", &n);
  for (int i = 0 ; i < n ; i++) {
    scanf("%d", &A[i]);
  }
  scanf("%d %d %d", &m, &k, &x);
}

// "perkalian" untuk dapat ways(L, *)
vector<int> multiply(vector<int> a, vector<int> b) {
  vector<int> ret(m, 0);

  for (int Z = 0 ; Z < m ; Z++)
    for (int i = 0 ; i < m ; i++) {
      int j = (Z - i + m) % m;
      
      // jumlahan = i dari a, jumlahan = j dari b
      ret[Z] = (ret[Z] + 1ll * a[i] * b[j]) % MOD;
    }
  
  return ret;
}

vector<int> power(vector<int> base, int pwr) {
  // identitas; sekuens kosong jumlahannya 0
  vector<int> ret(m, 0);
  ret[0] = 1;

  while (pwr) {
    if (pwr & 1) ret = multiply(ret, base);
    base = multiply(base, base);
    pwr >>= 1;
  }

  return ret;
}

int work() {
  vector<int> cnt(m, 0);
  for (int i = 0 ; i < n ; i++) {
    cnt[A[i] % m]++;
  }

  cnt = power(cnt, k);
  return cnt[x];
}

int main() {
  int t; cin >> t;
  for (int tc = 1 ; tc <= t ; tc++) {
    read();
    printf("%d\n", work());
  }
  return 0;
}

Simple and clean. Tidak perlu nulis perkalian matriks dan lebih ngebut :P

Contoh Lain - Pasti Menang!

shamelessly using own problem for example again, lel

Tautan menuju soal: Final SCPC CompFest 9 - Pasti Menang!

Abstrak soal: Ada game, yang mana game-nya dimainkan di DAG, dengan tiap node-nya antara tidak ada bidak, atau mungkin ada >= 1 bidak. Total ada K bidak. Akan dilakukan permainan yang dilakukan oleh 2 orang, dengan gerakan tiap orang adalah memindahkan salah satu bidak ke node lain yang ada direct edge-nya. Pemain kalah kalau tidak bisa menggerakkan bidak. Kita mau bikin konfigurasi peletakan bidak sedemikian hingga kalau 2 orang ini mainnya optimal, pasti orang pertama yang menang. Tentuin banyak caranya.

Udah nyoba bikin abstrak tapi masih kurang ringkas kayaknya ;_; Maaf ya. Anyway, ini soal dulu pas lombanya nggak ada yang AC ;_; Harusnya dengan pengetahuan dari paragraf sebelumnya + sesuatu cukup sih untuk solve soal ini. Coba kerjain dulu ya, baru scroll ke bawah.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

Observasinya:

Kalau bidaknya udah diletakkan bakal jadi nim-game, yang berdasarkan Sprague-Grundy Theorem pemain pertama pasti menang jika dan hanya jika hasil xor dari nimber $K$ bidak itu bukan 0
Nimber maksimum dibatasi oleh $\sqrt M$, kasarannya maksimum ada sekitar 400. Artinya, hasil xor dari nimber $K$ bidak maksimum 511.

Kita bisa modelkan ini jadi permasalahan The Toy Store, tapi di sini kita pakainya xor. Contoh solusi yang kucomot dari githubku:

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

const int MOD = 1e9 + 8;
const int N = 5e4 + 5;
const int MAX_GRUNDY = 512;

vector<int> multiply(vector<int> &a, vector<int> &b) {
    vector<int> ret(MAX_GRUNDY, 0);

    for(int i = 0 ; i < MAX_GRUNDY ; i++)
        for(int j = 0 ; j < MAX_GRUNDY ; j++)
            ret[i] = (ret[i] + 1ll * a[j] * b[i ^ j]) % MOD;

    return ret;
}

vector<int> power(vector<int> base, int po) {
    vector<int> ret(MAX_GRUNDY, 0);
    ret[0] = 1;

    while(po) {
        if(po & 1) {
            ret = multiply(ret, base);
        }

        base = multiply(base, base);
        po >>= 1;
    }

    return ret;
}

int grundy[N];
vector<int> adj[N];
int n, m, k;

void read() {
    scanf("%d %d %d", &n, &m, &k);

    for(int i = 0 ; i < m ; i++) {
        int u, v;
        scanf("%d %d", &u, &v);

        adj[u].push_back(v);
    }
}

void prepare() {
    for(int i = 1 ; i <= n ; i++) {
        set<int> s;

        for(int x : adj[i]) {
            s.insert(grundy[x]);
        }

        for(int j = 0 ; ; j++)
            if(!s.count(j)) {
                grundy[i] = j;
                break;
            }
    }
}

int solve() {
    vector<int> ret(MAX_GRUNDY, 0);

    for(int i = 1 ; i <= n ; i++) {
        ret[grundy[i]]++;
    }
    ret = power(ret, k);

    int ans = 0;
    for(int i = 1 ; i < MAX_GRUNDY ; i++) {
        ans = (ans + ret[i]) % MOD;
    }

    return ans;
}

void reset() {
    for(int i = 1 ; i <= n ; i++) {
        adj[i].clear();
    }
}

int main() {
    int t; 
    scanf("%d", &t);

    for(int tc = 1 ; tc <= t ; tc++) {
        read();
        prepare();
        printf("%d\n", solve());
        reset();
    }
    return 0;
}

Kompleksitas akhirnya per kasus uji adalah $O(M \log M + (\sqrt M)^2 \log K)$ = $O(M \log M + M \log K)$.

Soal Latihan

Aku gak terlalu tahu sih soal-soalnya, rasanya gak banyak yang emang harus banget pake ini. Beberapa yang bisa dipakai:

The Toy Store (dibahas di post ini)
Pasti Menang! (dibahas di post ini)
Exponentiation Table (+ cycle finding)

Penutup

Trik ini lumayan lucu sih, kalo menurutku. Terus ngodingnya juga nggak terlalu susah, nggak harus tau perkalian matriks (aku kadang rada pusing ngaliin matriks, tapi nggak akut kok). Mungkin rada spesifik kasusnya, tapi yaa lumayan berguna. Selain itu, walaupun dibahasnya tadi di ranah jumlah dan xor, aku sendiri yakin kalo bisa dengan operator lain juga, misal hasil kali. Oiya, untuk yang soal latihan terakhir, itu modelinnya rada beda, jadi itu bisa jadi latihan yang bagus :P

Akhir kata, semoga post ini bisa bermanfaat dalam menambah wawasan.

Baca Kalau Mau Baca

Kamis, 01 November 2018

Yang Seperti DP Matrix

1 komentar:

About

Categories