Sebenarnya udah mau nulis ini dari lama, cuma meniatkannya gak pernah bisa. Anyway, di post kali ini aku bakal bahas tentang maximum average. Iya, bukan sum. Average.
Kalo mo cerita, soal yang pake trik ini aslinya pernah dikasih ke anak Pelatnas 2017 buat latihan. Cuma gak dibahas. Terus pas APIO beberapa hari setelah latihan itu, ada satu soal yang pake konsep ini. Such a coincidence.
Oiya, dulu aku baca trik ini dulu di e-maxx, pas dulu iseng-iseng baca e-maxx dengan modal translate yandex. Artikel e-maxx yang kubaca.
Ide Utama - PROSJEK
Yaudah deh, langsung aja liat contoh soalnya ya. Soal COCI 2014/2015, PROSJEK.
Soalnya pendek, intinya: Dikasih array ukuran $N$, cari rata-rata maksimum subarray yang ukurannya lebih dari atau sama dengan $K$.
Nah, kalo $K = 1$ kan gampang ya. Cuma jelas pembuat soal gak bakal sepintar itu ngasih $K = 1$. Jadi kita coba gali lagi dari soal ini.
Karena $N$ gede ($3 \times 10^5$), gak mungkin kita coba tiap subarray yang notabene $O(N^2)$. Kita harus cari properti yang mungkin bisa dipakai. Biasanya, kita lempar ide-ide liar:
- Mungkin cari yang sum-nya maksimum?
- Gagal, liat aja $K = 1$
- Mungkin liat yang ukurannya tepat $K$?
- Gagal, liat aja sample 2, dia ngambil yang ukurannya 3 (2 4 3 4)
Sebenarnya apa kesulitan utama kita? Ada 2 hal yang harus dipertimbangkan, yaitu jumlahan elemen dan panjang subarray. Ada 2 variabel yang saling berpengaruh, sehingga mencari optimalnya tidak mudah.
Mari lempar ide liar lagi: Mungkin gak jawabannya bisa di-binary search? Atau dengan kata lain, mungkin gak untuk suatu $x$, ada subarray yang ukurannya lebih dari atau sama dengan $K$ yang punya rata-rata >= $x$?
Biasanya, kalo binary search the answer kita harus bisa validasi suatu tembakan jawaban dengan cepat. Nah, ini gimana cara ngeceknya dengan cepat? Bukannya harus cek satu-satu lagi tiap subarray yang ukurannya seenggaknya $K$? Well, mari kita main-main formula matematika:
$$ \frac{\sum_{i=l}^{r} a_i}{r-l+1} \ge x$$ $$ \sum_{i=l}^{r} a_i \ge (r-l+1) \times x$$ $$ \sum_{i=l}^{r} a_i - (r-l+1) \times x \ge 0$$ $$ \sum_{i=l}^{r} (a_i - x) \ge 0$$
Wah, ada sesuatu yang berguna. Secara ajaib panjang subarray jadi tidak dipertimbangkan lagi.
Katakanlah kita ingin memeriksa apakah ada subarray yang punya rata-rata >= $x$. Kita bisa membuat array baru, $a'$, yang mana $a'_i = a_i - x$. Selanjutnya, cukup memeriksa apakah ada subarray pada $a'$ yang jumlahannya >= 0. Untuk memeriksa yang ukurannya >= $K$, kita bisa simpan nilai minimum prefix sum tiap indeks yang valid. Untuk mengeceknya bisa dalam $O(N)$, sehingga digabung binary search kompleksitasnya jadi $O(N \log a_i)$
Contoh solusi PROSJEK:
Ini soal yang dulu dipake di JCPC CompFest 8. Berkas-berkas terkait soal dapat diakses di sini. Oiya, hampir semua soal CompFest udah ada di TLX. Cuma CompFest 7 sama 8 belum masuk karena sesuatu. Sementara cek soal Road to Hero ini di github aja dulu ya.
Inti soalnya: Dikasih DAG, cari maximum average path dari persimpangan 1 ke persimpangan $N$.
.
.
.
.
.
.
.
.
.
Oke ini intinya kayak pertidaksamaan tadi ya. Cuma sekarang kita pakenya edge dari grafnya. Setelah bobot semua edge dikurangi $x$, maka kita cukup ngecek ada apa nggak path dengan cost >= 0. Berhubung ini DAG jadinya lebih mudah karena tidak ada cycle. Kita cukup mencari longest path dari 1 ke N, yang bisa dicari pakai DP. Sehingga, kompleksitasnya $O((N + M) \log P_i)$.
Contoh solusi dapat dilihat pada github soalnya.
Soal Latihan
Beberapa soal yang menggunakan konsep serupa:
$$ \frac{\sum_{i=l}^{r} a_i}{r-l+1} \ge x$$ $$ \sum_{i=l}^{r} a_i \ge (r-l+1) \times x$$ $$ \sum_{i=l}^{r} a_i - (r-l+1) \times x \ge 0$$ $$ \sum_{i=l}^{r} (a_i - x) \ge 0$$
Wah, ada sesuatu yang berguna. Secara ajaib panjang subarray jadi tidak dipertimbangkan lagi.
Katakanlah kita ingin memeriksa apakah ada subarray yang punya rata-rata >= $x$. Kita bisa membuat array baru, $a'$, yang mana $a'_i = a_i - x$. Selanjutnya, cukup memeriksa apakah ada subarray pada $a'$ yang jumlahannya >= 0. Untuk memeriksa yang ukurannya >= $K$, kita bisa simpan nilai minimum prefix sum tiap indeks yang valid. Untuk mengeceknya bisa dalam $O(N)$, sehingga digabung binary search kompleksitasnya jadi $O(N \log a_i)$
Contoh solusi PROSJEK:
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
const int TRIAL = 50;
const double EPS = 1e-9;
int arr[N];
double psum[N];
int n, k;
void read() {
scanf("%d %d", &n, &k);
for (int i = 1 ; i <= n ; i++) {
scanf("%d", &arr[i]);
}
}
bool check(double x) {
// prefix sum, karene a_l + ... + a_r = prefix_r - prefix_{l-1}
for (int i = 1 ; i <= n ; i++)
psum[i] = psum[i-1] + arr[i] - x;
double mins = 1e9;
for (int i = k ; i <= n ; i++) {
// prefix_{i-k} jadi valid saat iterasi ke-i
mins = min(mins, psum[i - k]);
if (psum[i] - mins > -EPS)
return true;
}
return false;
}
double work() {
double lo = 0, hi = 1e7;
for (int i = 0 ; i < TRIAL ; i++) {
double mid = (lo + hi) / 2;
if (check(mid)) lo = mid;
else hi = mid;
}
return lo;
}
int main() {
read();
printf("%.9lf\n", work());
return 0;
}
Contoh Lain - Road to HeroIni soal yang dulu dipake di JCPC CompFest 8. Berkas-berkas terkait soal dapat diakses di sini. Oiya, hampir semua soal CompFest udah ada di TLX. Cuma CompFest 7 sama 8 belum masuk karena sesuatu. Sementara cek soal Road to Hero ini di github aja dulu ya.
Inti soalnya: Dikasih DAG, cari maximum average path dari persimpangan 1 ke persimpangan $N$.
.
.
.
.
.
.
.
.
.
Oke ini intinya kayak pertidaksamaan tadi ya. Cuma sekarang kita pakenya edge dari grafnya. Setelah bobot semua edge dikurangi $x$, maka kita cukup ngecek ada apa nggak path dengan cost >= 0. Berhubung ini DAG jadinya lebih mudah karena tidak ada cycle. Kita cukup mencari longest path dari 1 ke N, yang bisa dicari pakai DP. Sehingga, kompleksitasnya $O((N + M) \log P_i)$.
Contoh solusi dapat dilihat pada github soalnya.
Soal Latihan
Beberapa soal yang menggunakan konsep serupa:
- PROSJEK (dibahas di post ini)
- Road to Hero (dibahas di post ini)
- Programming Team (+ DP on tree)
- Travelling Merchant (+ macem shortest path)
- Spanning Tree Fraction (+ MST)
Penutup
Trik mencari maximum average ini bisa dibilang kayak wrapper-nya aja, yang beda di tiap soal cuma buat cara cek validitasnya (kayak binary search the answer biasa). Sejujurnya aku nggak ngerti aku ngomong apa di kalimat sebelumnya, semoga kalian ngerti.
Akhir kata, semoga post ini bisa meningkatkan wawasan. Dan semoga aku bisa balik ke Depok dengan selamat, karena sayang amplang-nya kalau nggak dimakan.
0 komentar:
Posting Komentar