Skip to main content

Monge Property Binary Search

Sumber: Mathfirst


Sudah lama tidak menulis materi disini. Blogku selalu ada draft dan ini upaya untuk mengurangi bebanku (mumpung liburan :v). Kebetulan di waktu aku menyelesaikan blog ini, ada kontes yang menggunakan tekniknya yaitu COCI 2018/2019 round 4 (Akvizna).

Oiya, teknik ini biasa dikenal dengan "IOI 2016 Aliens Trick"

Konsep Dasar

Soal Motivasi: APIO 2007 Backup Link

Pasti optimal untuk menghubungkan 2 buah bangunan yang bersebelahan.
Jadi soalnya direduksi menjadi diberikan array A berisi N-1 bilangan, pilihlah K bilangan yang tidak bersebelahan dengan total penjumlahan minimum!

Solusi DP:

DP[I][K] : nilai minimum yang dapat diperoleh dengan menggunakan I bilangan pertama, dan mengambil K bilangan.
DP[I][0] = 0
DP[I][K] = min (DP[I-1][K], DP[I-2][K-1] + A[K])
Jawabannya DP[N-1][K]. Solusi ini kompleksitasnya O(NK).

Observasi:

Misal nilai-nilai pada array diurutkan, pasti ada solusi optimal yang hanya menggunakan 3K elemen terkecil. Jadi sisa elemennya dapat dibuang.

Komplesitasnya menjadi O(K^2)

Cukup untuk menyampah sebuah subtask kalau di IOI :).

Tapi kalau mau AC, dibutuhkan observasi suatu properti.

Misalkan F(X) menyatakan nilai minimum yang diperoleh  dengan mengambil X bilangan, properti dari soal ini adalah F(X+1) - F(X) <= F(X+2) - F(X+1).

Proof (Informal):

Anggaplah solusinya untuk X=K adalah S. Untuk F(K+1) yang optimal, ada 2 kasus:
  1. Mengambil sebuah D yang tidak konflik dengan S: 
  • Jawaban akan bertambah sebanyak D. Nilai D pasti tidak kurang dari bilangan-bilangan di S. Karena apabila tidak, D akan diambil duluan dan S akan lebih optimal.
      2. Menghapus C bilangan di S, lalu mengambil C+1 bilangan: 
  • Misalkan kita menghapus suatu bilangan D dari S, maka kita harus mengambil 2 bilangan di antara D dalam sebagai solusi. anggaplah X artinya ambil, O artinya engga ambil. Kita mencari sebuah segment OOXOXOXOXOXOO dan mengubahnya menjadi OXOXOXOXOXOXO. Pasti semua kombinasi untuk memilih 5 X pada OXOXOXOXOXOXO  lebih besar dari solusi OOXOXOXOXOXOO karena apabila tidak, lebih optimal memilih kombinasi 5 X tersebut.
  • Diantara semua X di OXOXOXOXOXOXO, ambil 5 dengan nilai terkecil sebagai sebuah solusi S, WLOG asumsikan itu OXOXOXOXOXOOO. Dengan menambahkan X keenam, penambahannya akan lebih tinggi dari penambahan-penambahan sebelumnya. Penambahan ini akan lebih besar apabila dibandingkan dengan solusi optimal.
QED

Misalkan Slope_F(X) = F(X+1) - F(X).
Dari properti soal, didapat Slope_F(1) <= Slope_F(2) <= ...<=Slope_F(N-1)
Fungsi yang memenuhi properti ini dikatakan fungsi dengan nondecreasing slope.

Misal ada 2 fungsi nondecreasing slope F dan G, maka fungsi F+G juga nondecreasing slope. (proofnya trivial).

K sudah diberikan soal. Akan dicari Slope_F(K). Binary search bisa digunakan: 
  • Untuk mencari tahu apakah Slope_F(K) >= C, untuk suatu C, dapat dilakukan dengan mencari nilai X terkecil dimana Slope_F(X) = C.
  • Apabila X<=K, Slope_F(K) >= C.
  • Apabila X>K, Slope_F(K) < C.
Misalkan X di titik 0, maka Slope_F(K) >= Slope_F(X)
Misalkan X di titik 3, maka Slope_F(K) < Slope_FX)

Setelah binser, kita dapat Slope_F(K) dan X terkecil dimana Slope_F(X) = Slope_F(K). Maka, F(K) = F(X) + (K - X)*Slope_F(X).

