ACM ICPC Regional Harbin 2010 - Cross the Wall

Sebuah perkenalan kepada DP Convex Hull... 

Satu lagi soal dari ICPC Regional Harbin 2010 yang sedikit sekali diskusinya, yaitu Cross the Wall. Soal ini sangat menarik karena memerlukan observasi yang mendalam.

Inti dari persoalannya sederhana:

• Diberikan N persegi panjang dengan berbagai ukuran panjang dan lebar.
• Anda boleh membuat maksimal K buah lubang persegi panjang pada sebuah bidang (tembok) sedemikian sehingga setiap persegi panjang dapat melewati bidang tembok tanpa dirotasi.
• Lubang yang dibuat tidak boleh bersentuhan dengan lubang lainnya yang sudah pernah dibuat.
• Persegi panjang yang panjang dan lebarnya lebih kecil atau sama dengan panjang dan lebar lubang bisa melewati lubang tersebut.
• Biaya membuat sebuah lubang persegi panjang dengan panjang P dan lebar L adalah P &times L.
• Seluruh persegi panjang yang dibicarakan di sini memiliki sisi yang paralel dengan sumbu x atau y.
• Tentukan total biaya minimum untuk membuat setiap persegi panjang dapat melewati bidang tembok!

Batasan pentingnya:

• 1 ≤ N ≤ 50.000
• 1 ≤ K ≤ 100
• Panjang dan lebar setiap persegi panjang adalah bilangan bulat positif tidak lebih dari 1.000.000

Langsung saja ke pembahasannya:
Observasi 1:
Terdapat beberapa persegi panjang yang bisa "numpang lewat" pada lubang untuk persegi panjang lain yang lebih besar. Kejadian ini muncul ketika ada suatu persegi panjang A dengan panjang p dan lebar l, dan ada persegi panjang lain (sebut saja B) yang memiliki panjang P dan lebar L, dengan p ≤ P dan l ≤ L. Dalam tulisan ini, persegi panjang A dikatakan terdominasi oleh persegi panjang B.

Berdasarkan observasi 1, kita bisa membuat struktur dominasi-terdominasi dari seluruh persegi panjang. Struktur ini membentuk DAG (Directed Acyclic Graph). Jelas bahwa lubang yang perlu kita buat cukup memperhatikan persegi panjang yang tidak terdominasi oleh persegi panjang lainnya. Hal ini disebabkan karena persegi panjang lainnya yang terdominasi dijamin dapat melewati salah satu dari lubang yang nantinya akan dibuat.

Untuk selanjutnya, persegi panjang yang tidak terdominasi oleh siapapun akan disebut dengan "persegi panjang penting".

Bagaimana cara mengetahui persegi panjang yang mana yang merupakan persegi panjang penting? Persoalan ini sebenarnya cukup klasik dan dapat diselesaikan dengan bantuan struktur data Binary Indexed Tree. Oleh karena itu saya akan langsung menjelaskan caranya:

1. Mulailah dengan BIT yang kosong (nilainya 0 semua).
2. Urutkan pasangan (panjang, lebar) dari setiap persegi panjang menurut panjangnya (yang lebih besar lebih awal). Jika ada yang sama, urutkan menurut lebarnya (yang lebih besar lebih awal).
3. Mulailah dengan i = 1
4. Lakukan query pada BIT, cek apakah jumlahan dari elemen ke-(lebar persegi panjang ke-i) sampai elemen ke-1.000.000 sama dengan 0. Bila ya, artinya persegi panjang ke-i penting. Bila tidak, artinya persegi panjang ke-i tidak penting.
5. Tambahkan elemen ke-(lebar persegi panjang ke-i) dengan 1 (pada BIT).
6. Bila i < N, lanjutkan ke langkah 4 dengan i := i + 1. Jika i ≥ N, maka selesai.

