Tags

2. Radar Pesawat

Pembuat soal: Risan

URL:

Fakta-fakta menarik:

  • Soal ini adalah soal dengan nilai rata-rata, median dan maksimum peserta paling kecil di kompetisi ini.
  • Ini adalah soal ketiga saya di OSN. Tahun lalu saya mempropose Waterfall dan Missile yang keduanya muncul di hari kedua OSN 2010 di mana hanya Felik Junvianto yang berhasil menyelesaikan soal Waterfall dengan sempurna :).
  • Awalnya, soal ini hanya memiliki tiga subtask. Subtask pertama bernilai 20 poin adalah subtask 3 saat ini, subtask kedua bernilai 40 poin adalah subtask 4 saat ini, dan subtask ketiga bernilai 40 poin adalah subtask 5 saat ini. Tetapi setelah melalui berbagai pertimbangan dari juri-juri lain, ditambahkanlah subtask 1 dan 2 serta poin untuk subtask 1 yang lama dinaikkan menjadi 40 poin.
  • Di luar prediksi pembuat soal, setelah diubah seperti ini pun tidak ada satu pun peserta, baik OSN maupun OSN terbuka, yang berhasil menyelesaikan lebih dari 3 subtask pertama. Dan bahkan, subtask ke-3 pun terbukti sangat sulit diraih. Padahal di malam sebelumnya, saya masih berpikir akan ada 1 atau 2 peserta yang berhasil memperoleh nilai penuh di soal ini dan beberapa peserta memperoleh nilai 85.

Mari kita mulai analisis soal ini dengan beberapa definisi dan lemma:

Definisi 2.1 Dua buah pesawat disebut sejenis jika dan hanya jika mereka mulai terbang di saat bersamaan dan memiliki kecepatan yang sama.

Definisi 2.2 Sebuah solusi disebut valid jika dan hanya jika semua pesawat berhasil dideteksi oleh semua radar yang dipasang pada konfigurasi di solusi ini dengan memperhatikan semua batasan yang terdapat di soal.

Lemma 2.1 Banyaknya radar yang diperlukan untuk mendeteksi seluruh pesawat tidak akan kurang dari 1, kecuali banyaknya pesawat adalah 0.

Lemma 2.2 Dua buah pesawat akan selalu melewati titik dengan nilai y yang sama jika dan hanya jika mereka terbang bersama-sama dengan kecepatan yang sama.

Lemma 2.3 Dua buah pesawat yang mulai terbang di waktu berbeda atau yang terbang dengan kecepatan berbeda akan melalui titik dengan nilai y berupa bilangan irrasional di saat yang berbeda.

Lemma 2.4 Ada penempatan radar-radar optimal di mana semua radar berada di titik dengan nilai y yang sama.

Subsoal 1 (15 poin)

Batasan: Tidak ada dua pesawat yang mulai terbang di saat bersamaan maupun memiliki kecepatan yang sama. Asumsikan kita meletakkan sebuah radar pada sembarang titik yang tidak akan dilalui pesawat manapun dan memiliki nilai y irrasional. Berdasarkan lemma 2.3 dan batasan di soal ini, semua pesawat akan melewati sisi radar kita di saat berbeda. Jelas bahwa setiap kali sebuah pesawat melewati sisi radar, ia tidak terhalang oleh objek apa pun dari radar sehingga ia akan terdeteksi oleh radar. Dengan kata lain, semua pesawat dapat dideteksi cukup dengan tidak lebih dari satu radar. Berdasarkan batas minimum yang diberikan oleh lemma 2.1, dapat disimpulkan bahwa banyaknya radar yang diperlukan pada kasus di subtask ini adalah 1.

Subsoal 2 (15 poin)

Batasan: Semua pesawat mulai terbang di saat bersamaan dan memiliki kecepatan yang sama.

Lemma 2.5 Sebuah radar tidak dapat mendeteksi lebih dari dua buah pesawat sejenis. Mari kita sebut banyaknya radar yang diperlukan untuk menembak N buah pesawat sejenis adalah r.

Klaim

r >= ceil(N / 2)………….(2.1)

Pembuktian Asumsikan r < ceil(N / 2). Berdasarkan Pigeon Hole Principle, pasti ada sebuah radar yang mendeteksi setidaknya ceil(N / r) pesawat. Karena r < ceil(N / 2), ceil(N / 2) pasti lebih dari 2. Kontradiksi dengan lemma 2.5. QED.

Klaim

r <= ceil(N / 2)………….(2.2)

Pembuktian Kita nomori pesawat dari kiri ke kanan dengan bilangan bulat 1, 2, …, N. Untuk k bilangan bulat positif di mana 2k – 1 <= N, kita letakkan sebuah radar pada titik dengan posisi y manapun dan posisi x lebih besar dari posisi x pesawat ke-(2k – 1). Jika 2k <= N, radar tersebut harus diletakkan pada posisi x yang lebih kecil dari posisi x pesawat ke-2k. Dengan posisi penempatan ini, banyaknya radar yang dibutuhkan adalah ceil(N / 2) dan seluruh pesawat dapat terdeteksi. Sehingga, pasti ada solusi valid dengan radar sebanyak maksimum ceil(N / 2). QED.

