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 1: AI Engineer di GDP Labs

Intern atau magang, suatu kegiatan untuk merasakan suasana kantor. Daripada tidur-tiduran ngewibu gajelas selama sebulan, lebih baik ngoding 8 jam sehari di kantor kan?
Pertama tahu GDP Labs dari lomba BNPCHS 2017. Waktu penutupan, Pak On Lee, CEO GDP Labs, bawa seminar. Terus kan di akhir acara aku kenalan dan dikasih kartu nama :D
Aku awalnya berminat mau magang semester 2, namun temenku Rania semester 0 udah magang di GDP Labs. Aku jadinya daftar magang winter sebagai AI Engineer dan keterima :) Aku ditaro di bagian GLAIR (GDP Labs Artificial Intelligence Research).
Bagian-bagian dari blog ini: - Tentang GDP Labs - Kosa Kata Machine Learning - Onboarding (19 Desember 2018) - Minggu Pertama (26 - 28 Desember 2018) - Minggu Kedua (2 - 4 Januari 2018) - Minggu Ketiga (7 - 11 Januari 2018) - Minggu Keempat (14 - 18 Januari 2018) - Minggu Kelima (21 - 25 Januari 2018) - Minggu Keenam (28 - 31 Januari 2018)
- Penutup
Iklan Sejenak Tentang GDP Labs
GDP Labs itu bagian dari GDP Venture. GDP…

Mengikuti ICPC 2018

ah, ICPC. Singkatan dari International Collegiate Programming Contest. Perlombaan paling bergengsi untuk anak kuliahan. UI sendiri cukup aktif mengikuti perlombaan ini. Aku sebagai Maba dapat kesempatan untuk mengikuti lomba ini dan dapat keluar negeri juga. hehe. Berikut cerita ICPCku tahun ini. Selamat menikmati.

Pembentukan Tim


Di UI ada seleksi untuk pembentukan tim ICPC yang nantinya akan mewakili UI ke regional yang ke luar negeri. Seleksi ini dibuka untuk seluruh UI, kating-kating sampai maba boleh daftar, bahkan untuk non fasilkom pun boleh (Pak Denny bilang pernah ada anak FMIPA lolos :O).

Seleksi ini cukup singkat. Ada 3 kontes. 2 kontes pendek dan 1 kontes panjang.

Kontes pendek itu durasinya 2.5 jam dan ngerjain di lab. Dapet poin berdasarkan ranknya yaitu max(18-rank,2). Kontesnya di Vjudge.

Kontes panjang itu durasinya 1 minggu dan dapet poin cuma berdasarkan jumlah solve. kontesnya dari selasa - selasa depannya.

Ini aku ada kendala di laptop. Jadi laptopku saat itu (ROG…

Jurnal Fasilkom Semester 1: Mengamati Budaya Trap

Bentar-bentar,
"Kok ada lagi? bukannya udah?" 
Postingan tersebut adalah karena terlalu banyak konten bagi maba :(. Ini postingan rutinnya. Oiya, karena suatu kesalahan, 2 section terakhir di postingan itu hilang :/ jadi aku terpaksa kelarin ini.
Kali ini cuma bahas 3 Section doang: - Budaya Trap Fasilkom - Akhir PMB - Perkuliahan Fasilkom Budaya Trap Fasilkom
Ah, trap. Awal masuk, pengertianku tentang trap itu adalah seseorang yang suka bilang ga belajar, taunya belajar. Namun aku makin bingung gitu lama-lama. Orang belajar di perpus -> trap, orang nanya dosen -> trap, ga deadliner -> trap.

Yang aku pahami tentang sistem trap ini:



Kata trap dipake dengan semakin liar seiring berjalannya waktu, ngerasa kaya asal pake aja. Aku cukup risih sih kalau dibilang trap. Kalau nanya, paling-paling jawabanya OSN 2017 atau Compfest 9 tahun lalu (Aku ada alasannya loh :v). Aku ga terlalu suka budaya tuduh trap ini, apakah bisa di hentikan?
Akhir PMB
PMB (Pembinaan Mahasiswa Baru…