Oke sekarang kita bahas apa itu sliding window. Jadi, sliding window itu teknik yang bisa kita pakai jika problem memiliki 2 kriteria berikut :
Misal i menyatakan batas kanan segmen, dan F(i) menyatakan batas kiri bagi i agar windownya seoptimal mungkin dan valid, maka, untuk tiap
Inti dari soal ini adalah, diberikan nilai M sebagai batas, kita diminta mencari segmen yang panjangnya maksimal dengan jumlahan elemennya tidak melebihi M. Serta, jika terdapat beberapa segmen yang panjangnya sama-sama maksimal, ambil yang jumlahan elemennya paling kecil. Secara brutal, soal ini bisa dicoba dengan kompleksitas O(N^2). Akan tetapi, karena itu pasti TLE, maka mari kita lupakan. Mari kita turunkan kompleksitasnya menjadi O(N) dengan sliding window (yay!) .
Sebelum itu, apakah benar soal ini bisa diselesaikan dengan sliding window? Mari kita lihat 2 kriteria yang saya tulis sebelumnya. Kriteria 1 sudah cukup jelas. Kemudian, untuk kriteria 2, bisa dibuktikan benar karena elemen arraynya nonnegatif (jika bisa negatif, statement F(j) >= F(i) bisa salah).
Nah, sekarang bagaimana cara menyelesaikannya? Kita bisa mencatat 2 hal penting, yakni sum(jumlahan sementara) , dan left(batas kiri sekarang). Setiap kali kita memperpanjang segmen, kita cek apakah sum sekarang melebihi M. Jika iya, maka kita perkecil segmen dengan menggerakkan left ke kanan, sambil mengurangi sum dengan elemen array yang bersangkutan. Catat panjang yang maksimal, serta minimalisir sum jika terdapat beberapa yang panjangnya maksimal. Dengan demikian, kita bisa mencapai kompleksitas O(N) yang pasti AC. Berikut sample code saya yang kurang enak dilihat.
Inti dari soal ini adalah, kita diberi array lokasi yang sudah terurut menaik, serta budget.Untuk memindahkan beras dari suatu lokasi ke lokasi lainnya sama dengan jarak antar kedua lokasi.Kita diminta membuat satu hub, terserah lokasi di mana yang penting integer, supaya kita bisa memindahkan beras dari sebanyak-banyaknya lokasi, tanpa melebihi budget yang diberikan. Oiya, beras dari suatu lokasi cuma bisa dipindahkan sekali.
Lokasi yang kita ambil pasti berupa segmen yang kontinu, dan hub yang kita pakai pasti berada di antara lokasi terkiri dan terkanan
Lokasi yang kita pakai pasti median dari lokasi-lokasi.Hal ini akan meminimalisir penggunaan budget dari memindahkan beras dari tiap lokasi.
Selesai mendapatkan observasi itu, tentu kita bisa menggunakan sliding window. Untuk membantu penghitungan budget, kita bisa menggunakan bantuan prefix sum (bisa digoogle, tidak terlalu sulit dicari).
Sebelum menutup postingan jelek ini, saya ingin menekankan juga, bahwa sliding window tidak hanya dipakai untuk mencari rentang yang optimal. Ada kalanya sliding window dipakai untuk mencari banyaknya window yang valid. Selain itu, sliding window tidak hanya bisa dipakai pada 1D saja. Sliding window juga bisa digunakan di 2D, dengan cara membruteforce di satu dimensi dan menjalankan sliding window di dimensi lainnya. Kalo ditanya, saya prefer bruteforce baris (apa sih). Jika ada kritik, saran, dan pertanyaan bisa ditulis di komentar di bawah :3
Soal yang bisa dipakai latihan untuk sliding window (terurut berdasarkan OJnya, lalu difficultynya menurut saya) :