Sliding Window

Lol, blog ini udah lumyan berdebu ya :p anyway, setelah sekian lama gak ngeblog (dan rebutan mau ngeblog ini sama hkf) , saya mau nulis suatu topik yang mungkin namanya agak asing, yaitu sliding window. Menurut saya bisa dibilang rada asing, karena kalo nyoba googling sliding window secara mentah resultnya literally sliding window semua (mungkin banyak yang lagi mau bangun rumah?).

Oke sekarang kita bahas apa itu sliding window. Jadi, sliding window itu teknik yang bisa kita pakai jika problem memiliki 2 kriteria berikut :

• Yang ditanyakan berhubungan dengan subsekuens/segmen yang kontinu, di mana kita biasanya diminta mencari "rentang jendela" yang paling optimal, bisa terpanjang maupun terkecil. Biasanya untuk menentukan window yang valid, ada syarat tertentu.
• Misal i menyatakan batas kanan segmen, dan F(i) menyatakan batas kiri bagi i agar windownya seoptimal mungkin dan valid, maka, untuk tiap
  j>i , berlaku F(j) >= F(i) .

Udah gitu aja kok, simple kan? :p Anyway, kalau misalnya masih agak gak jelas (penjelasan saya emang sering gaje ._.) , saya mau bahas 2 soal sekarang. Yang pertama dari SPOJ, Megatron and his rage

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.
 

  
#include  <cstdio>
#include  <algorithm>
using namespace std;

pair<int,int> ans; 

int TC,p,m,arr[50005],left,sum,r;

int main(){
 scanf("%d",&TC);
 while(TC--){
  ans=make_pair(0,0); //ans.first menyimpan sum
  left=0;             //ans.second menyimpan panjang optimal
  sum=0;
  scanf("%d %d",&p,&m);
  for(r=0 ; r < p; r++){
   scanf("%d",&arr[r]);
   sum+=arr[r];
   
   while(sum > m)   //pengecekan syarat
    sum-=arr[left++];
    
   if(r-left+1 > ans.second){ 
    ans.first=sum;
    ans.second=r-left+1;
   }
   else if(r-left+1 == ans.second)
    ans.first=min(ans.first,sum);
  }
  printf("%d %d\n",ans.first,ans.second);
 }
 return 0;
} 

Well, gitu aja. Nggak terlalu ribet kan? :v

Oke, sekarang lanjut ke soal kedua, IOI 2011 - Ricehub.
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.

Kita bisa menarik beberapa observasi, seperti :

• 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.
• Untuk tiap i<j , kita tahu bahwa batas kiri i pasti <= batas kiri j

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
Sekian dan terima kasih!

Soal yang bisa dipakai latihan untuk sliding window (terurut berdasarkan OJnya, lalu difficultynya menurut saya) :

SPOJ - Broken Keyboard
SPOJ - Megatron and his rage
SPOJ - Thor vs Frost Giants
SPOJ - Help the PM!
TLC - Kucing
UVa - Smallest Sub-Array
IOI 2006 - Deciphering the Mayan Writing
IOI 2011 - Ricehub
IOI 2005 - Garden