Soal yang menarik untuk dibahas kali ini berasal dari UVa 11491 - Erasing and Winning.
Persoalannya sederhana, kita diberikan sebuah bilangan yang besarnya n dan n ~ 100000. Jika kita harus menghapus d dijit, maka berapa bilangan terbesar yang dapat kita hasilkan?
Karena banyaknya dijit cukup besar, jelas bahwa brute force \(O(2^n)\) tidak akan bekerja.
Observasi 1:
Solusi optimal ketika d dijit dihapus sama saja dengan: bilangan terbesar yang dapat dihasilkan bila kita menghapus 1 dijit dari solusi optimal saat (d-1) dijit dihapus. Oleh karena itu, kita dapat menghapus 1 per 1 dan di setiap langkahnya harus optimal. Observasi ini memunculkan aroma greedy pada persoalan ini.
Observasi 2:
Misalkan bilangan itu adalah a0,a1,a2, ..., an-1. Penghapusan sebuah dijit yang optimal adalah menghapus ai, jika ai < ai+1 dan i adalah seminimal mungkin. Bila tidak ada i yang memenuhi, hapus dijit paling belakang. Kebenaran pernyataan ini cukup intuitif.
Berdasarkan kedua observasi itu, kita dapat merancang algoritma greedy: hapus 1 per 1 dijit dengan cara sesuai dengan observasi 2, sampai d dijit terhapus.
Permasalahan sisanya tinggal bagaimana implementasi yang efisien. Pada prakteknya anda dapat menggunakan struktur data linked-list dan/atau set untuk mencapai algoritma O(N log N). Berikut ini adalah implementasi dengan set:
Persoalannya sederhana, kita diberikan sebuah bilangan yang besarnya n dan n ~ 100000. Jika kita harus menghapus d dijit, maka berapa bilangan terbesar yang dapat kita hasilkan?
Karena banyaknya dijit cukup besar, jelas bahwa brute force \(O(2^n)\) tidak akan bekerja.
Observasi 1:
Solusi optimal ketika d dijit dihapus sama saja dengan: bilangan terbesar yang dapat dihasilkan bila kita menghapus 1 dijit dari solusi optimal saat (d-1) dijit dihapus. Oleh karena itu, kita dapat menghapus 1 per 1 dan di setiap langkahnya harus optimal. Observasi ini memunculkan aroma greedy pada persoalan ini.
Observasi 2:
Misalkan bilangan itu adalah a0,a1,a2, ..., an-1. Penghapusan sebuah dijit yang optimal adalah menghapus ai, jika ai < ai+1 dan i adalah seminimal mungkin. Bila tidak ada i yang memenuhi, hapus dijit paling belakang. Kebenaran pernyataan ini cukup intuitif.
Berdasarkan kedua observasi itu, kita dapat merancang algoritma greedy: hapus 1 per 1 dijit dengan cara sesuai dengan observasi 2, sampai d dijit terhapus.
Permasalahan sisanya tinggal bagaimana implementasi yang efisien. Pada prakteknya anda dapat menggunakan struktur data linked-list dan/atau set untuk mencapai algoritma O(N log N). Berikut ini adalah implementasi dengan set:
Tidak ada komentar :
Posting Komentar