Tags
Ringkasan Pembahasan Soal Radar
Pasti ada penempatan radar-radar optimal di mana semua radar berada di titik dengan nilai y yang sama (segaris). Pada penempatan ini, pesawat dengan T yang berbeda ataupun V yang berbeda pasti akan terdeteksi di waktu yang berbeda. Contoh saja, kita bisa mengambil y bilangan irrasional, misalnya PI.
Oleh karena itu, kita bisa mengelompokkan pesawat-pesawat berdasarkan T dan V (yang T dan V nya sama diberi nomor yangsama).
Misal ada 3 pesawat dengan T dan V berturut-turut (dari kiri ke kanan):
(a) T = 5, V = 2
(b) T = 3, V = 2
(c) T = 5, V = 2
Pesawat (a) bisa kita beri nomor 1, (b) bisa kita beri nomor 2, (c) karena sama dengan (a) kita beri nomor 1. Kasus ini bisa dikodekan sebagai:
1 2 1
Misal r adalah radar. Kita bisa menempatkan r seperti berikut ini sehingga semua pesawat pasti terdeteksi:
1 r 2 1
Ketika pesawat-pesawat bernomor 1 melewati sisi radar, kedua pesawat dapat terdeteksi (sekali lagi ingat, pesawat-pesawat yangdinomori berbeda akan melewati samping radar di waktu yang berbeda). Begitu pula ketika satu-satunya pesawat bernomor 2melewati sisi radar ia akan terdeteksi.
Ilustrasi:
1 r . 1 (ketika pesawat-pesawat bernomor 1 melewati sisi-sisi radar)
. r 2 . (ketika pesawat-pesawat bernomor 2 melewati sisi-sisi radar)
Sekarang kita coba meletakkan radar-radar sesedikit mungkin. Pada solusi optimal, tidak akan ada dua atau lebih pesawat bernomor sama terletak di sebelah kiri radar paling kiri. Mengapa? Karena hal ini akan mengakibatkan pesawat bernomor tersebut yangberposisi paling kiri tidak terdeteksi radar. Perhatikan contoh berikut.
[1] 1 r …
Pada kasus tersebut, pesawat yang diberi kurung siku tidak dapat terdeteksi. Perhatikan kasus berikut juga untuk lebih jelasnya:
1 2 1 r …
Pada saat pesawat-pesawat bernomor 1 melewati samping radar r, kasus sebelumnya terjadi ([1] 1 r …).
Nah, perhatikan bahwa jika radar paling kiri bisa diletakkan di antara pesawat ke-i dan ke-(i + 1) dari kiri maupun di antara pesawat dengan urutan ke-j dan ke-(j + 1), dan i > j, pasti ada solusi yang lebih atau setidaknya sama optimal dengan peletakkan radar di antara pesawat ke-i dan ke-(i + 1) dibanding di antara j dan (j + 1).
Mengapa? Asumsikan ada solusi optimal di mana radar terkiri diletakkan di antara j dan (j + 1). Geser radar tersebut ke posisi antara i dan (i + 1), maka semua pesawat tetap dapat terdeteksi.
Oleh karena itu, letakkan radar terkiri di posisi sekanan mungkin yang masih valid (tidak ada dua atau lebih pesawat bernomor sama terletak di sebelah kirinya). Lalu hapus semua pesawat yang bisa ia deteksi baik di kiri maupun di kanan. Lalu kita peroleh subproblem yang sama persis (cari peletakan radar terkiri lagi), bisa rekursi. Misal solusi optimal untuk subproblem ini adalah S’, maka solusi untukproblem kita adalah S’ + 1 (tambah 1 karena kita sudah meletakkan sebuah radar di posisi paling kiri).
Dengan solusi berdasar pada teknik greedy ini, jika diimplementasikan dengan tepat akan diperoleh algoritma dengan kompleksitasO(n lg n).
kalau butuh pemikiran seperti ini sih 5 jam kurang kak :p
*Ali Jaya Meilio Like Komentar Irvin :p
Pembahasan soal radar memang ditulis sedetil-detilnya supaya tidak ambigu. By no means you should do exactly all those steps in the competition. Sebagian besar hal di pembahasan ini sebenarnya “obvious”, tapi tetap ditulis. Dengan kata lain, algoritmanya seharusnya bisa diperoleh hanya dalam beberapa menit dan implementasinya pun sederhana.
parah kau, san. Bikin soal kayak begini. Kalau aku dikasih tu soal pasti aku bakal nangis semalaman…
Wah, ada Nisma! Apa kabar? Lama ga kontak
Yup, makanya soalnya baru dikeluarin setelah elu lulus. Hahaha *bercanda Nis*
Yup, lama tak bersua juga, San.
Ya iya,lah. kagak mungkin kau jadi peserta plus pembuat soal. tidak adil itu namanya..
Ih blognya jadi imut gitu :*
Risan cupu ini ga beres2 wkwkwkwk #ampunsannn
kurang ngerti solusi Radar pesawat subtask 4 & 5
mungkin bisa dijelasin dikit
terima kasih
Done.
@kak risan : hmmm kak… ntuh yakin bisa N log N??? bukannya worstcasenya bisa N^2
… jadi tiap kali ngeiterasi pesawat, kan ngecek ke sebelum2nya 
(sebanyak N – posisi sekarang)…
jadi kalo semua pesawatnya beda2 tipe nya
kok bisa N log N
… apa ngesearchnya pake binary search 
… tapi kalau gitu musti pake sorting dunk (insertion 
)…
pusing @.@ LOL
Engga diimplementasiini langsung kayak gitu. Ada triknya supaya jadi O(n lg n), dan lumayan gampang (kalian coba cari sendiri). Tapi udah gw jelasin triknya di pembahasan yang non-summary.
duh kak… masih kurang ngerti triknya bagian
“Jika nomor radar yang tersimpan untuk pesawat jenis i lebih kecil dari nomor radar yang terakhir dipasang, maka ia terdeteksi oleh radar yang terakhir dipasang tersebut. Jika tidak, kita harus memasang radar baru untuk mendeteksi pesawat ini.”