Google Code Jam 2015 Round 1A

就結果來說...沒有參加實在太可惜了...參加了應該就ADVANCE了...

希望1B跟C不要比這場難就好了..

話說這場的時間是星期六的早上9時, 這星期實在太辛苦了..星期六真的要睡很久就沒參加了

事後在Practice看看水平如何...

A是很簡單的一題, B要想一會兒..我覺得B在於我來說有點運氣成分, 就是不一定每次都可以想到

C直接果斷只做了C-small...C-large有空再想吧, 應該很tricky?

現場來說, 只要做到A,BC-small, 基本就1000名內 = 升級了...

Google Code Jam 2015 Round 1A

題目: https://code.google.com/codejam/contest/4224486/dashboard#s=p0

A: (Math, Greedy)

一題直接的數學題...數據也不大, 能過小的基本也能過大的...

就是給了兩個方案, 各自Greedy地計算一個數字, 然後輸出就是了

唯一令我confuse了一會的是那個"rate", 我第一眼以為是以秒算的, 那麼不能整除的話

就要 ceil 了, 但從test case來看, 這個"rate"是每10秒計的...其實也很合理

#include<bits/stdc++.h>
using namespace std;

int T,t1,t2,n,a[1005],r;

int main(){
    scanf("%d", &T);
    for(int qwe=1; qwe <= T;qwe++){
        scanf("%d", &n);
        t1=t2=r=0;
        for(int i=0; i<n;i++) {
            scanf("%d", &a[i]);
            if(i) {
                r = max(r, a[i-1]-a[i]);
                if(a[i-1] > a[i]) t1 += a[i-1]-a[i];
            }
        }
        r = max(r,0);
        for(int i=0; i<n-1;i++) t2 += min(a[i], r);

        printf("Case #%d: %d %d\n", qwe,t1,t2);

    }
    return 0;
}

B: (Binary Search, Math)

這題能腦子一閃想到也算是運氣, 意思是Round 1B或C有這類題目, 我未必能想到

我直接就看大數據來想的, 但要是真的做不到large case, 應該small case有一些簡單暴試的方法

題目給了 B個髮型師 (|B| <= 1000), 每個髮型師要M_i (M_i <= 10^5) 的時間理髮

你是第N位客人 (N<= 10^9), 每一個客人會等到有任意有空的髮型師就找他理髮, 要是有數個有空的就找 ID 最小的髮型師, 問會是那一個髮型師為你理髮呢?

始且順住我的思路盡力寫下:
首先由於 N 太大, (這個N 是small / large case 都一樣的)

連 O(N)都過不了, 所以我估了數個可能的複雜度: O(B lg (N)) , O(B lg( max(M_i))) ...
於是思路就是以 |B| 為重點來開始想

"For 每一個B 做些什麼" 這樣子...好像也沒什麼想法

於是在紙上 visualize test case: 是這樣子的

這是第一個test case, 由於N = 4, 所以答案就是 B = 1

類似這樣的畫法, 另外2個test case也都畫出來了

一些 M_i 不能整除的也都亂畫了幾個

然後靈光一閃的位置到了...

我就這樣打直畫了一筆

然後開始想...這個是代表時間吧

在任意時間, 總共處理 (正在處理中的都算) 了多少位客人?

這個好像能知道的樣子

加上之前估算的複雜度, 一個字: Binary Search

然後開始細想:  最大的時間是多少? 直接想最惡劣的情形(對客人來說): 只有1個髮型師, 他還要用最久的時間處理一個人,  這樣最大的時間就是 10^9 * 10^5 = 10^14!

O(lg (10^14)) 足夠有餘!

而每一個時間, 怎樣算有多少客人已經處理?

設時間是 t ,  由於我們正在處理中的都算, 所以是 Ceil( t / m_i) 

總數就是 Sum (Ceil (t / m_i) ) , 這個可以用O(|B|) 算出

我們要找的是: 最少的時間令這個Sum >= N

這樣, O(B lg (N*max(M_i))) 感覺很像樣了

問題是, 現在我們有一個時間點了 (這個時間作為第N個客人, 你會被處理)

怎樣找出答案要求的髮型師 ID呢?

我的想法是: 把這個時間點再減 1 , 然後再算一下Sum (總共多少位客人在處理)

然後有以下的推論:

這個前一秒的Sum 肯定比我們以Binary Search找的小, 不然我們Binary Search 那一步就錯了 (contradiction)

那麼這一秒可以使Sum增加的原因是, 某些髮型師在這"前一秒"剛好完成手頭上的工作, 空出來了

把這2個Sum 的difference叫offset, 我們要找的髮型師就是 第 offset 個 剛好完成工作空出來的髮型師, 這些髮型師的特點是 : 他們的理髮時間 M_i 能夠整除我們Binary Search的時間-1秒

