2015年4月19日 星期日

2015 Google Code Jam Round 1A

官方題目、比賽網站（可下載練習用測資並judge）

Problem A. Mushroom Monster 這題其實很簡單，但是題目敘述讓人很難理解，尤其對於非英文母語使用者而言，真正的功夫都花在理解題意。
我現在重新簡要的闡述題意：
有兩個人，第一個人會任意的在盤子中放置蘑菇、第二個人會吃掉蘑菇；
給你\(N\)個時間點（每個時間點之間間隔一樣久）盤子中的蘑菇數量，請計算第二個人至少吃了幾個蘑菇。
第二個人有兩種吃蘑菇的策略，分別如下：
1. 他在任意時間吃掉任意數量的蘑菇。
2. 只要盤子裡還有蘑菇，他就會以固定的速度吃蘑菇；否則，他就會暫停吃蘑菇。
請分別針對這兩種策略計算他至少吃了幾個蘑菇。


有幾個點導致題意難以理解：
1. （我自己一開始）以為那\(N\)個數字是被加進來的蘑菇數量，所以完全不理解。
2. （在FB看到其他人反應）題目中特別點到那\(N\)個時間點間隔\(10\)秒，讓他們以為第二個人吃的速度必須是每秒整數個。


不過，一旦理解了題意，這題就迎刃而解了！
對於第一種策略：
沒什麼特別的，只有盤子中蘑菇數量減少時，當做那減少的量被他吃掉了。
而第二種策略：
找出盤子中蘑菇數量減少最多的一次，當做他吃蘑菇的速度，
然後從頭到尾掃過去計算他吃了多少。
（注意盤子蘑菇不夠時就不會吃了）
時間複雜度：\(O(N)\)
AC code 
 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
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

int m[10000],N;

