2015 Google Code Jam Round 2

contents

  1. 1. A. Pegman
  2. 2. B. Kiddie Pool
    1. 2.1. Linear Programming
    2. 2.2. Greedy
    3. 2.3. Minkowski Sum

超過凌晨的競賽,隔天起床有一種說不出的疲累感,坑了一個早上,仍然沒想到最後幾題。看來已經玩不下去!圍觀到這裡。

A. Pegman

在谷歌地圖上放置一個小人,小人會根據當前給予的方向指標持續地移動,直到碰到下一個方向指標,請問至少要改變幾個方向指標所指引的方向,滿足在任何一個小人位置都不會走到邊界外部。

由於放在非指標位置就不能移動,只需要考慮小人放在指標上,考慮每一個方向指標都指向另一個指標,這樣就能保證有數個循環,盡可能地挑選原方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;

char sg[128][128];
int ig[128][128];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char dd[] = "><v^";
int main() {
int testcase, n, m, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%s", sg[i]);

int idx = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (sg[i][j] != '.') {
ig[i][j] = idx++;
}
}
}

int match = 0, ret = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (sg[i][j] != '.') {
int odd = 0;
for (int k = 0; k < 4; k++)
if (dd[k] == sg[i][j])
odd = k;
int cost = 1, mm = 0;
for (int k = 0; k < 4; k++) {
int x = i, y = j;
x += dx[k], y += dy[k];
while (x < n && x >= 0 && y < m && y >= 0) {
if (sg[x][y] != '.') {
if (k == odd)
cost = 0;
mm = 1;
break;
}
x += dx[k], y += dy[k];
}
}
match += mm, ret += cost;
}
}
}

printf("Case #%d: ", ++cases);
if (match != idx)
puts("IMPOSSIBLE");
else
printf("%d\n", ret);
}
return 0;
}

B. Kiddie Pool

放滿游泳池的水,目標容積 $V$ 溫度 $X$,有 $N$ 種水源,每一種水源有各自的流速 $R$、溫度 $C$,水源可以同時放水,請問達到目標容積、溫度的最少時間為何。

當下直觀地沒考慮水源可以同時使用,卡了一陣子。

Linear Programming

發現可以同時運作,考慮二分最少時間,其中一種最簡單的應用線性規劃,判斷線性規劃方程式是否有解,python 內建 LP 也許很過分。自己曾經寫過 simplex,不過調校上相當痛苦,判斷有沒有解有困難。以下為 LP 模型,二分時間 $\text{limit_time}$

  1. $x_i \le \text{limit_time} * R[i]$
  2. $\sum{C_i x_i} = V X$
  3. $\sum x_i = V$
  4. $x_i \ge 0$

帶入 simplex algorithm,判斷四條方程式是否有解。代碼就不附,解不出來。

Greedy

另外一種方式,考慮限制 t 時間內能調配的最高溫 high_t、最低溫 low_t,這兩種溫度可以貪心法求得,接著考慮目標溫度 low_t <= X <= high_t,因為中間的溫度一定可解,具有連續性。

複雜度 $O(N \log X)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h> 
using namespace std;

const int MAXN = 128;
const double eps = 1e-10;
double R[MAXN], C[MAXN], V, X;
int N;
vector< pair<double, double> > A;

int checkTime(double limitT) {
double v, t, low_t, high_t;
double mxV, teC;

v = t = 0;
for (int i = 0; i < N; i++) {
mxV = A[i].second * limitT; // flow in limit time
teC = A[i].first;

mxV = min(mxV, V - v);
t = (t * v + mxV * teC) / (v + mxV);
v += mxV;
if (v >= V - eps)
break;
}
if (v < V - eps)
return 0;
low_t = t;

v = t = 0;
for (int i = N-1; i >= 0; i--) {
mxV = A[i].second * limitT; // flow in limit time
teC = A[i].first;

mxV = min(mxV, V - v);
t = (t * v + mxV * teC) / (v + mxV);
v += mxV;
if (v >= V - eps)
break;
}
if (v < V - eps)
return 0;
high_t = t;
return X >= low_t - eps && X <= high_t + eps;
}
int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %lf %lf", &N, &V, &X);

A.clear();
for (int i = 0; i < N; i++) {
scanf("%lf %lf", &R[i], &C[i]);
A.push_back(make_pair(C[i], R[i]));
}
sort(A.begin(), A.end());

double mxT, mnT;
mnT = A[0].first, mxT = A[N-1].first;

