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…

Fasilkom Semester 3 Bagian 1: Kerja dan Kelompok

Yess! jurnal semesteran is back. Ini tahun yang super sibuk bagiku. Jadi, aku bakal bagi jurnalnya jadi 2 bagian: akademis dan nonakademis. Alasannya biar ga panjang-panjang dan bisa fokus aja sih. Ya, selamat menikmati.

SIAK WAR & Nasib Matkul SIAK WAR, waktu memilih matkul bagi anak UI.

Bukan galang namanya kalau ga kalah siak war. Waktu war, aku masing magang di OVO. Aku udah double-triple check kalau wifi OVO yang kenceng bisa buka SIAK. Aku sudah rela datang ke kantor sebelum waktu mulai kerja demi war. Tapi, kok siaknya gamau kebuka ya? aku kiranya down. Taunya, temen-temenku bisa. REEEE.

Aku struggle terus selama beberapa menit. Gak bisa-bisa! Oh noo. I saw my life flash before my eyes. Akhirnya, aku kepikiran ganti ke tethering HP dan siak lancar jaya. Tapi apa boleh buat, perang sudah selesai dan aku tidak mendapatkan 5 dari 7 matkul yang aku inginkan.


Kalah war efeknya jangka panjang. Seminggu aku habiskan membuka website siak & scele untuk mengecek penambahan kapas…

Jurnal Semester 2 Fasilkom: Aksiologi Nguli?

Yes! sudah 1 tahun aku di fasilkom! Berhubung maba, disamping mengambil 23 sks, aku juga mengambil 5 organisasi/kepanitiaan; mencari sOft SKilL kata mereka. Aku pikir ada cukup banyak bahan untuk ngeblog. Rencana awalnya, mau kubagi dua part. Tapi, organisasiku beberapa masih jalan jadi nanti yang dua part semester tiga aja. Ya, dikesempatan ini aku cuma bakal rekap matkul-matkulku semester ini.

Seperti biasa, coba tebak urutan dari kemunculan matkul-matkul ini! jawaban di akhir blog.

Dasar - Dasar Pemrograman 2 (DDP2)
Kalau DDP1 kemarin tujuannya agar biasa dengan bahasa pemrograman, DDP2 ini diajarkan teori pemrograman lebih definitif menggunakan bahasa yang berbeda, Java.

Ujung-ujungnya gabanyak beda sama DDP1 si. Belajarnya macam rekursi, OOP, GUI (javafx) gitu-gitu. Pak Stef kerennya ingat nama semua murid-muridnya jadi kalau ada yang nanya, bapaknya mempersilahkan dengan nyebut namanya.

Ada kegiatan lab setiap hari senin sore. Labnya dimulai jam 4, tapi jam 3 soalnya sudah dibuk…