所以找第offset 個髮型師 (就是答案) 這一步還是可以O(|B|)找的...

算法也完成了

這題還是很有信心的...因為每一步都真的想得很通, 也很說服到自己再code的...

能一棍過太好了, 就是不知現場發揮有沒有這麼好= =

下面用%I64d 是因為我在Codeforces隨便submit再copy的, 我不會其它方法使code那麼好看了(排版上)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int T;
LL b,n,m[1005];
int main(){
    scanf("%d", &T);
    for(int qwe=1;qwe<=T;qwe++){
        scanf("%I64d%I64d", &b, &n);
        for(int i=0; i<b;i++) scanf("%I64d", &m[i]);

        LL lo = 0, hi = 100000000000005LL, mi, M;
        while(lo <= hi){
            mi = lo + (hi-lo)/2;
            LL sum = 0;
            for(int i=0; i<b;i++){
                sum += (LL)ceil(mi*1.0/m[i]);
            }

            if(sum >= n){ hi = mi-1; M = mi; }
            else lo = mi+1;
        }
        LL psum = 0;
        vector<int> idList;
        for(int i=0; i<b;i++){
            psum += (LL)ceil((M-1)*1.0/m[i]);
            if((M-1)%m[i] == 0) idList.push_back(i+1);
        }
        LL offset = n - psum;
        printf("Case #%d: %d\n", qwe, idList[offset-1]);
    }
    return 0;
}

C-Small: (Brute Force, Geometry)

就 Small來說, 的確比B簡單...

Large還沒想所以就不講了 (想到的話再講吧..= =)

題目是問, 給了 N 點, 求N 個數字, 第 i 個數字代表 最少要刪除多少點才能使第 i 點在convex hull 上面

Small Case 沒什麼好說的, 因為 N<=15, 直接地說是怎樣做都可以, 夠暴力就OK了

我的做法是最直接的 O(2^N  * N) 

實作時不想煩好像寫了 O(2^N * N^2) 的, 反正都能過就沒多想了..

Convex Hull 我用我唯一會的寫法: Monotone Chain

(有出cheat 參考網上寫法)

算法就是 bitwise地決定刪走那些點, 把剩下的點做一次Convex Hull, 

看看第 i 點在不在 hull 裡面...就這樣子

Convex Hull 是O(N)的, 因為sort 那一步可以放在 bitwise brute force外面

這題很好...順路幫助我記回基本的Convex Hull寫法

明天再來看看有沒有精力想 Large吧...

#include<bits/stdc++.h>
#define LL long long
using namespace std;

struct P{
    LL x,y;
    P(LL x, LL y): x(x), y(y){}
    P(){}
    P operator-(P a){
        return P(x-a.x, y-a.y);
    }
    double operator^(P a){
        return x*a.y - y*a.x;
    }
    void eat(){scanf("%I64d%I64d", &x, &y);}
}tree[20],control[20];

int T,n;
vector<P> hull;

bool ss(P a, P b){
    return (a.x < b.x) || (a.x==b.x && a.y < b.y);
}

double ccw(P o, P a, P b){
    return (a-o)^(b-o);
}

bool convexHull(int x, int s){
    vector<P> src;
    hull.clear();

    int m = 0;
    for(int i=0; i<n;i++)
        if(x & (1<<i)) src.push_back(tree[i]);

    for(int i=0; i<src.size(); i++){
        while(m >= 2 && ccw(hull[m-2], hull[m-1], src[i]) < 0){ hull.pop_back(); m--;}
        hull.push_back(src[i]); m++;
    }
    for(int i=src.size()-2, t=m+1; i>=0; i--){
        while(m >= t && ccw(hull[m-2], hull[m-1], src[i]) < 0){hull.pop_back(); m--;}
        hull.push_back(src[i]); m++;
    }

    for(int i=0; i<hull.size(); i++)
        if(hull[i].x == control[s].x && hull[i].y == control[s].y) return true;

    return false;

}

