Kamis, 11 April 2013

UVa 1232 - Skyline

Soal ini bersumber dari ICPC Regional Asia, Singapore, 2007-2008. Menarik untuk dibahas, sehingga saya menuliskannya di sini. Sangat disarankan Anda mencoba terlebih dahulu untuk menyelesaikannya.

Inti soalnya kita memiliki sebuah array yang awalnya berisi angka 0 dan akan melayani sejumlah operasi. Operasi ini adalah membuat nilai array di suatu interval tertentu menjadi nilai maksimum antara nilai sebelumnya dengan suatu nilai yang baru. Tugas kita adalah menghitung ada berapa kali perubahan nilai yang terjadi.

Sebuah kata kunci yang tidak boleh Anda lewatkan adalah "You may assume that the amount of overlap for each dataset is at most 2000000". Biasanya soal yang menyebutkan batasan seperti ini dapat diselesaikan dengan algoritma output-sensitive, artinya kompleksitasnya bergantung pada keluaran.
Berhubung di soal ini hanya ada satu macam operasi (query), kita bisa mengerjakannya secara offline (setiap operasi dibaca dulu, lalu dikerjakan dulu semuanya, baru dicetak semuanya). Biasanya cara ini lebih mudah ketimbang kita harus melaksanakan setiap operasi secara online.

Sekarang kita memiliki sejumlah interval posisi kiri dan kanan, yang menyatakan ketinggian dan kedalaman gedung. Berhubung yang kita miliki adalah interval-interval, cara paling intuitif yang mungkin terpikir adalah mengurutkan interval itu, dari yang paling kiri. Setelah itu, kita proses mulai dari kiri ke kanan.

Untuk suatu petak di lokasi koordinat (i,i+1), mungkin ada beberapa gedung di sana. Sebut saja gedung-gedung itu memiliki ketinggian H[1], H[2], ..., H[X], bila diurutkan mulai dari gedung paling depan ke belakang. Misalkan array H itu adalah [2, 5, 3, 4, 6, 9, 8, 11, 15]. Banyaknya overlap yang perlu kita tambahkan adalah 6, karena [2, 5, 6, 9, 11, 15] membentuk deretan yang memenuhi persyaratan di soal. Gedung dengan ketinggian 3, 4, dan 8 tidak termasuk dalam overlap, karena mereka sudah tertutup oleh gedung yang lebih tinggi dan muncul sebelum dia.

Dengan ide tersebut, kita bisa melakukan sweep line dari kiri ke kanan. Setiap menemukan awal interval, selipkan ketinggian dan kedalaman gedung itu ke array H. Sementara itu bila menemukan akhir interval, keluarkan elemen itu dari array H. Di setiap petak, tambahkan nilai overlap ke jawaban akhir. Sekarang tinggal bagaimana kita menyelipkan/menghapus elemen baru ke H dan menghitung banyaknya overlap secara efisien.

Kembali pada contoh sebelumnya, misalnya H = [2, 5, 3, 4, 6, 9, 8, 11, 15] dan H[i] menyatakan elemen ke-i (one based). Gedung dengan ketinggian H[1] pasti kita hitung, karena dia gedung yang pertama ada. Gedung berikutnya yang akan kita hitung adalah gedung i (i > 1), dimana H[i] ≥ H[1] dan i adalah seminimal mungkin. Gedung berikutnya yang harusnya kita hitung sebagai bagian dari overlap juga dapat dicari dengan cara yang serupa.

Karena persoalan ini membutuhkan operasi pencarian minimum, dengan sedikit utak-atik kita dapat memanfaatkan struktur data segment tree. Anggap kita punya array baru bernama S, dan untuk setiap i, S[H[i]] = i. Untuk contoh di atas, S = [-, 1, 3, 4, 2, 5, -, 7, 6, -, 8, -, -, -, 9, ...] (- menyatakan kosong, tidak terdefinisi). Misalkan gedung yang baru saja dihitung ke dalam overlap adalah gedung ke-S[i]. Maka gedung berikutnya yang perlu dihitung adalah gedung ke-min(S[i+1], S[i+2], S[i+3], ...). Mengapa hal ini bisa benar? Karena kita mencari gedung yang lebih tinggi dari i, dan indeksnya paling kecil, persis seperti yang kita inginkan. Ulangi terus pencarian tersebut sampai ke gedung yang terakhir di dalam S dan tambahkan ke jawaban akhir.

Berapa banyaknya elemen di dalam S? Paling banyak adalah sebanyak N (banyaknya gedung), karena paling banyak hanya ada N ketinggian gedung yang berbeda. Oleh karena itu setiap operasi pencarian gedung berikutnya untuk dihitung dilakukan dalam \(O(\log{N})\).

Bagaimana dengan update saat melakukan line sweep? Sama sekali tidak sulit karena kita sudah menggunakan segment tree. Bila gedung itu memiliki ketinggian h dan di kedalaman d, cukup update S[h] = d (tentunya dengan operasi segment tree, kompleksitasnya \(O(\log{N})\).
Jika K menyatakan banyaknya overlap, maka kompleksitas algoritma ini adalah \(O((K+N)\log{N})\). Karena paling banyak ada 2N kali update, dan K kali operasi cari minimum.

Berikut ini implementasi saya:

Tidak ada komentar :

Posting Komentar