UVa 11491 - Erasing and Winning

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 a₀,a₁,a₂, ..., a_n-1. Penghapusan sebuah dijit yang optimal adalah menghapus a_i, jika a_i < a_i+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:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> #include <utility> #include <vector> #include <queue> #include <map> #include <set>   #define REP(a,b) for (int a = 0; a < b; a++) #define FOR(a,b,c) for (int a = b; a <= c; a++) #define RESET(a,b) memset(a,b,sizeof a)   #define LL long long #define INF 2123123123 #define PB push_back #define PII pair<int,int> #define MP make_pair #define F first #define S second   using namespace std;   int n,d; char sc[100002]; set<pii> him; set<int> bil;   int main(){    scanf("%d%d", &n, &d);    while (n|d){       scanf("%s", sc);               him.clear();       bil.clear();               sc[n++] = 'a';       REP(i,n){          him.insert(MP(i, sc[i] - '0'));          if ((i < n-1) && (sc[i] < sc[i+1])){             bil.insert(i);          }       }               REP(i,d){          //buang2in          int di = *bil.begin();                     //cek nyatu?          set<PII>::iterator it = him.find(MP(di, sc[di] - '0'));          if (it != him.begin()){             it--;               set<pii>::iterator naw = it;                           him.erase(MP(di, sc[di] - '0'));             it++;             set<pii>::iterator nex = it;                           if ((naw->S) < (nex->S)){                bil.insert(naw->F);               }          }else{             him.erase(MP(di, sc[di] - '0'));          }          bil.erase(di);       }                 set<pii>::iterator it = him.begin();       REP(i,him.size()-1){          printf("%d", it->S);            it++;       }       printf("\n");               scanf("%d%d", &n, &d);         }      return 0;   }