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…

Pembahasan OSN 2016 Day 1 + Day 2

OSN tinggal lagi sebulan. Aku sadar bahwa ada pembahasan resmi OSN 2015 dan 2017, tapi gaada yang 2016 :(. Terutama ada soal super asik "wisata palembang" yang dimana orang yang AC setelah dua tahun ini baru dua orang (sekarang 3, karena ada aku :v). Jadi aku buat pembahasan OSN 2016. Mungkin soalnya udah basi(:v) tapi mudah-mudahan masih dapat dijadikan pembelajaran.

Catatan:
Aku engga ngeshare source codeku, karena implementasi itu bagian serunya. Tapi bakal ada beberapa pseudocode, aku tulis menggunakan bahasa pseudopascal :v.

Day 1

Pasar 16 Ilir

Subtask 1-6,8  (67 poin)

Perhatikan bahwa N*M paling banyak 20, cukup kecil jadi kita bisa buat semua kemungkinan jalannya. Kita asumsikan kasus terburuk, yaitu N*M=20. ini akan maksimum ketika R=4 dan C=5 (atau sebaliknya). Jadi banyaknya kemungkinan jalan cukup sedikit. Kita bisa simpan semua kemungkinan jawabannya dalam array, dan apabila ditanya harga antar P dan Q tinggal iterasi saja isi arraynya.

Nah, sekarang tinggal gimana …

Jurnal Pelatnas 2 TOKI 2018, Minggu 3: Gochisōsama (+MIT Application)

Catatan: dikarenakan betapa gregetnya minggu terakhir ini, aku sama sekali gak sempet nulis harian seperti pada jurnal-jurnal sebelumnya. Berdasarkan nilai kuis minggu ini dan nilai-nilaiku minggu lalu, performaku divonis menurun oleh Pak Rully. Maka, minggu terakhir ini aku memutuskan untuk fokus total pada pelatnas dan ga ngeblog harian seperti biasanya. Aku baru bisa mulai menulis sepulangnya aku dari pelatnas 2. Jadi gaya penulisan pada tulisan ini bakal sedikit berbeda. Artinya gaada ROTD :(

Pelatnas 2 sudah memasuki minggu terakhir, dan seperti yang ditulis pada catatan diatas, minggu ini bisa jadi merupakan minggu yang paling menantang dalam karir komputerku.

Rabu, 7 Maret 2018

Ah, hari rabu, hari maut…

Seperti yang sudah diketahui, Setiap hari Rabu bakal diadakan kuis, semacam tes penilaian yang bobotnya sangat besar dalam menentukan siapakah yang bakal lolos ke pelatnas 3 nantinya. Setiap pagi selalu diawali dengan hal yang sama yakni dibangunin Kak Dimas (Sepertinya bebera…