Permasalahannya sekarang, bagaimana caranya mencari X terkecil untuk suatu Slope? 

Math time!
Satu iterasi binser mencari X terkecil yang memenuhi C <= Slope_F(X), Untuk suatu Slope C.
C <= F(X+1) - F(X)
F(X+1) - F(X) - C >= 0
(F(X+1) - C*(X+1)) - (F(X) - CX) >= 0
Buat fungsi G(X) = F(X) - X*C. Fungsi ini bersifat nondecreasing slope.
G(X+1) - G(X) >= 0
Slope_G(X) >= 0

Kalau fungsi G(X) di plot, kurang lebih akan seperti ini:

Titik menyatakan dimana Slope_Gnya berubah.
Slope_G titik-titik di [0,3) negatif
Slope_G titik-titik di [3,6] nonnegatif

Dimanakah letak X terkecil sehingga Slope_G(X) nonnegatif? tidak lain adalah ketika G minimum! atau bisa dikatakan optimal.

Untuk mencari G minimum, tinjau kembali rumusnya: G(X) = F(X) - X*C, dengan X adalah banyaknya elemen yang diambil. Dengan memerhatikan rumusnya, yang dilakukan G sebenarnya adalah memberi penalti C untuk setiap elemen yang di ambil oleh F.

Jadi, bisa digunakan DP[N] : nilai G minimum dengan menggunakan N bilangan pertama.
Transisinya:
DP[1]  = min(0, A[1] - C)
DP[I]   =  min(DP[I-1], DP[I-2] + A[I] - C)
Perbedaan DP ini dengan DP naive adalah DP ini membuang dimensi K sehingga perhitungan dilakukan dalam O(N). Setelah mendapatkan G minimum, nilai X dapat dicari dengan backtracking berapa bilangan minimum yang diambil untuk mencapai nilai G tersebut.

Dalam binser, simpan nilai G dan Slopenya. Selesai binser, F(K) = G + slope*K.

Kode: https://ideone.com/24fLTJ

Kompleksitas: binary search O(log N), ditambah DP O(N), kompleksitas totalnya O(N log N).

Monge Property?

Di China, teknik ini udah lumrah dari lama banget. Namun, baru ngehits setelah muncul di IOI 2016, Aliens. Teknik ini diajarkan ketika aku pelatnas 3 dan semuanya stress xD. Ternyata setelah aku telusuri lebih dalam, ini algo yang cukup simple, yang susah itu ngeproof slopenya -_-"

Aku gasuka nama "Aliens Trick" karena sebelum itu tekniknya dah ada. Aku dan Yehez berhasil menemukan nama aslinya, yaitu "Monge Property" (Paper). Karena ini pakai binary search, nama lebih cocok adalah "Monge Property Binary Search" :)

Variasi

Ini juga bisa dilakukan apabila slopenya nonincreasing. Hanya perlu modif sedikit. Berikut pseudocode umumnya: https://ideone.com/2PvPYW

Monge Property ini dapat juga dipakai untuk optimisisasi algo-algo lain seperti DP Convex Hull (IOI 2016 Aliens), atau Kruskal Algorithm (link soal). Yah intinya Monge Property lumayan flexibel lah :)

Monge Properti juga dapat digunakan untuk menendang lebih dari 1 dimensi. Aku sih menyebutnya double monge wkwkwkwk. Aku pernah menggunakannya di soal COCI Akvizna, sayangnya telat submit (AC sih). Aku gasadar kalau hanya butuh 1x monge, Untuk penjelasan tentang double monge bisa cek postingan ini.

Membuktikan Properti Slope

Membuktikan properti slope, Slope_F(X) <= Slope_F(X+1), atau Slope_F(X) >= Slope_F(X+1) ini cukup menantang! apalagi di kontes kan kita juga tidak tahu apakah benar solusinya memang memakai teknik ini.

Selain menggunakan direct proof seperti di soal BACKUP tadi, bisa juga dengan metode bruteforce. cetak saja Slope_F(1), Slope_F(2), dst. Jadi, kalau misal ngestuck, coba cek ada properti slopenya enggak :"v.

Setelah aku solving puluhan soal dengan teknik ini, aku ada semacam "insting" untuk mengetahui soal yang kira-kira bisa pakai teknik ini. contohnya soal Akvizna COCI, aku langsung tahu bisa pakai teknik ini :)

Maaf jawabannya kurang memuaskan untuk bagian ini :/ setiap soal membutuhkan proof yang berbeda memang.

