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.

Misalkan B'(x) menyatakan posisi si-B pada detik ke-x dengan polyline yang baru. Jika paket dikirimkan pada A(t), maka paket akan diterima di posisi B'(t).

Untuk memperjelas, perhatikan gambar berikut:

Jika paket dikirimkan saat si-A berada di posisi x, maka si-B akan menerimanya pada posisi x juga. Demikian pula untuk y.

Kini persoalan bisa dipandang menjadi si kurir bergerak secara instan!

Observasi 2:
Paket harus dikirimkan antara detik 0 dan t, dengan t adalah waktu si-B mencapai titik akhir perjalanannya.

Observasi 3:
Jika pada suatu waktu x (0 ≤ x ≤ t) jarak A(x) dengan B'(x) pernah lebih kecil atau sama dengan R, maka paket berhasil dikirimkan. Hal ini jelas karena kini pengiriman berlangsung secara instan.

Untuk memeriksa apakah jarak A(x) dengan B'(x) sempat lebih kecil atau sama dengan R, bisa dicari jarak terpendek yang pernah dicapai oleh A(x) dengan B'(x) lalu dibandingkan dengan R.

Beruntungnya, mencari jarak terpendek yang pernah dicapai tidak sulit. Kita akan bekerja dengan persamaan parametrik.
Misalkan:
Polyline A: \(\left[ A_1, A_2 \right] \)
Polyline B yang sudah dibuang R unit pertama: \( \left[ B_1, B_2 \right] \)

\(
\displaystyle A(x) = A_1 + \frac{x}{t} dA \\
\displaystyle B'(x) = B_1 + \frac{x}{t} dB
\)

dengan:
\(
dA = A_2 - A_1 \\
dB = B_2 - B_1
\)

Lalu definisikan \(f(x)\) sebagai jarak antara \(A(x)\) dengan \(B'(x)\)
\(
\begin{eqnarray*}
f(x) &=& \left|\left| A(x) - B'(x) \right|\right| \\
&=& \left|\left| (A_1 - B_1) + \frac{x}{t} (dA - dB)\right|\right|
\end{eqnarray*}
\)

Misalkan:
\(
\displaystyle P = A_1 - B_1 \\
\displaystyle Q = dA - dB \\
\displaystyle m = \frac{x}{t} \\
\)

Dengan \(m\) terdefinisi untuk \([0, 1]\):
\(
\begin{eqnarray*}
f(m) &=& \left|\left| P + mQ \right|\right| \\
&=& \sqrt{(P + mQ)_x^2 + (P + mQ)_y^2} \\
&=& \sqrt{P_x^2 + 2P_xQ_xm + Q_x^2m^2 + P_y^2 + 2P_yQ_ym + Q_y^2m^2} \\
&=& \sqrt{\left( Q_x^2 + Q_y^2 \right) m^2 + \left(2P_xQ_x + 2P_yQ_y\right) m + \left( P_x^2 + P_y^2 \right)}
\end{eqnarray*}
\)

Kita dapatkan bahwa \(f(m)\) merupakan akar dari fungsi kuadrat yang hanya terdefinisi untuk \(m\) antara 0 sampai dengan 1. Nilai minimal tentu saja dicapai saat fungsi kuadrat ini mencapai titik minimum. Titik terendah dari fungsi kuadrat \(ax^2 + bx + c\) adalah \(-b/(2a)\). Namun titik ini bisa saja berada di luar \([0, 1]\). Jika terjadi demikian, ambil nilai terendah antara \(f(0)\) atau \(f(1)\).

Dengan begini, kita sudah bisa menyelesaikan persoalan ini untuk polyline berupa 1 segmen garis. Pemeriksaan apakah dengan suatu nilai R paket terkirim atau tidak bekerja dalam O(1). Sekarang saatnya kita perluas solusi untuk kasus lebih umum.

Hal yang diidamkan adalah memotong-motong polyline ini menjadi beberapa segmen garis dan menyelesaikannya satu per satu. Kenyataannya, hal ini bisa dilakukan!

Kita menjaga supaya dalam suatu pemrosesan sepasang segmen garis, tidak ada segmen garis yang "berbelok". Ada dua kasus yang perlu ditangani, yaitu:

1. Si-A berbelok sebelum si-B menyelesaikan perjalanan 1 segmen. Untuk kasus ini, pecah perjalanan si B menjadi 2 segmen garis.
2. Si-B berbelok sebelum si-A menyelesaikan perjalanan 1 segmen. Untuk kasus ini, pecah perjalanan si A menjadi 2 segmen garis.

Dengan cara ini, akan didapatkan maksimal |A|+|B| pasangan segmen garis, dengan |A| menyatakan banyaknya segmen garis pada polyline A dan |B| menyatakan banyaknya segmen garis pada polyline B. Untuk soal ini, maksimal dihasilkan 2N pasangan segmen garis.

Jadi gunakan binary search, lalu periksa 2N pasangan segmen garis ini. Kompleksitas akhir adalah O(N log N).

Waspada

Ini soal geometri, gunakan epsilon!

Berikut adalah contoh solusi dari saya:

syntax highlighting tutorial