printf("Case #%d: ", ++cases);
if (X < mnT - eps || X > mxT + eps) {
puts("IMPOSSIBLE");
} else {
double l = 0, r = 1e+9, mid; // MAXV / MINR = 10000.0 / 0.0001
double ret = 0;
for (int it = 0; it < 256; it++) {
mid = (l + r)/2;
if (checkTime(mid))
r = mid, ret = mid;
else
l = mid;
}
printf("%.8lf\n", ret);
}
}
return 0;
}

Minkowski Sum

在此先將問題轉換成「求 1 秒內最多能湊出多少公升的 X 度水」,知道單位時間內的最多流量,就能貪心得到最短時間。

將每一種水源 $(R_i, C_i)$ 轉換成向量 $v_i = (R_i, R_i \times C_i)$,目標要在 $t$ 時間內,得到 $\sum{t_i v_i} = (V, V \times X)$,滿足所有的 $t_i \le t$

將問題壓縮成 $t_i \in \left \[ 0, 1 \right]$,將所有符合的 $\sum{t_i v_i}$ 疊加起來,得到的區域相當於在做 Minkowski Sum,區域是一個凸多邊形。接著在 $y = X x$ 尋找交集的最大 x 值。

Demo

上圖是一個 3 個水源的情況,假設要湊出溫度 $X = 0.5$,相當於找 $y = 0.5 x$,這三個向量在單位時間內的疊加為淡紅色區域。為了得到這淡紅色區域,使用極角排序,依序疊加可以得到下凸包,反過來疊加可以得到上凸包。

明顯地要找一個凸包跟一條線的交點,得到單位時間內的最大流量。此時的 x 軸表示流量、y 軸表示熱量,找到交集中最大的 x 座標值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6

struct Pt {
double x, y;
int label;
Pt(double a = 0, double b = 0, int c = 0):
x(a), y(b), label(c) {}
Pt operator-(const Pt &a) const {
return Pt(x - a.x, y - a.y);
}
Pt operator+(const Pt &a) const {
return Pt(x + a.x, y + a.y);
}
Pt operator*(const double a) const {
return Pt(x * a, y * a);
}
bool operator<(const Pt &a) const {
if (fabs(x - a.x) > eps)
return x < a.x;
if (fabs(y - a.y) > eps)
return y < a.y;
return false;
}
};
double dot(Pt a, Pt b) {
return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
bool cmp(const Pt& p1, const Pt& p2)
{
if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
if (p1.y * p2.y < 0) return p1.y > p2.y;
double c = cross2(p1, p2);
return c > 0 || (c == 0 && fabs(p1.x) < fabs(p2.x));
}
Pt getIntersect(Pt as, Pt ae, Pt bs, Pt be) {
Pt u = as - bs;
double t = cross2(be - bs, u)/cross2(ae - as, be - bs);
return as + (ae - as) * t;
}
int cmpZero(double v) {
if (fabs(v) > eps) return v > 0 ? 1 : -1;
return 0;
}
//
const int MAXN = 128;
int N;
double R[MAXN], C[MAXN], V, X;
void solveWithMinkowskiSum() {
vector<Pt> P;
for (int i = 0; i < N; i++)
P.push_back(Pt(R[i], R[i]*C[i]));
sort(P.begin(), P.end(), cmp); // solar sort

vector<Pt> convex;
double mxFlow = 0; // in unit time with temperature X
Pt u, v, o(0, 0), to(1, X); // y = (X) x, maximum x

u = v = Pt(0, 0);
convex.push_back(u);
for (int i = 0; i < N; i++) {
v = u + P[i];
u = v;
convex.push_back(v);
}

reverse(convex.begin(), convex.end());
u = v = Pt(0, 0);
for (int i = N-1; i >= 0; i--) {
v = u + P[i];
u = v;
convex.push_back(v);
}

for (int i = 0, j = (int) convex.size()-1; i < convex.size(); j = i++) {
u = convex[j], v = convex[i];
if (cmpZero(cross(o, to, u)) * cmpZero(cross(o, to, v)) < 0) {
Pt in = getIntersect(o, to, u, v);
mxFlow = max(mxFlow, in.x);
}
if (cmpZero(cross(o, to, v)) == 0)
mxFlow = max(mxFlow, v.x);
}

if (fabs(V) < eps)
printf("%.10lf\n", 0.0);
else if (fabs(mxFlow) < eps)
puts("IMPOSSIBLE");
else
printf("%.10lf\n", V / mxFlow);
}
int main() {
int testcase, cases = 0;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %lf %lf", &N, &V, &X);

V *= 10000, X *= 10000;
for (int i = 0; i < N; i++) {
scanf("%lf %lf", &R[i], &C[i]);
R[i] *= 10000, C[i] *= 10000;
}

printf("Case #%d: ", ++cases);
solveWithMinkowskiSum();
}
return 0;
}