Kupas Kode: ICPC Wold Final 2014

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:

Si-A berbelok sebelum si-B menyelesaikan perjalanan 1 segmen. Untuk kasus ini, pecah perjalanan si B menjadi 2 segmen garis.
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:

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
 
#define REP(a,b) for (int a=0; a<b; a++)
 
#define INF 1e+30
#define MAXN 50005
#define EPS 1e-12
 
using namespace std;
 
struct point
{
  double x,y;
 
  point operator-(const point &other) {
    point temp;
    temp.x = x - other.x;
    temp.y = y - other.y;
    return temp;
  }
};
 
int TRY = 100;
int N[2];
point tik[2][MAXN];
point lover[2*MAXN][2];
 
bool eq(double a, double b){
  return fabs(a - b) < EPS;
}
 
bool lesseq(double a, double b){
  if (eq(a, b)) return 1;
  return a < b;
}
 
bool lesst(double a, double b){
  if (eq(a, b)) return 0;
  return a < b;
}
 
double clamp(double a, double b, double c){
  return max(a, min(b, c));
}
 
double dist(const point &a, const point &b){
  double dx = a.x - b.x;
  double dy = a.y - b.y;
  return sqrt(dx*dx + dy*dy);
}
 
struct position{
  int id;
  point current;
  int nex;
 
  position(){};
  position(int _id, double offset){
    id = _id;
    current = tik[id][0];
    nex = 1;
 
    // guaranteed valid
    advance(offset);
  }
 
  bool ended(){
    return nex == N[id];
  }
 
  double muv(){
    return dist(current, tik[id][nex]);
  }
 
  void advance(double offset){
    while (lesst(muv(), offset)){
      offset -= muv();
 
      current = tik[id][nex];
      nex++;
    }
 
    double dx = tik[id][nex].x - current.x;
    double dy = tik[id][nex].y - current.y;
    double len = dist(current, tik[id][nex]);
 
    current.x += offset/len * dx;
    current.y += offset/len * dy;
 
    if (eq(muv(), 0)){
      // may need this
      nex++;
    }
  }
};
 
bool ok(double R){
  position pos[] = {position(0,0), position(1,R)};
 
  int p = 0;
  while (!pos[0].ended() && !pos[1].ended()){
    lover[p][0] = pos[0].current;
    lover[p][1] = pos[1].current;
    p++;
 
    double adv = min(pos[0].muv(), pos[1].muv());
    pos[0].advance(adv);
    pos[1].advance(adv);
  }
  lover[p][0] = pos[0].current;
  lover[p][1] = pos[1].current;
  p++;
 
  // check pair of segment
  REP(i,p-1){
    point A = lover[i][0];
    point B = lover[i][1];
 
    point dA = lover[i+1][0] - lover[i][0];
    point dB = lover[i+1][1] - lover[i][1];
 
    point P = A - B;
    point Q = dA - dB;
 
    double pA = Q.x*Q.x + Q.y*Q.y;
    double pB = 2*P.x*Q.x + 2*P.y*Q.y;
    double pC = P.x*P.x + P.y*P.y;
 
    double t = clamp(0, -pB/(2*pA), 1);
    double minDistSQ = pA*t*t + pB*t + pC;
 
    if (lesseq(minDistSQ, R*R)){
      return 1;
    }
  }
  // check pair of point
  REP(i,p){
    if (lesseq(dist(lover[i][0], lover[i][1]), R)){
      return 1;
    }
  }
 
  return 0;
}
 
int main(){
  while (1){
    REP(i,2){
      if (scanf("%d", &N[i]) != 1){
        goto heaven;
      }
      REP(j,N[i]){
        scanf("%lf %lf", &tik[i][j].x, &tik[i][j].y);
      }  
    }
 
    double tourLength = 0;
    REP(i,N[1]-1){
      tourLength += dist(tik[1][i], tik[1][i+1]);
    }
 
    double ki = 0;
    double ka = tourLength;
    double ans = -1;
    REP(cob,TRY){
      double tgh = (ki + ka) / 2;
 
      if (ok(tgh)){
        ans = tgh;
        ka = tgh;
      }else{
        ki = tgh;
      }
    }
 
    if (ans < -0.5){
      printf("impossible\n");
    }else{
      printf("%.12lf\n", ans);
    }
  }
 
  heaven:
  return 0;
}

syntax highlighting tutorial

Pages

Kamis, 26 Februari 2015

ICPC Wold Final 2014 - Messenger

Ringkasan Soal

Pembahasan

Waspada

1 komentar :

Pages

Kamis, 26 Februari 2015

ICPC Wold Final 2014 - Messenger

Ringkasan Soal

Pembahasan

Waspada

Tulisan terkait:

1 komentar :