int main(){
    scanf("%d", &T);
    for(int qwe=1; qwe<=T;qwe++){
        scanf("%d", &n);
        for(int i=0; i<n;i++){ tree[i].eat(); control[i] = P(tree[i].x, tree[i].y);}
        sort(tree, tree+n, ss);
        printf("Case #%d:\n", qwe);
        if(n<=2){
            for(int i=0; i<n;i++) printf("0\n");
        }
        else{
            for(int s=0; s<n;s++){
                int ans = 1<<28;
                for(int i=0; i< (1<<n); i++){
                    if(i&(1<<s)==0) continue;
                    if(convexHull(i, s)){
                        int tmp=0;
                        for(int j=0; j<n; j++) tmp += !(i&(1<<j));
                        ans = min(ans, tmp);
                    }
                }
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

C-Large: (Geometry)

糾纏了幾日, 終於完成了這題

果然是C-Large, 基本上要是即場做的話還是會果斷放棄
算法倒也不算複雜, 但重溫/新學了一些做Geom的技巧 

思路是這樣的...還是先從數據量估算複雜度開始

O(n^2) 是絕對可行的, 但不太可能以n^2 完成...

然後發現O(n^2 lg(n)) 也非常足夠

把這個複雜度Bare in mind, 再想想實際上如何入手

最直接想到的是, 一點要成為convex hull上的一點, 以它跟左右兩個hull點連起來

這一點 "另外一邊"的所有點都要刪去

推而廣之, 一點跟任何另外一點連成一線, 以這條線為分界線

刪除線隨便一邊的點, 另一邊+線上的點就可以成為hull

這樣的話 把全部2點都連起來作分界線試一下, 每條線有2個可能性 (刪去隨便一面的點)

這步至少要O(n^2)

剩下的 O(lg n)...我懂的也只有Binary Search了

說起來, 這種情況下bsearch能起作用的:

假設我們有方法把點排序,  然後用bsearch找出一個連續的範圍, 裡面的點是都要刪去的

這樣的話問題就解決了...

high level 地說:

1. for 每一點 i ,  O(n)
1. 用某種次序把點排序 O(n lg n)
2. for 另一個點 j , i != j  O(n)
1. bsearch 要刪去的點的range O(lg n)
2. 比較2種可能性那種較好 O(1)

總算起來就是O(n^2 lg n)了..

問題是怎樣排序了, 點排序的話不是先x 後y,  就是sort by angle吧..以我認識來說=.=

這題是sort by angle! 可是我沒code過, 也不太了解實作上怎樣做

也不能直接用cross product去排序, 因為 >= 180度的有負數 / 0, 根本sort不了

經Peter神提點, 原來大家都是用atan2()這個function來算角度再sort的...

所以所謂sort by angle (以某點為origin)  就是先O(n) 用atan2() 算一下角度

如果是負數的話要加 2*PI  把角度變回正數, 這樣atan2()的range是 [0, 2*PI)

Sort完後再來想是不是能利用來bsearch了

假設現在是用點 i 作origin, 我們要找最少要刪多少點才能使 點 i 在hull上
那麼 點i 連到點 j 的線, 角度是 angle (j)

但還有另一邊, 另一邊的角度是 angle(j) - PI, 如果是負數的話也一樣加上2*PI

現在有2個角度, 我們分一下大小,  所以我們有了一個range, 這個range 剛好是 PI 度 (一條直線)
我們可以bsearch 在這個range內的點,  要小心的是不包括在線上的點

假設我們bsearch了在這個range內的點是  s, 我們就可以比較2種可能性了:
把這s 個點刪去,  代表 剩下的點作一個hull (點 i 是origin, 肯定在線上=hull上)

或是把 n - s - 線上的點 刪去, 代表用這s點和線上的點作hull (點 i 是origin, 肯定在線上=hull上)

這樣以點 i 作origin, 把所有點 j 的2種可能性都比較完就能知點答案

for 每一個點\i 都這樣做 就好了

然後當然還是WA了, 搞了很久還是不知道為什麼
終於發現原來是精度問題, 太久沒做連精度問題都忘了怎樣處理

找了small case的一個test case試, 發現 在1e-7的位置會出現問題

所以先設eps 為 1e-7, 然後sorting 和bsearch時 (總之要比較2個double的時候)
便要考慮eps:

feq(x,y)  :=  fabs((x)-(y)) <= eps
flt (x,y) :=  ((x)+eps) < (y)

fle(x,y) := ((x)+eps) <= (y)

我大約記得是這樣吧, 也不太肯定, 總之這樣之後就AC了...

然後實作上首先是:
bsearch是如果是用內置的lower_bound / upper_bound

跟sort 一樣, 可以自己寫個bool 的 comp function, 我這次也寫了一個, 裡面就是用上面的flt / feq 等去比較

另外聽GG說好像有不用double的sort法, 就沒有精度問題

方向大概是是找出180度的點. 以它為pivot 把點分成 < 180度和 > 180度

然後2種點內各自用cross product sort
感覺像是 quick sort 那種先fix 死一個pivot 再分2邊處理那樣

可以學習一下

後記:  MS 那邊那個比賽這兩天也進行了 Round 1A / B, 打得很差, 但還是有一題值得記下的, 其實問題很有學習價值, 但平台太差, 沒有practice, 也不能賽後submit, 也沒有solution / editorial....真的很令人生氣, 看看把那唯一值得記下(AC)了的一題怎樣歸類在另外開文寫吧..