Kupas Kode: UVa 12440 - Save the Trees

Soal menarik yang akan dibahas kali ini adalah UVa 12440 - Save the Trees. Sedikit sekali diskusi yang ada di internet tentang soal ini, sehingga saya memutuskan untuk menulis pembahasannya.

Persoalannya adalah, diberikan sebuah barisan pohon (bisa sampai 100000) dengan ketinggian dan jenis tertentu. Tugas kita adalah mengelompokkan pohon-pohon konsekutif ke dalam beberapa grup, dimana banyakya grup tidak dibatasi dan di dalam grup tidak boleh ada pohon berjenis sama. Biaya untuk mengelompokkan sebuah grup sama dengan tinggi maksimum dari pohon di grup tersebut. Berapa biaya total minimal yang mungkin untuk mengelompokkan semua pohon tersebut?

Misalnya tinggi pohon ke-i dinyatakan dengan h[i], dan jenis pohon ke-i adalah c[i].
Observasi 1:
Untuk setiap pohon ke-i, ada pohon x dimana x adalah minimal dan x ≤ i, sedemikian sehingga c[j] untuk x ≤ j ≤ i unik. Kita sebut x ini sebagai pre[i].

Observasi 2:
Biaya mengelompokkan pohon dari 1 sampai i sama dengan biaya mengelompokkan pohon dari 1 sampai x-1 ditambah max(h[i],h[i-1],...,h[x]) dengan pre[i] ≤ x ≤ i. Di antara semua kemungkinan x, pilih yang biayanya minimal. Karena muncul sub-masalah, kita dapat menggunakan dynamic programming (DP). Formulasi DP-nya:

