Thursday, 26 February 2015

ICPC Wold Final 2014 - Messenger

Beberapa minggu terakhir ini saya sedang "balas dendam" soal-soal ICPC World Final tahun lalu (2014). Di antara beberapa soal yang telah saya selesaikan, ada sebuah soal yang sangat berkesan, yaitu yang berjudul Messenger. Oleh karena itu saya akan membahasnya.

Ringkasan Soal

Ada dua orang, sebut saja si-A dan si-B. Masing-masing dari mereka berjalan pada polyline (pada bidang 2 dimensi) dengan kecepatan 1 unit per detik. Polyline rute perjalanan mereka tidak harus sama. Si-A hendak mengirimkan paket ke si-B dengan cara menggunakan kurir. Kurir akan dilepas, lalu berjalan dengan kecepatan 1 unit per detik untuk bertemu si-B. Biaya kurir adalah jarak yang ditempuh si kurir. Perhatikan bahwa si-A dan si-B selalu berjalan tanpa henti, sehingga kurir harus tepat bertemu dengan si-B di suatu titik memberikan paketnya.

Pembahasan

Yang membuat soal ini sulit adalah si-A, si-B, dan kurir berjalan dengan kecepatan 1 unit per detik. Jika si kurir ini begitu dilepas si-A secara instan langsung bertemu si-B, soal menjadi lebih mudah!

Bagaimana pun juga, soal ini memiliki aroma binary search yang kuat. Jadi saya memulai dengan menembak suatu angka, misalkan R, yang menunjukkan jarak tempuh si kurir. Jika kurir berhasil mengirimkan paket ini, kurangi R. Jika tidak berhasil, tambahkan R.

Mari kita sederhanakan soalnya. Anggap polyline si-A dan si-B hanya berupa sebuah segmen garis.

Misalkan:
A(x): posisi si-A pada detik ke-x
B(x): posisi si-B pada detik ke-x

Observasi 1:
Jika si-A mengirimkan paket pada detik t, maka si-B harus menerima paket itu sebelum atau pada detik (t+R). Dengan kata lain, paket dikirim di posisi A(t) dan berhasil diterima di posisi B(t+R) jika jarak A(t) dengan B(t+R) kurang dari atau sama dengan R.

Dengan observasi 1, kita bisa membuang R unit pertama dari pergerakan si-B.