Yang sebenarnya dilakukan algoritma itu adalah mencari apakah ada elemen lain yang lebarnya lebih dari atau sama dengan lebar persegi panjang saat ini. Bagaimana dengan panjangnya? Berhubung suatu elemen dalam BIT tersebut hanya bernilai 1 bila sudah diproses, dan pemrosesan dilakukan mulai dari persegi panjang yang panjangnya paling besar, maka dijamin bahwa panjangnya selalu lebih besar atau sama dengan panjang persegi saat ini.

Kompleksitas keseluruhan untuk proses tersebut adalah O(N log M), dengan M adalah 1.000.000.

Observasi 2:
Misalkan terdapat Q buah persegi panjang penting, dengan panjang dan lebar p₁l₁, p₂l₂, p₃l₃, ..., p_Ql_Q. Jika dipenuhi p₁ ≤ p₂ ≤ p₃ ≤ ... ≤ p_Q, maka dijamin akan dipenuhi juga l₁ ≥ l₂ ≥ l₃ ≥ ... ≥ l_Q. Hal ini akan selalu dipenuhi; karena jika tidak, artinya masih ada persegi panjang yang bisa terdominasi.

Observasi 3:
Jika ada Q buah persegi panjang penting, maka tugas kita selanjutnya tinggal mengelompokkannya ke dalam maksimal K buah kelompok. Mengelompokkan sejumlah persegi panjang sama artinya dengan membuat sebuah lubang terkecil yang dapat dilalui setiap persegi panjang dalam kelompok tersebut.

Observasi 4:
Jika dipenuhi p₁ ≤ p₂ ≤ p₃ ≤ ... ≤ p_Q, maka setiap kelompok pasti memiliki sejumlah persegi panjang yang konsekutif. Dengan kata lain, suatu kelompok pasti berisikan persegi panjang penting ke-i, i+1, i+2, ..., j, dengan i ≤ j. Lubang yang nantinya dibuat akan memiliki panjang p_j dan lebar l_i.

Berdasarkan observasi 2, 3, dan 4, maka persoalan ini bisa diselesaikan dengan DP. Definisikan f(d, i) sebagai biaya minimal pembuatan d buah lubang supaya persegi panjang penting 1, 2, 3, ..., i bisa dimuat dalam d lubang tersebut. Hubungan rekursifnya:
\[\displaystyle
f(d,i) = \left\{
\begin{array}{ll}
\infty & ,i \ge 0 \wedge d = 0\\
0 &,i=0 \wedge d \ge 0\\
\displaystyle \min_{\displaystyle 1 \le k \le i} \left( p_i l_{k} + f(d-1, k-1) \right) & ,i \gt 0
\end{array} \right.
\]

Karena Q maksimal senilai dengan N, jelas bahwa kompleksitas DP tersebut O(N²K) dan tidak akan AC. Apakah bisa dilakukan optimasi?

Bila diperhatikan lebih lanjut, sebenarnya rekurens DP itu memiliki karakteristik khusus:

• Untuk mencari nilai f(d,i), perlu mencari nilai k sedemikian sehingga p_il_k + f(d-1,k-1) minimal. Nilai p_i selalu konstan, sehingga yang perlu diperhatikan tinggal l_k dengan f(d-1,k-1). Lebih jauh lagi, setiap nilai k yang mungkin berkorespondensi dengan l_k dan f(d-1,k-1).

Melihat karakteristik tersebut dan perumusan yang ada, sebenarnya bentuk p_il_k + f(d-1,k-1) bisa dimodelkan menjadi persamaan garis dengan gradien l_k dan konstanta f(d-1,k-1). Perhatikan gambar berikut:

Persaman garis untuk k=1..4

Sekarang kita memiliki banyak persamaan garis. Masing-masing persamaan garis menyatakan nilai f(d,i) yang mungkin pada nilai x = p_i. Nilai terkecil untuk f(d,i) tentunya dicapai dengan cara memilih titik terendah pada saat x = p_i. Jadi secara sederhana kita tinggal menarik garis x = p_i, lalu lihat koordinat y terkecil yang berpotongan dengan salah satu garis yang ada.

Misalkan kita telah mendapatkan jawaban untuk f(d,i). Bagaimana mencari nilai f(d,i+1)? Ternyata caranya sederhana! Perhatikan bahwa tidak ada perubahan pada persamaan-persamaan garis yang sudah ada sebelumnya (karena nilai l_k dan f(d-1,k-1) tidak berubah), dan muncul sebuah persamaan garis baru dengan gradien l_i dan konstanta f(d-1,i-1).

Lalu apa istimewanya? Kadang-kadang penting untuk mengubah sudut pandang persoalan karena bisa jadi muncul ide-ide yang berguna. Sekarang algoritma untuk soal ini adalah dengan DP bottom up dengan alur:

for d = 0..K
  bidang <- kosong
  for i = 0..N
    f(d,i) <- ekstraksiMinimum(bidang, p_i)
    tambahkan persamaan garis ke-i ke bidang dengan gradien = l_i, konstanta = f(d-1,i-1)

Bila ekstraksiMinimum dilakukan dengan loop O(N), maka kompleksitasnya tetap O(N²K). Akan tetapi, bisa dilakukan optimasi dengan memperhatikan bahwa hanya ada beberapa persamaan garis yang penting, yaitu yang berada pada bagian lower-envelope seperti yang ditunjukkan gambar berikut:

Observasi 5:
Setiap garis mungkin menyatu dengan lower-envelope dan mungkin tidak. Bila menyatu, maka dipastikan hanya ada dua kejadian: 1) garis mulai menjadi bagian dari lower-envelope, disusul dengan 2) garis sudah bukan menjadi bagian dari lower-envelope. Sekali keluar dari lower-envelope, maka garis itu tidak akan pernah menjadi bagian lower-envelope lagi. Sifat ini bisa dimanfaatkan!

