Amar dan Kina

Soal#

Informasi#

• Sumber: CompFest 2014 - Final CP Mahasiswa
• Tanggal: 2014-09-21

Arsip#

• TLX

Ringkasan#

Diberikan sebuah array $A$ berisi bilangan bulat positif. Untuk suatu segmen array, sebuah bilangan $X$ dikatakan sebagai angka spesial apabila $X$ muncul sebanyak tepat $X$ kali pada segmen array tersebut. Hitunglah total banyaknya angka spesial dari semua segmen array dengan panjang $K$ pada $A$.

Solusi#

Petunjuk#

Pembahasan#

Seperti pada Petunjuk 1, mari kita iterasi setiap segmen dari kiri ke kanan. Teknik ini juga dikenal sebagai sliding window karena kita bisa bayangkan terdapat sebuah window/segmen yang selalu bergeser ke kanan.

Untuk setiap segmen, kita catat kemunculan/frekuensi setiap bilangan. Lalu kita hitung banyaknya angka spesial pada segmen dengan memanfaatkan informasi kemunculan setiap bilangan.

Bagian terpenting dari solusi di atas adalah bagaimana cara untuk mencatat kemunculan bilangan pada suatu segmen. Apabila kita melakukannya secara naif, yakni dengan melakukan iterasi untuk setiap bilangan pada segmen, maka algoritma akan berjalan dengan waktu yang lama. Untuk itu, mari kita cari cara yang lebih efisien untuk menghitung kemunculan bilangan.

Kita kembali lagi ke teknik sliding window. Saat window bergeser ke kanan, satu bilangan di kanan akan ditambahkan ke segmen serta satu bilangan di kiri akan dihapus. Oleh karena itu, jika kita sudah memiliki informasi kemunculan bilangan pada window yang lama, maka kita tidak perlu menghitung lagi semua kemunculan bilangan pada window yang baru. Kita hanya perlu memperbarui informasi kemunculan bilangan yang ditambahkan ke window dan dihapus dari window.

Awalnya, kita hitung kemunculan bilangan pada segmen paling kiri, yang kita simpan dengan menggunakan array. Lalu, kita hitung banyaknya angka spesial pada segmen tersebut, yang kita simpan ke dalam sebuah variabel dan kita tambahkan ke jawaban akhir. Kita akan memperbarui kedua informasi tersebut setiap kita menggeser window.

Saat kita menggeser window ke kanan, kita menambahkan satu bilangan, sehingga kemunculan bilangan tersebut bertambah satu. Jika kemunculan bilangan yang ditambahkan membuat bilangan tersebut menjadi angka spesial, maka kita tambahkan satu ke variabel yang mencatat banyaknya angka spesial. Namun, jika sebelumnya bilangan tersebut merupakan angka spesial, maka kita kurangi satu dari variabel. Lakukan hal yang serupa pada bilangan yang dihapus dari window. Pada akhir setiap langkah iterasi, tambahkan nilai variabel ke jawaban akhir.

Kode#

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

const int MAXX = 1'000'000;

int T, N, K;
int A[MAXX];
lli ans, special_cnt;
int cnt[MAXX + 1];

void update(int x, bool add){
    // numbers greater than K
    // are impossible to become
    // a special number
    if(x > K) return;

    if(add){
        cnt[x]++;
        if(cnt[x] == x){
            special_cnt++;
        }
        else if(cnt[x] == x + 1){
            special_cnt--;
        }
    }
    else{
        cnt[x]--;
        if(cnt[x] == x){
            special_cnt++;
        }
        else if(cnt[x] == x - 1){
            special_cnt--;
        }
    }
}

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

    cin >> T;
    while(T--){
        cin >> N >> K;
        for(int i = 0; i < N; i++){
            cin >> A[i];
        }

        ans = special_cnt = 0;
        for(int i = 0; i < K; i++){
            update(A[i], 1);
        }
        ans += special_cnt;

        for(int i = K; i < N; i++){
            update(A[i], 1);
            update(A[i - K], 0);
            ans += special_cnt;
        }

        cout << ans << '\n';

        // reset
        for(int i = 1; i <= K; i++){
            cnt[i] = 0;
        }
    }
    return 0;
}