Seperti judulnya, kali ini saya akan bercerita tentang grid compression. Sebelumnya ada suatu kisah.
Suatu ketika saat Pelatnas 2 TOKI 2011, terdapat soal yang menyeramkan. Saya tidak berhasil menemukan soal tersebut, tapi intinya seperti ini:
Batasan:
Saya berpikir seharian, dan tidak menemukan bagaimana cara menyelesaikannya. Kemudian kami diberikan contoh solusi soal tersebut dalam bentuk kode. Saya menghabiskan semalaman untuk memahami kode tersebut, dan akhirnya mengerti penyelesaian solusinya.
Misalkan nilai maksimal seluruh koordinat cukup kecil, yaitu 100. Sebenarnya kita cukup membuat array boolean 2 dimensi, lalu untuk setiap sel yang merupakan bagian dari persegi panjang, kita tandai sebagai true. Perhitungan luasnya sederhana, yaitu tinggal menghitung banyaknya sel yang bernilai true. Untuk keliling, kita perlu menghitung banyaknya "sekat" yang memisahkan dua sel bernilai true dan false.
Kurang lebih solusinya seperti ini:
Kompleksitas solusi ini adalah O(N*MAXV*MAXV).
Solusi ini tidak dapat digunakan ketika rentang koordinatnya besar. Namun perhatikan bahwa sebenarnya tidak semua titik koordinat kita perlukan. Apabila hanya ada paling banyak 50 persegi panjang, berarti hanya ada 2*50 posisi x yang perlu diperhatikan (dikali dua karena terdapat x1 dan x2). Demikian pula untuk posisi y. Artinya, kita dapat mentransformasi seluruh koordinat 109*109 itu menjadi koordinat 100*100. Teknik ini biasa disebut dengan "grid compression", atau kadang cukup "compress" saja.
Grid compression dapat diimplementasikan dengan membuat pemetaan.
Untuk membuat pemetaan, cara yang saya sukai adalah dengan menampung semua kemungkinan nilainya, sort, lalu unique. Pada C++:
Unique adalah STL dari include<algorithm>, yang menerima vector yang terurut, lalu memampatkan seluruh elemen yang unik ke bagian awal vector, dan akhirnya mengembalikan pointer pertama elemen yang tidak unik. Elemen-elemen tidak unik yang terletak di bagian akhir vector ini biasanya teracak.
Sebelum unique:
Sesudah unique:
Pada akhirnya, erase akan menghapus seluruh elemen tidak unik ini dari vector.
Kini kita dapatkan pemetaan dari nilai yang sudah dikompres ke nilai aslinya. Apabila dibutuhkan pemetaan balik dari nilai asli ke nilai yang sudah dikompres, Anda dapat melakukan binary search pada vector realX, dan indeks elemen yang ditemukan adalah nilai kompresinya.
Perhatikan contoh kasus berikut.
Untuk mencari nilai yang sudah dikompres untuk 5, lakukan binary search untuk mencari indeksnya. Akan ditemukan bahwa 4 merupakan indeks dari elemen bernilai 5, yang artinya juga nilai yang sudah dikompres untuk 5 adalah 4.
Apabila Anda ingin praktis, boleh juga digunakan unordered_map atau map pada STL C++ untuk pemetaan baliknya.
Setelah menguasai grid compression, solusi soal di atas dapat dimodifikasi:
Solusi ini bekerja dalam O(N3).
Akhirnya sesudah mengerjakan soal ini, saya menguasai teknik grid compression.
Soal yang saya ceritakan sebenarnya adalah penyederhanaan dari soal aslinya yang berbentuk 3 dimensi:
Untuk mengoptimisasinya, setiap balok tidak "diisi" dengan for-loop 3 lapis, melainkan hanya "diisi" keenam "papan permukaan"-nya saja. Setelah memproses seluruh balok, lakukan floodfill dari koordinat (0, 0, 0). Floodfill ini tidak boleh menembus papan permukaan yang sudah ada. Pada akhirnya, volume dapat dihitung dengan memproses sel yang tidak terkena floodfill, dan luas permukaan dengan sel terkena floodfill yang berbatasan dengan sel yang terkena floodfill. Solusi ini bekerja dalam O(N3). GILA.
Bila Anda menemukan soal latihan grid compression yang bagus, mohon memberi tahu saya dengan menuliskannya di bagian komentar. Semoga bermanfaat!
Suatu ketika saat Pelatnas 2 TOKI 2011, terdapat soal yang menyeramkan. Saya tidak berhasil menemukan soal tersebut, tapi intinya seperti ini:
- Terdapat ruang 2 dimensi
- Akan dibangun sebuah gambar, dapat didekomposisi menjadi N persegi panjang
- Persegi panjang ke-i terletak di koordinat (xi1, yi1) sampai dengan (xi2, yi2)
- Beberapa persegi panjang boleh saja saling tumpang tindih
- Wujud gabungan dari seluruh persegi panjang ini adalah gambar yang dimaksud
- Cari keliling dan luas dari gambar ini!
Batasan:
- N ≤ 50
- 0 ≤ nilai seluruh koordinat ≤ 109
Saya berpikir seharian, dan tidak menemukan bagaimana cara menyelesaikannya. Kemudian kami diberikan contoh solusi soal tersebut dalam bentuk kode. Saya menghabiskan semalaman untuk memahami kode tersebut, dan akhirnya mengerti penyelesaian solusinya.
Teknik Grid Compression
Misalkan nilai maksimal seluruh koordinat cukup kecil, yaitu 100. Sebenarnya kita cukup membuat array boolean 2 dimensi, lalu untuk setiap sel yang merupakan bagian dari persegi panjang, kita tandai sebagai true. Perhitungan luasnya sederhana, yaitu tinggal menghitung banyaknya sel yang bernilai true. Untuk keliling, kita perlu menghitung banyaknya "sekat" yang memisahkan dua sel bernilai true dan false.
Kurang lebih solusinya seperti ini:
Kompleksitas solusi ini adalah O(N*MAXV*MAXV).
Solusi ini tidak dapat digunakan ketika rentang koordinatnya besar. Namun perhatikan bahwa sebenarnya tidak semua titik koordinat kita perlukan. Apabila hanya ada paling banyak 50 persegi panjang, berarti hanya ada 2*50 posisi x yang perlu diperhatikan (dikali dua karena terdapat x1 dan x2). Demikian pula untuk posisi y. Artinya, kita dapat mentransformasi seluruh koordinat 109*109 itu menjadi koordinat 100*100. Teknik ini biasa disebut dengan "grid compression", atau kadang cukup "compress" saja.
Implementasi
Grid compression dapat diimplementasikan dengan membuat pemetaan.
Untuk membuat pemetaan, cara yang saya sukai adalah dengan menampung semua kemungkinan nilainya, sort, lalu unique. Pada C++:
Unique adalah STL dari include<algorithm>, yang menerima vector yang terurut, lalu memampatkan seluruh elemen yang unik ke bagian awal vector, dan akhirnya mengembalikan pointer pertama elemen yang tidak unik. Elemen-elemen tidak unik yang terletak di bagian akhir vector ini biasanya teracak.
Sebelum unique:
1 1 1 2 3 4 4 5 5 5 8 8
Sesudah unique:
1 2 3 4 5 8 5 4 5 1 8 1
^
nilai kembalianPada akhirnya, erase akan menghapus seluruh elemen tidak unik ini dari vector.
Kini kita dapatkan pemetaan dari nilai yang sudah dikompres ke nilai aslinya. Apabila dibutuhkan pemetaan balik dari nilai asli ke nilai yang sudah dikompres, Anda dapat melakukan binary search pada vector realX, dan indeks elemen yang ditemukan adalah nilai kompresinya.
Perhatikan contoh kasus berikut.
indeks: 0 1 2 3 4 5 realX : 1 2 3 4 5 8
Untuk mencari nilai yang sudah dikompres untuk 5, lakukan binary search untuk mencari indeksnya. Akan ditemukan bahwa 4 merupakan indeks dari elemen bernilai 5, yang artinya juga nilai yang sudah dikompres untuk 5 adalah 4.
Apabila Anda ingin praktis, boleh juga digunakan unordered_map atau map pada STL C++ untuk pemetaan baliknya.
Setelah menguasai grid compression, solusi soal di atas dapat dimodifikasi:
Solusi ini bekerja dalam O(N3).
Akhirnya sesudah mengerjakan soal ini, saya menguasai teknik grid compression.
Versi asli soal
Soal yang saya ceritakan sebenarnya adalah penyederhanaan dari soal aslinya yang berbentuk 3 dimensi:
- Terdapat ruang 3 dimensi
- Akan dibangun sebuah patung, dapat didekomposisi menjadi N balok
- Balok ke-i terletak di koordinat (xi1, yi1, zi1) sampai dengan (xi2, yi2, zi2), melayang di udara tanpa bergerak
- Balok-balok boleh saja saling tumpang tindih
- Wujud gabungan dari seluruh balok-balok ini adalah patung yang dimaksud
- Pada wujud gabungan, dijamin tidak terdapat lubang udara di tengah-tengah patung
- Cari luas permukaan dan volume dari balok ini!
Untuk mengoptimisasinya, setiap balok tidak "diisi" dengan for-loop 3 lapis, melainkan hanya "diisi" keenam "papan permukaan"-nya saja. Setelah memproses seluruh balok, lakukan floodfill dari koordinat (0, 0, 0). Floodfill ini tidak boleh menembus papan permukaan yang sudah ada. Pada akhirnya, volume dapat dihitung dengan memproses sel yang tidak terkena floodfill, dan luas permukaan dengan sel terkena floodfill yang berbatasan dengan sel yang terkena floodfill. Solusi ini bekerja dalam O(N3). GILA.
Latihan
Saran dari anonim (dari komentar):Penutup
Grid compression sering digunakan, terutama untuk tingkat ICPC. Biasanya muncul sebagai ide yang mendukung algoritma utama. Grid compression juga digunakan pada range tree.Bila Anda menemukan soal latihan grid compression yang bagus, mohon memberi tahu saya dengan menuliskannya di bagian komentar. Semoga bermanfaat!
Ini salah satu contoh soal yang menggunakan teknik grid compression. http://bit.ly/2uOsxMy. CMIIW.
BalasHapusNah iya betul, terima kasih ya
HapusSaya tambahkan ke tulisan ini