Petualangan Codemon

Soal#

Informasi#

• Sumber: CompFest 2012 - Penyisihan CPC Senior

Arsip#

• TLX

Ringkasan#

Terdapat $N$ jenis Codemon dan $M$ jurus berbeda. Codemon jenis $i$ memiliki level $L_i$, kekuatan $P_i$, dan awalanya menguasai $S_i$ jurus unik. Codemon jenis $j$ dapat menguasai jurus-jurus tambahan dari Codemon jenis $i$ apabila $L_i > L_j$ dan $P_i > P_j$. Untuk setiap Codemon, hitunglah banyak jurus maksimum yang dapat dikuasainya!

Solusi#

Petunjuk#

Pembahasan#

Untuk memudahkan, misal $A_i$ menyatakan himpunan jurus yang dikuasai oleh Codemon jenis $i$.

Jelas bahwa seekor Codemon jenis $j$ dapat belajar kepada semua Codemon yang memenuhi syarat agar menguasai jurus sebanyak-banyaknya. Solusi tersebut dapat diimplementasi dengan pseudocode berikut.

for each j from 1 to N do
    let Aj' = Aj
    for each i from 1 to N do
        if Li > Lj and Pi > Pj then
            Aj' = Aj' ∪ Ai
    print |Aj'|

Mari kita lakukan optimisasi pada solusi di atas. Daripada menggunakan himpunan untuk merepresentasikan jurus-jurus yang dikuasai oleh seekor Codemon, kita bisa menggunakan bitmask. Codemon jenis $i$ menguasai jurus $A_{ik}$ jika dan hanya jika bit pada posisi ke-$A_{ik}$ bernilai $1$. Misal $B_i$ menyatakan representasi bitmask dari himpunan jurus yang dikuasai oleh Codemon jenis $i$. Untuk merepresentasikan operasi penggabungan himpunan, kita bisa menggunakan operasi bitwise or. Selain itu, kita juga membutuhkan suatu fungsi untuk menghitung banyaknya bit bernilai $1$ pada suatu bitmask, seperti fungsi __builtin_popcount dari GCC.