Berdasarkan pertidaksamaan (2.1) dan (2.2), kita peroleh:

ceil(N/2) <= r <= ceil(N/2)

dengan kata lain, r = ceil(N/2).

P.S.: ceil(x) adalah pembulatan ke atas dari x.

Subsoal 3 (40 poin)

Lemma 2.6 Pada solusi optimal, tidak ada dua buah radar sedemikian sehingga posisi x mereka sama-sama berada di antara posisi x pesawat ke-i dan pesawat ke-(i+1), sama-sama setelah pesawat terakhir, ataupun sama-sama sebelum pesawat pertama.

Pembuktian Asumsikan sebaliknya, maka kita bisa menghapus salah satu radar dan banyaknya pesawat yang bisa terdeteksi tetap sama. Kontradiksi. QED.

Berdasarkan Lemma 2.3 dan 2.4, kita bisa menyusun salah satu solusi optimal dengan hanya meletakkan semua radar pada y yang sama dan irrasional. Dengan kata lain, daerah penempatan radar berbentuk garis lurus.

Pertama-tama, kita dapat mengelompokkan garis tersebut menjadi N+1 bagian, dengan N merupakan banyaknya pesawat. Secara lebih akurat, kelompok pertama adalah daerah dengan posisi x lebih kecil dari posisi x pesawat pertama, kelompok ke-i adalah daerah dengan posisi x di antara posisi x pesawat ke-i dan ke-(i-1), dan kelompok terakhir adalah kelompok dengan posisi x lebih besar dari posisi x pesawat terakhir.

Berdasarkan lemma 2.6, pada masing-masing kelompok kita hanya perlu meletakkan 0 atau 1 buah radar. Dan dikarenakan N cukup kecil, algoritma brute force yang mencoba semua kemungkinan penempatan dengan kompleksitas O(N ^2* 2^N) cukup untuk menyelesaikan subtask ini. Untuk dua subtask terakhir, ada beberapa observasi tambahan.

Lemma 2.7 Pada solusi valid manapun, tidak ada dua pesawat sejenis di mana keduanya memiliki posisi x lebih kecil dari radar dengan posisi x paling kecil.

Lemma 2.8 Asumsikan S1 adalah solusi valid dengan banyak radar minimum ketika radar dengan posisi x paling kecil diletakkan di posisi x pada x1 dan S2 adalah solusi valid dengan banyak radar minimum ketika radar dengan posisi x paling kecil diletakkan di posisi x pada x2. Jika x1 > x2, maka banyaknya radar pada solusi S1 tidak akan melebihi banyaknya radar pada solusi S2.

Lemma 2.9 Memindahkan posisi x radar tidak akan memberikan efek apapun selama dia masih berada di kelompok yang sama. Berdasarkan lemma 2.7, kita telah menentukan posisi-posisi radar pertama yang mungkin. Berdasarkan lemma 2.8 dan lemma 2.9, di antara posisi-posisi yang mungkin tersebut kita letakkan radar di kelompok dengan nomor sebesar mungkin. Asumsikan P adalah himpunan pesawat-pesawat pada permasalahan awal dan P’ adalah himpunan pesawat-pesawat di P yang tidak terdeteksi radar tersebut.

Lemma 2.10 Banyaknya radar yang dibutuhkan adalah 1 lebih dari banyaknya radar yang dibutuhkan pada permasalahan dengan P’ sebagai masukan (terdapat subpermasalahan).

Subsoal 4 (15 poin)

Hanya dengan mengikuti observasi tersebut tanpa optimasi tambahan, algoritma berdasar pada teknik greedy tersusun dengan kompleksitas O(N^2). Caranya, letakkan radar pertama pada kelompok bernomor sebesar mungkin yang masih valid, hapus semua pesawat yang terdeteksi olehnya, selesaikan permasalahan serupa dengan pesawat-pesawat tersisa sebagai himpunan pesawat masukan.

Subsoal 5 (15 poin)

Algoritma yang diperlukan untuk menyelesaikan subtask ini sama persis dengan subtask 4, hanya dengan observasi tambahan. Setiap kali memasang sebuah radar, kita tidak perlu menghapus pesawat-pesawat yang terdeteksi olehnya secara literal.

Trik: Kita nomori radar-radar dengan bilangan natural 1, 2, …, r dari radar dengan posisi x paling kecil hingga radar dengan posisi x paling besar. Iterasikan pesawat mulai dari nomor terkecil hingga terbesar. Gunakan sebuah array untuk menampung nomor radar terbesar sejauh ini yang mendeteksi sebuah “jenis” pesawat yang mana sang radar berada di posisi x lebih kecil dari posisi x pesawat tersebut. 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. Dengan cara ini, kita bisa menyusun algoritma dengan kompleksitas O(n lg n).

Advertisements