Sunday, 10 February 2013

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\\ \min_{pre[i] \le x \le i} \left( \left( \max_{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)

Walaupun dengan kompleksitas \(O(N\log{N})\), runtime algoritma ini di UVa mencapai 2 detik. Menurut rumor, terdapat algoritma \(O(N)\) untuk soal ini. Bagi anda yang mengetahuinya, jika anda berkenan anda dapat memberitahu solusi tersebut di komentar.

Berikut kode saya:
syntax highlighting tutorial

No comments :

Post a Comment