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

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

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

#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)$

#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 值。

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

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

#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;
}