$\displaystyle f(i) = \left\{ \begin{array}{ll} 0&, i < 1\\ \displaystyle \min_{\displaystyle pre[i] \le x \le i} \left( \left( \max_{\displaystyle x \le j \le i} h[j] \right) + f(x-1) \right) &, i \ge 1 \end{array} \right.$

Jawabannya ada di f(N).

Dengan formulasi DP tersebut, untuk kasus terburuk kompleksitasnya adalah

$O(N^2)$ (ketika semua pohon berbeda jenis). Karena pasti TLE, kita butuh observasi yang lebih lanjut. Misalkan kita sudah mengetahui nilai-nilai f(0), f(1), f(2), ..., f(i-1) dan hendak mencari nilai f(i). Selain itu, kita sudah mengetahui nilai g(1,i-1), g(2,i-1), ..., g(i-1,i-1) dimana g(x,i) menyatakan ketinggian maksimum dari pohon-pohon dari x sampai i.

Observasi 3:
Misalkan cost[x] menyatakan nilai f(i) jika diputuskan untuk mengelompokkan pohon-pohon dari x hingga i, maka untuk setiap x, cost[x] = g(x,i) + f(x-1). Selanjutnya kita tinggal mencari nilai minimum dari cost[x] dengan pre[i] ≤ x ≤ i sebagai nilai dari f(i).

Observasi 4:
Jika kita sudah mengetahui nilai g(1,i-1), g(2,i-1), ..., g(i-1,i-1), nilai g(1,i), g(2, i), ..., g(i,i) dapat diketahui dengan bantuan struktur data stack. Teknik ini mirip dengan teknik yang digunakan di pembahasan soal Span. Kita akan membutuhkan update untuk suatu interval cost[x] karena adanya perubahan nilai fungsi g, yaitu saat i bertambah 1. Observasi ini merupakan bagian paling penting untuk mengoptimisasi algoritma kita.

Observasi 5:
Update untuk suatu interval dan melakukan ekstraksi nilai minimum dari suatu interval dapat dilakukan dengan bantuan struktur data segment tree, untuk mencapai kompleksitas

$O(\log{N})$ per operasi. Lebih jelasnya, kita butuh segment tree dengan kemampuan:

Tambah nilai dari indeks ke-a hingga indeks ke-b dengan c (bisa saja c negatif)
Cari nilai terkecil dari indeks ke-a hingga indeks ke-b

Dengan DP bottom-up dan bantuan segment tree itu, kita bisa capai kompleksitas

$O(N\log{N})$ . Karena setiap elemen hanya masuk ke dalam stack maksimal sekali, lalu keluar maksimal sekali. Setiap masuk atau keluar, dilakukan update terhadap array cost.
Untuk lebih jelasnya, perhatikan contoh kasus berikut:

Untuk mencari nilai f(9), terlebih dahulu kita mencari nilai-nilai g(i,9) dari g(i,8). Kita lakukan operasi:

Tambah nilai cost dari indeks ke-7 hingga indeks ke-8 dengan -3
Tambah nilai cost dari indeks ke-4 hingga indeks ke-6 dengan -4
Tambah nilai cost dari indeks ke-4 hingga indeks ke-9 dengan 5
Nilai f(9) adalah nilai terkecil dari cost indeks ke-6 sampai ke-9 (perhatikan bahwa pre[9] = 6), yaitu 14
Tambah nilai cost dari indeks ke-9 hingga indeks ke-9 dengan 14, sebagai bekal untuk mencari nilai f(10) (jika ada)

Berikut kode saya:

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <utility>
#include <vector>
#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 MP make_pair
#define F first
#define S second
#define PII pair<int,int>
 
#define MAXN 131072
using namespace std;
 
int INF = 2123123123;
 
struct node{
   int val,prop;
};
 
int nkasus;
int n,h[MAXN],col[MAXN];
int dp[MAXN];
int pre[MAXN];
int stek[MAXN],p;
node stri[2*MAXN];
set<int> him;
 
void isiPre(){
   him.clear();
    
   int di = 1;
   FOR(i,1,n){
      while (him.count(col[i])){
         him.erase(col[di++]);
      }
      him.insert(col[i]);
       
      pre[i] = di;
   }
}
 
void build(int nod, int ki, int ka){
   stri[nod].val = 0;
   stri[nod].prop = 0;
    
   if (ki < ka){
      int tgh = (ki + ka) >> 1;
       
      build(2*nod+1, ki, tgh);
      build(2*nod+2, tgh+1, ka);
   }
}
 
void push(int x){
   stri[2*x+1].prop += stri[x].prop;
   stri[2*x+2].prop += stri[x].prop;
   stri[x].prop = 0;
}
 
int GET(int x){
   return stri[x].val + stri[x].prop;
}   
 
void update(int nod, int ki, int ka, int a, int b, int val){
   if ((a <= ki) && (ka <= b)){
      stri[nod].prop += val;
   }else{
      int tgh = (ki + ka) >> 1;
       
      push(nod);
       
      if (a <= tgh) update(2*nod+1, ki, tgh, a, b, val);
      if (b >  tgh) update(2*nod+2, tgh+1, ka, a, b, val);
       
      stri[nod].val = min(GET(2*nod+1), GET(2*nod+2));
   }
}
 
int query(int nod, int ki, int ka, int a, int b){
   if ((a <= ki) && (ka <= b)){
      return GET(nod);
   }else{
      int tgh = (ki + ka) >> 1;
      int ret = INF;
       
      push(nod);
       
      if (a <= tgh) ret = min(ret, query(2*nod+1, ki, tgh, a, b));
      if (b >  tgh) ret = min(ret, query(2*nod+2, tgh+1, ka, a, b));
       
      stri[nod].val = min(GET(2*nod+1), GET(2*nod+2));
       
      return ret;
   }
}
 
int main(){
   scanf("%d", &nkasus);
   REP(jt,nkasus){
      scanf("%d", &n);
      FOR(i,1,n){
         scanf("%d %d", &col[i], &h[i]);
      } 
      h[0] = MAXN;
       
      isiPre();
       
      stek[0] = 0;
      p = 1;
       
      build(0,1,n);
       
      FOR(i,1,n){
         while (h[stek[p-1]] <= h[i]){
            update(0, 1, n, stek[p-2]+1, stek[p-1], -h[stek[p-1]]);
            p--;
         }
         stek[p++] = i;
         update(0, 1, n, stek[p-2]+1, stek[p-1], h[i]);
    
         dp[i] = query(0, 1, n, pre[i], i);
         update(0, 1, n, i+1, i+1, dp[i]);
      }
       
      printf("Case %d: %d\n", jt+1, dp[n]);
   }
    
   return 0;
}

Pages

Minggu, 10 Februari 2013

UVa 12440 - Save the Trees

Tidak ada komentar :

Posting Komentar

Pages

Minggu, 10 Februari 2013

UVa 12440 - Save the Trees

Tulisan terkait:

Tidak ada komentar :

Posting Komentar