Prosedur yang berikutnya perlu dilakukan mirip dengan pemrosesan titik pada algoritma Graham's scan dalam mencari convex hull. Buat sebuah stack yang menampung garis-garis yang mungkin menjadi bagian lower-envelope di kemudian hari. Setiap kali hendak memasukkan garis baru, buang semua garis pada top of stack yang tidak mungkin lagi menjadi bagian lower-envelope (karena tergantikan oleh garis yang baru ini).

Dapat diperhatikan bahwa isi stack ini adalah garis-garis yang gradiennya terurut menurun. Berikut visualisasi ketika hendak memasukkan garis baru:

Misalkan gambar kiri menyatakan keadaan sebelum dimasukkan garis baru. Ketika ada garis baru mau dimasukkan (garis merah pada gambar tengah), maka garis biru tidak akan pernah menjadi bagian dari lower-envelope lagi. Oleh karena itu, garis biru bisa dibuang dan hasil akhirnya ditunjukkan pada gambar kanan. Saya akan sebut garis yang tidak akan menjadi bagian lower-envelope lagi sebagai garis "tidak penting".

Syarat untuk menentukan apakah suatu garis masing penting atau tidak penting sederhana, tinggal perhatikan 2 elemen teratas pada top of stack (dengan kata lain, 2 garis dengan gradien terkecil). Bila ketiga titik potong dari masing-masing pasangan garis tersebut teratur, maka tidak ada garis yang tidak penting. Sementara bila tidak teratur, maka garis dengan gradien terkecil sudah "tidak penting" (karena ditemukan yang lebih penting, yaitu garis yang baru mau dimasukkan). Detil tentang implementasinya dapat Anda turunkan dengan rumus-rumus perpotongan garis.

Sekarang, ekstraksiMinimum dapat dilakukan dalam O(1), cukup dengan memelihara persamaan garis mana yang merupakan bagian dari lower-envelope. Hal ini bisa diimplementasikan dengan membuat variabel penunjuk pada stack (bila ingin lebih formal, sebenarnya yang digunakan bukan stack, melainkan deque karena diperlukan operasi pop-front, push-back, dan pop-back). Akhirnya, didapatkan algoritma dengan kompleksitas O(NK).

Catatan: teknik ini biasa disebut dengan DP convex-hull, atau convex-hull-optimization.

Implementasinya tidak rumit dan dapat di-coding dalam waktu singkat.