int main()
{
    int NumberOfTestcases;
    scanf("%d",&NumberOfTestcases);
    for(int CaseNumber=1;CaseNumber<=NumberOfTestcases;CaseNumber++)
    {
        printf("Case #%d: ",CaseNumber);
        scanf("%d",&N);
        for(int i=0;i<N;i++)
            scanf("%d",m+i);
        int ans1=0,ans2=0,big=0;
        for(int i=1;i<N;i++)
            ans1+=max(0,m[i-1]-m[i]);
        for(int i=1;i<N;i++)
            big=max(big,m[i-1]-m[i]);
        for(int i=0;i<N-1;i++)
            ans2+=min(big,m[i]);
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}


Problem B. Haircut 一家時尚髮廊中有\(B\)個理髮師，編號\(1\)到\(B\)，其中編號\(k\)的理髮師會花費\(M_k\)的時間幫一個顧客理髮。
對於每個顧客，一旦有空閒的理髮師時，他就會由編號最小（而不是花費時間最少）的理髮師負責理髮。
請問第\(N\)位顧客會由編號多少的理髮師負責？
（\(1\leq{N}\leq10^9,1\leq{B}\leq10^3,1\leq{M}_k\leq10^5\)）


因為\(N\)很大，所以一定要把它從複雜度當中壓掉。
正確的策略：
先利用二分搜計算第\(N\)個顧客開始剪頭髮的時間，（對於每個時間，可以\(O(B)\)判斷是否剪到頭髮）
然後算出他是那個時間點的第\(x\)位顧客，找到第\(x\)位在這個時間點完成前一項工作的理髮師即可。
時間複雜度：\(O(B\ log(N\times{M}_k))\)
AC code 
 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
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

int M[10000],B,N;

ll count(ll t) // count the number of customers with started cut(include)
{
    if(t<0)
        return 0ll;
    ll re=0;
    for(int i=1;i<=B;i++)
        re+=t/M[i]+1;
    return re;
}

int main()
{
    int NumberOfTestcases;
    scanf("%d",&NumberOfTestcases);
    for(int CaseNumber=1;CaseNumber<=NumberOfTestcases;CaseNumber++)
    {
        scanf("%d%d",&B,&N);
        for(int i=1;i<=B;i++)
            scanf("%d",M+i);
        ll l=0,r=(ll)1e15,m;
        while(l<=r)
        {
            m=(l+r)/2;
            if(count(m)<N)
                l=m+1;
            else
                r=m-1;
        }
        // target starts cut at time "l"
        printf("Case #%d: ",CaseNumber);
        int tmp=count(l-1);
        for(int i=1;i<=B;i++)
        {
            if(l%M[i]==0)
            {
                tmp++;
                if(tmp==N)
                {
                    printf("%d\n",i);
                    break;
                }
            }
        }
    }
    return 0;
}


Problem C. Logging 給你平面上的\(N\)個相異點，請對每個點回答：至少需要去除幾個點，才能使這個點在所有點構成的凸包上（含邊界）。

這題特殊的是他的範圍：
Small是\(T\leq100,N\leq15\)
Large是\(T\leq14,N\leq3000\)

Large的\(T\)縮小了，這顯然就暗示我們：複雜度會卡在邊緣！

先講Small，只要\(2^N\)枚舉所有點的子集之後做凸包即可！（注意要保留線上的點）
總時間複雜度：\(O(N\times2^N)\)
寫得有點亂不過至少能過Small的code 
 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
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

struct PT{
    int x,y,id;
    PT(int _x=0,int _y=0): x(_x),y(_y) {}
    PT operator -(const PT&b)const
    {
        return PT(x-b.x,y-b.y);
    }
    ll operator %(const PT&b)const // cross
    {
        return 1ll*x*b.y-1ll*y*b.x;
    }
    bool operator < (const PT&b)const
    {
        if(x!=b.x)
            return x<b.x;
        return y<b.y;
    }
}dot[100];

int ans[100];
int N;

vector<PT> use;
PT tmp[100],st[100];
int top;

void check()
{
    int num=0;
    for(PT x:use)
        tmp[num++]=x;
    assert(num==SZ(use));
    std::sort(tmp,tmp+num);
    top=-1;
    for(int i=0;i<num;i++)
    {
        while(top>=1 && ((st[top]-st[top-1])%(tmp[i]-st[top]))<0)
            top--;
        st[++top]=tmp[i];
    }
    for(int i=0;i<=top;i++)
        ans[st[i].id]=min(ans[st[i].id],N-num);
    top=-1;
    for(int i=num-1;i>=0;i--)
    {
        while(top>=1 && ((st[top]-st[top-1])%(tmp[i]-st[top]))<0)
            top--;
        st[++top]=tmp[i];
    }
    for(int i=0;i<=top;i++)
        ans[st[i].id]=min(ans[st[i].id],N-num);
}

void run(int l)
{
    if(l==N)
    {
        check();
        return;
    }
    run(l+1);
    use.pb(dot[l]);
    run(l+1);
    use.pop_back();
}

int main()
{
    int NumberOfTestcases;
    scanf("%d",&NumberOfTestcases);
    for(int CaseNumber=1;CaseNumber<=NumberOfTestcases;CaseNumber++)
    {
        scanf("%d",&N);
        for(int i=0;i<N;i++)
            scanf("%d%d",&dot[i].x,&dot[i].y),dot[i].id=i;
        fill(ans,ans+N,123456);
        use.clear();
        run(0);
        printf("Case #%d:\n",CaseNumber);
        for(int i=0;i<N;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}

至於Large：
對於每個被詢問的點\(A\)，我們嘗試對每個不為\(A\)的點\(B\)計算線段\(AB\)為凸包上的邊時，需要砍掉多少點。
若認定線段有方向性，那麼這部分可以簡化成尋找一個點\(C\)滿足有向角\(AB\)到\(AC\)不小於\(\pi\)，並最小化期間的點數。
那麼，只要以\(A\)為中心將其他的點做極角排序，上面這個步驟就可以用類似sliding window的方法快速解決！
時間複雜度：\(O(N^2logN)\)
把題目的範圍帶進去算，應該就不難理解為何會是\(T\leq14\)了。
我的ACcode 
 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
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

struct PT{
    int x,y,id;
    PT(int _x=0,int _y=0): x(_x),y(_y) {}
    PT operator -(const PT&b)const
    {
        return PT(x-b.x,y-b.y);
    }
    ll operator %(const PT&b)const // cross
    {
        return 1ll*x*b.y-1ll*y*b.x;
    }
    ll operator *(const PT&b)const // dot
    {
        return 1ll*x*b.x+1ll*y*b.y;
    }
    ll len2()const
    {
        return x*x+y*y;
    }
}dot[30000];

int N;
const PT stu=PT(1,0);
bool cmp(const PT &pa,const PT &pb)
{
    if(stu%pa>0 && stu%pb<0)
        return 1;
    if(stu%pa<0 && stu%pb>0)
        return 0;
    if(stu%pa==0 && stu*pa>0)
    {
        if(!(stu%pb==0 && stu*pb>0))
            return 1;
        return stu*pa<stu*pb;
    }
    if(stu%pb==0 && stu*pb>0)
        return 0;
    if(pa%pb!=0)
        return pa%pb>0;
    return pa.len2()<pb.len2();
}

vector<PT> use;

int main()
{
    int NumberOfTestcases;
    scanf("%d",&NumberOfTestcases);
    for(int CaseNumber=1;CaseNumber<=NumberOfTestcases;CaseNumber++)
    {
        scanf("%d",&N);
        for(int i=0;i<N;i++)
            scanf("%d%d",&dot[i].x,&dot[i].y),dot[i].id=i;
        printf("Case #%d:\n",CaseNumber);
        if(N==1)
        {
            puts("0");
            continue;
        }
        for(int i=0;i<N;i++)
        {
            int ans=123456;
            use.clear();
            for(int j=0;j<N;j++)
            {
                if(j==i)
                    continue;
                use.pb(dot[j]-dot[i]);
            }
            sort(use.begin(),use.end(),cmp);
            assert(SZ(use)==N-1);
            for(int i=0;i<N-1;i++)
                use.pb(use[i]);
            int l=0,r=0;
            for(;l<N-1;l++)
            {
                if(r<=l)
                    r=l+1;
                while(r<l+N-1 && (use[l]%use[r]>0 || (use[l]%use[r]==0 && use[l]*use[r]>0 && use[l].len2()<use[r].len2()) ))
                    r++;
                ans=min(ans,r-l-1);
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}
這份code跑Large測資跑了大概\(27\)秒，大概是因為比較的部份我弄得太複雜，常數很大。
賽後下載別人的解法，發現大部分人都用了atan2()來做極角排序，精度是夠的！
甚至dreamoon直接把atan2()的值排序然後找差值，根本沒有保留向量一起排序；
此外，他把所有極角\(+2\pi\)複製一遍並且嘗試最大化不用刪除的點，實作上比較直觀，也比較沒有奇怪的細節！
他的code我下載下來只跑了\(9\)秒，比我的code快了約\(3\)倍！！！



GCJid: jo4
這場比賽以100分 2:34:52的成績排到第305名！

A,B都解得算順利，花費的思考時間不算太長。
C就很驚險了，想了很久，決定先暴搜拿下Small，然而不想重寫凸包而使用過去的code片段的下場就是：
因為變數名稱沒改好而WA了兩次！
之後在床上思考Large，突然靈機一動想到作法爬起來寫！

倒數8~9分的時候才寫完Large，然後拿Small測...有bug!
還沒找到bug，但是發現離結束不到8分鐘，就乾脆先下載Large了XD
然後邊跑Large邊找bug，跑完先上傳...(知道這個一定會WA)
-
過不了多久，就很幸運的找到bug，原來只是個\(N=1\)的special case!
於是修完就先重傳Large~
然後拿3筆Small測，都對了 :D
就相信Large會過，等比賽結束...
最後上傳Large那時候已經只剩3分8秒了OAO
----
我在GCJ從來沒有破台過...包含qualification @@
還好C沒有別的bug，自認計算幾何很弱...
張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)