Latihan Soal:

https://www.spoj.com/problems/BACKUP/
IOI 2016 Aliens
https://open.kattis.com/problems/blazingnewtrails
http://hsin.hr/coci/contest4_tasks.pdf (Problem E)
https://training.ia-toki.org/problemsets/126/problems/703/ (Bisa juga pake DP DNC)
https://codeforces.com/blog/entry/49691 (disini banyak :v)

Comments

Popular posts from this blog

Intern Semester 2: Data Science Intern di OVO

Fuih, ini pengalaman internshipku sekitar setahun yang lalu. Karena segala kesibukan akademis dan organisasi, aku baru sempat kelarin sekarang. So sorry! X(. Hmm sebenernya engga sibuk-sibuk amat sih... mungkin aku kebanyakan procrass? anw, ya kali ini aku bakal nyeritain pengalamanku intern di data science di OVO setahun yang lalu, yaitu dari juni - agustus 2019. Oiya, Sebenernya postnya udah 90% kelar di akhir agustus lalu, tinggal penutupnya doang tapi entah kenapa aku lupa total ngerjain post-postku. Awalnya rencananya mau detail banget deskripsiin tiap minggu kek blog intern GDP Labsku, tapi setelah aku baca-baca lagi kok ngebosenin ya? jadinya aku refactor besar-besaran dan jadilah blog post ini. Selamat menikmati ya :D Liburan Semester 2 Aku cukup senang karena durasi libur di Fasilkom 3.5 bulan. Ini memberi banyak waktu untuk beristirahat dari semua kesibukan-kesibukan selama kuliah. Tapi, apakah memang benar kita butuh 3.5 bulan untuk kembali segar? aku tidak! Aku c

Mengikuti ICPC 2019 Bagian 1: Jakarta Regional

Halo, sudah lama tidak berjumpa! Semester ini aku terlalu banyak kegiatan jadi lupa ada blog ini. Jadi, liburan semester ini bakal ada banyak blog-blog yang bakal keluar ^_^. Kali ini, aku bakal nyeritain pengalamanku mengikuti ICPC lagi tahun ini. ICPC,  The International Collegiate Programming Contest  adalah lomba programming yang setiap tahun diadakan. Tentunya aku ikut lagi dong. Apalagi, sudah dibekali ilmu dari matkul TKTPL saat semester 2. Peminat CP di UI lumayan banyak, jadi diadakan seleksi untuk masuk tim intinya. Aku lolos :D. Pembentukan Tim Aku gak perlu mikirin mau ngetim siapa, karena komposisinya sudah ditentukan oleh Pak Denny. Aku dapat tim bareng Kak Norman dan Budi. Aku lumayan seneng dengan timku. Tahun lalu, aku ngetim Kak Norman juga jadi sudah tahu kemampuan masing-masing. Budi, aku sudah sering ketemu saat ngajar di pelatnas 2 dan pelatnas 3 dan skillnya jago, Aku mikirnya dia bakal ngecarry kita, hehe. Oh, kita kebagian regional Kuala Lumpur. Jad

Pengalamanku Ikut PCS UGM 2017

Jadi aku baru saja ngikutin lomba Programming UGM (PCS). Lombanya harusnya bertiga, namun aku ikutnya sendiri. Lolos xD. Nama “timku” untuk lomba ini adalah “Ngeramaikan Saja” karena aku ngerasa cuma bakal ngeramein doang. Hari 1 (kesialan) Aku bangun jam 7 pagi lalu langsung ke bandara dan naik pesawat. Sampai di Jogja baru dapat sms dari Kak Krisna (yang jemput aku) karena aku pake airplane mode jadinya baru bisa bales, dia jadinya baru otw. Aku nunggu sekitar 20 menit sebelum di telpon, aku bilang nunggu di terminal B deket KFC.  “lho di terminal B kan gaada KFC?” “ada kok, yang di depan itu” Aku diminta ke kedatangan, tetap saja gak ketemu ketemu dia ._., Kak Krisna fotoin tempatnya dan aku kebingungan karena beda banget sama posisiku. Ternyata aku ada di terminal A! Kak Krisna pun ngakak di telpon. Berangkat deh ke hotel. aku sampai hotel jam 12 lebih sedikit dan check-in baru bisa jam 2. Tapi karena kamarnya udah siap, aku dikasih langsung masuk kamar. Aku buka l