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)

Refrensi:

https://codeforces.com/blog/entry/49691

https://www.cse.ust.hk/~golin/Talks/Revisiting_Monge.pdf

https://ioinformatics.org/page/ioi-2016/42 (Analisis IOI Aliens)