for each j from 1 to N do
    let Bj' = Bj
    for each i from 1 to N do
        if Li > Lj and Pi > Pj then
            Bj' = Bj' | Bi
    print count_one_bits(Bj')

Untuk suatu $j$, jika kita bisa mengetahui hasil operasi bitwise or dari semua $B_i$ di mana $L_i > L_j$ dan $P_i > P_j$, kita bisa menghilangkan satu tingkat perulangan. Misal $\text{query}(l, p)$ memberikan hasil operasi bitwise or dari semua $B_i$ di mana $L_i \ge l$ dan $P_i \ge p$. Berikut adalah pseudocode dari solusi yang menggunakannya.

for each j from 1 to N do
    let Bj' = Bj | query(Lj + 1, Pj + 1)
    print count_one_bits(Bj')

Kita dapat menggunakan struktur data seperti segment tree dua dimensi untuk mengimplementasikannya secara efisien.

Terdapat solusi yang lebih sederhana dan efisien dari solusi sebelumnya. Kita buat sebuah array, misalnya bernama $a$, dengan panjang setidaknya $\max P_i$ dan awalnya berisi nol. Array $a$ bertujuan untuk menyimpan suatu bitmask yang merepresentasikan himpunan jurus. Didefinisikan pula dua fungsi yang berkerja pada $a$:

1. $\text{query}(p)$ yang menghasilkan nilai dari $a_p \ | \ a_{p + 1} \ | \ \dots \ | \ a_{|a|}$ dan
2. $\text{update}(p, b)$ yang mengubah nilai $a_p$ menjadi $a_p \ | \ b$.

Bitmask yang merepresentasikan himpunan jurus maksimal yang bisa dikuasai oleh Codemon jenis $j$ adalah $B_j \ | \ \text{query}(P_j + 1)$. Setelah itu, kita akan memanggil $\text{update}(P_j, B_j)$. Iterasi dimulai dari Codemon yang memiliki level tinggi terlebih dahulu.

let C = array of Codemons
sort C by level in descending order
for each c in C do
    let j = the type of Codemon c
    let Bj' = Bj | query(Pj + 1)
    answer[j] = count_one_bits(Bj')
    update(Pj, Bj)

for each j from 1 to N do
    print answer[j]

Namun, solusi di atas masih belum tepat. Bisa saja terdapat dua jenis Codemon $j$ dan $k$ di mana

• $L_j = L_k$,
• $P_j < P_k$, dan
• dilakukan pencarian jawaban pada Codemon jenis $k$ terlebih dahulu.

Berikut adalah kasus uji yang bisa menyebabkan solusi di atas menjadi salah.

2 1
1 2 1
1
1 1 0

Oleh karena itu, kita bisa melakukan pemanggilan fungsi $\text{update}$ setelah semua Codemon dengan level yang sama telah dicari jawabannya. Kita bisa mengimplementasikannya menggunakan dua pointer, mengkategori Codemon berdasarkan level, atau mengurutkan Codemon berdasarkan kekuatan secara menaik apabila levelnya sama. Sedangkan fungsi $\text{query}$ dan $\text{update}$ dapat diimplementasi secara efisien dengan menggunakan segment tree.

Kode#

#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long int lli;

struct codemon {
    int idx, L, P, S;
    lli B;
};

const int MAXN = 50000;
const int MAXL = 50000;
const int MAXP = 50000;

int N, M;
lli ans[MAXN];
lli ST[4 * MAXP];
map <int, vector<codemon>, greater<int> > L;

void update(int node, int l, int r, const int& idx, const lli& val){
    if(l == r){
        ST[node] |= val;
        return;
    }

    int m = (l + r)/2;
    if(idx <= m)
        update(2 * node + 1, l, m, idx, val);
    else
        update(2 * node + 2, m + 1, r, idx, val);
    ST[node] = ST[2 * node + 1] | ST[2 * node + 2];
}

lli query(int node, int l, int r, const int& ql, const int& qr){
    if(ql > qr || r < ql || qr < l) return 0;

    if(ql <= l && r <= qr) return ST[node];

    int m = (l + r)/2;
    return  query(2 * node + 1, l, m, ql, qr) |
            query(2 * node + 2, m + 1, r, ql, qr);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> N >> M;

    int mxP = 0;
    for(int i = 0; i < N; i++){
        codemon c;
        cin >> c.L >> c.P >> c.S;
        c.L--, c.P--;
        c.B = 0;
        c.idx = i;
        
        while(c.S--){
            int Bi;
            cin >> Bi;
            Bi--;
            c.B |= 1LL << Bi;
        }

        mxP = max(mxP, c.P);
        L[c.L].push_back(c);
    }

    for(const auto& p : L){
        const int& Li = p.first;
        const vector<codemon>& C = p.second;
        for(const codemon& c : C)
            ans[c.idx] = query(0, 0, mxP, c.P + 1, mxP) | c.B;

        for(const codemon& c : C)
            update(0, 0, mxP, c.P, c.B);
    }

    for(int i = 0; i < N; i++)
        cout << __builtin_popcountll(ans[i]) << '\n';
    return 0;
}

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long int lli;

struct codemon {
    int idx, L, P, S;
    lli B;
};

const int MAXN = 50000;
const int MAXP = 50000;

int N, M, mxP = 0;
lli ST[4 * MAXP];
codemon C[MAXN];
lli ans[MAXN];

lli _query(int node, int l, int r, const int& ql, const int& qr){
    if(ql > qr || r < ql || qr < l) return 0;

    if(ql <= l && r <= qr) return ST[node];

    int m = (l + r)/2;
    return  _query(2 * node + 1, l, m, ql, qr) |
            _query(2 * node + 2, m + 1, r, ql, qr);
}

lli query(const int& p){
    return _query(0, 0, mxP, p, mxP);
}

void _update(int node, int l, int r, const int& idx, const lli& val){
    if(l == r){
        ST[node] |= val;
        return;
    }

    int m = (l + r)/2;
    if(idx <= m)
        _update(2 * node + 1, l, m, idx, val);
    else
        _update(2 * node + 2, m + 1, r, idx, val);
    ST[node] = ST[2 * node + 1] | ST[2 * node + 2];
}

void update(const int& p, const lli& b){
    _update(0, 0, mxP, p, b);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> N >> M;
    for(int i = 0; i < N; i++){
        codemon& c = C[i];
        cin >> c.L >> c.P >> c.S;
        c.L--, c.P--;
        c.B = 0;
        c.idx = i;
        
        while(c.S--){
            int Bi;
            cin >> Bi;
            Bi--;
            c.B |= 1LL << Bi;
        }
        
        mxP = max(mxP, c.P);
    }

    sort(C, C + N, [](const codemon& x, const codemon& y){
        return x.L > y.L || (x.L == y.L && x.P < y.P);
    });
    for(const auto& c : C){
        ans[c.idx] = query(c.P + 1) | c.B;
        update(c.P, c.B);
    }

    for(int i = 0; i < N; i++)
        cout << __builtin_popcountll(ans[i]) << '\n';
    return 0;
}