Median

Soal#

Informasi#

• Sumber: IDEAFUSE 2024 - CP Final Round
• Tanggal: 2024-10-19

Arsip#

• TLX

Ringkasan#

Diberikan sebuah array $S$ yang berisi $N$ bilangan bulat berbeda. Diberikan pula suatu indeks $K$ pada array. Carilah subarray terpanjang yang memiliki panjang bilangan ganjil di mana $S[K]$ adalah median dari array tersebut.

Solusi#

Petunjuk#

Pembahasan#

Kita tahu bahwa subarray yang dimaksud pada soal akan memiliki sifat pada Petunjuk 2, yaitu banyaknya bilangan yang lebih kecil dari $S[K]$ sama dengan banyaknya bilangan yang lebih besar dari $S[K]$. Karena kita ingin membuat $S[K]$ adalah elemen dari subarray tersebut, maka untuk mencari subarray yang memenuhi, kita bisa menggunakan strategi berikut.

1. Cari semua subarray $S[L..K - 1]$ (di kiri indeks $K$) dan $S[K + 1...R]$ (di kanan indeks $K$). Subarray juga bisa kosong.
2. Untuk semua subarray $S[L..K - 1]$, cari salah satu subarray $S[K + 1..R]$ yang memenuhi subarray pada soal, yakni panjanganya ganjil dan memenuhi syarat pada Petunjuk 2.

Kita tidak perlu mendaftar semua subarray. Cukup catat saja banyaknya bilangan yang lebih kecil dan lebih besar dari $S[K]$. Kita bisa gunakan teknik mirip prefix sum untuk mencatat informasi tersebut untuk semua subarray. Berikut adalah contoh kode untuk menghitung informasi tersebut.

typedef pair<int, int> pii;

vector <pii> left;
pii count = {0, 0};
for(int L = K - 1; 1 <= L; L--){
    if(S[L] < S[K]) count.first++;
    else if(S[L] > S[K]) count.second++;
    left.push_back(count);
}

vector <pii> right;
count = {0, 0};
for(int R = K + 1; R <= N; R++){
    if(S[R] < S[K]) count.first++;
    else if(S[R] > S[K]) count.second++;
    right.push_back(count);
}

Misal $S = [10, 6, 9, 5, 1, 7, 2, 3, 8, 4]$ dan $K = 4$, sehingga $S[K] = 5$ (kasus uji ke-4 pada contoh masukan kasus uji). Dalam bentuk tabel, berikut adalah hasil eksekusi dari kode di atas. Pasangan bilangan di kiri indeks ke-$K$ adalah isi dari array left dan pasangan bilangan di kanan indeks ke-$K$ adalah isi dari array right.

Untuk mecari subarray yang memenuhi, kita pilih sebuah pasangan bilangan yang nilainya sama atau kita pilih dua pasangan bilangan yang jika dijumlahkan akan bernilai sama.

Pasangan-pasangan bilangan yang bernilai sama antara lain

• (0,0) yang merepresentasikan subarray $S[4..4] = [5]$ dan
• (1,1) yang merepresentasikan subarray $S[4..7] = [5, 1, 7]$.

Sedangkan dua pasangan-pasangan bilangan yang jika dijumlahkan akan bernilai sama antara lain

• (0,1) dan (1,0) yang merepresentasikan subarray $S[3..5] = [9, 5, 1]$,
• (0,1) dan (2,1) yang merepresentasikan subarray $S[3..7] = [9, 5, 1, 7, 2]$,
• (0,1) dan (3,2) yang merepresentasikan subarray $S[3..9] = [9, 5, 1, 7, 2, 3, 8]$,
• (0,2) dan (3,1) yang merepresentasikan subarray $S[2..8] = [6, 9, 5, 1, 7, 2, 3]$, dan
• (0,2) dan (4,2) yang merepresentasikan subarray $S[2..10] = [6, 9, 5, 1, 7, 2, 3, 8, 4]$.

Kita bisa menyederhanakan sebuah pasangan bilangan dengan cara mengurangi setiap bilangan dengan nilai minimum dari kedua bilangan. Contohnya

• (3,1) dapat disederhanakan menjadi (2,0) karena $\min(3, 1) = 1$ dan (3-1,1-1) = (2,0).
• (5,5) dapat disederhanakan menjadi (0,0) karena $\min(5, 5) = 5$ dan (5-5,5-5) = (0,0).
• (2,9) dapat disederhanakan menjadi (0,7) karena $\min(2, 9) = 2$ dan (2-2,9-2) = (0,7).

Jadi, untuk mencari subarray yang memenuhi, kita tinggal cari pasangan bilangan (0,0) atau dua pasangan bilangan yang saling berkebalikan.

Kita bisa menyederhanakannya lebih lanjut dengan cara hanya mencatat satu bilangan saja, yakni hasil pengurangan banyaknya bilangan yang lebih besar dari $S[K]$ dengan banyaknya bilangan yang lebih kecil dari $S[K]$ (atau sebaliknya). Dari tabel pertama, tabel akhirnya adalah sebagai berikut.

Jadi kita hanya perlu mencari bilangan 0 atau dua bilangan yang jika dijumlahkan akan menghasilkan 0. Untuk setiap bilangan pada subarray kiri, cari bilangan paling kanan yang penjumlahannya bernilai 0 agar panjang subarray-nya maksimum. Hal ini dapat dilakukan dengan array atau struktur data map.

Kode#

#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

const int MAXN = 100000;

int T, N, K, ans;
int S[MAXN];
map <int, int> R;

int main(){
    cin >> T;
    for(int t = 1; t <= T; t++){
        R.clear();

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

        ans = 1;
        int diff = 0;
        for(int i = K + 1; i < N; i++){
            if(S[i] > S[K]) diff++;
            else diff--;

            if(diff == 0){
                ans = max(ans, i - K + 1);
            }

            R[diff] = i;
        }

        diff = 0;
        for(int i = K - 1; 0 <= i; i--){
            if(S[i] > S[K]) diff++;
            else diff--;

            if(diff == 0){
                ans = max(ans, K - i + 1);
            }

            if(R.find(-diff) == R.end()) continue;
            ans = max(ans, R[-diff] - i + 1);
        }


        cout << "Case #" << t << ": " << ans << '\n';
    }
    return 0;
}