Google Code Jam 2015 Round 1C

終於有心情打最後一篇今年的GCJ文

話說幾經辛苦把這場的solution都看完再把題目都AC之後

發現這場真的遺憾 還記得只要我做到 C-Small 就能Advance了

而C-Small (甚至C-Large) 在看完solution後驚覺是很易的...是應該能做到的

這兒學習到一件事, 要正視自己一直以來其中一個思考的弱點..下面再說

至於B-Large 是絕對不可惜, 甚至我也是在昨天才勉強明白solution的方法

只能說我的Probability / Expected Value學得太差了...

總結來說, 這場比1B學得更多, Ad-hoc度雖然也很高, 但仍然是有學習的地方

即場時我AC了 整題的A跟B-Small, 其它都是事後再AC的

玩了3場的GCJ Round 1, 我認為心理跟策略上也是有改善的空間

Google Code Jam 2015 Round 1C

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

A: (Ad-hoc, Greedy)

這題是我唯一能整題過的題目...

就結果來說, 其實Small的思路跟Large的是完全一樣

但即場由於策略問題, 完全沒多加思考Large 就跑去看B跟C了...

弄得同一樣的Code, 卻過了一小時才交A-Large...

題目本身很易嗎? 也不算, 也不是難...是很伏

很明顯很容易想少一些Case的類型

題目是這樣的:

給了一個R*C的Grid, 你跟你弟弟要玩一個遊戲.

你弟弟會放一隻 1*x  (打橫長x格) 的船在任意位置

你要做的就是猜船的位置, 並且把他打沉 (你看不到船的位置)

打沉的方法是: 把船的 x 格佔有位置都說出來

問題是你知道弟弟會出cheat, 他可以任意移動船的位置, 

只要跟你所知道的情報沒有矛盾就可以了

例如: 你說了某一格的位置, 弟弟可以先把船移動, 然後跟你說"沒有中"

當然, 當某一格他說了沒有中 (或中了) 之後, 那一個的狀態就不能再改變了

不然就跟你所知的情報有矛盾了

問題問, 你先走, 在知道弟弟會盡可能地出cheat的情況下, 你最少要用多少步才能勝出?

Small Case是Large的引導版, 是只有一個Row的 (R*C, R = 1)

我是先把想法大概猜到了, 才開始做個簡單的證明的

思路大約是: 由於最少都要用X做答案, 每次弟弟出Cheat會把答案的次數增大1

所以盡量減少他可以出Cheat的次數...對這個是可以控制到的, 因為他不能與我所得的情報相矛盾

怎樣可以限制弟弟出Cheat的次數呢? 不難聯想到跟Greedy有點關係

"盡可能"選擇某些位置使他不能出很多次Cheat這樣

答案就是: 由左至右, 每次選第 x 格

如果弟弟說了"中"的話, 基本最多再選 x 次就完結了 (為什麼不是x - 1次是伏位, 下面再說)

但弟弟這樣說沒好處, 如果他還能出Cheat的話

但他要再出Cheat, 就只能把船向右移了 (如果本身是選中了的話)

那麼我就再一次選向右的第x格...如此類推

那麼弟弟已經走投無路, 所有左邊的位置都比我"封鎖"了

他被迫要說"中了"

那麼我們就限定了那一格是船的某一部分

但伏位是...很自然會以為那格是船的 "最右點"

但這未必是真的,  要是 C 本身不能被X整除, 那麼其實右邊還有空間再移動

只是不夠整架船移動 (再出Cheat)

所以要是你用x - 2 步把船的 x - 2格都猜中了

第 x - 1 步, 弟弟永遠都可以說你錯了, 他可以出最後一次Cheat把船向相反方向移動一格

浪費你多一步 所以要是 C本身不能被 X 整除的話, 答案還要另外 + 1

這基本就是Small的答案了

而Large呢, 首先發現, 每一Row都是獨立的, 可以分開來看

Greedy地選也完全沒問題

所以就把這個策略重複 R-1 次, 最後一個Row就當是Small一樣的做法就好了...

策略上...我應該先花幾花鐘想想Small是否能改一下就能交Large的...

這題根本不用花一小時再交...

#include<bits/stdc++.h>

#define LL long long

#define PI acos(-1)

#define x first

#define y second

#define PII pair<int,int>

#define F(x,y,z) for(int (x)=(y);(x)<(z);(x)++)

#define pb push_back

#define mp make_pair

#define eps 1e-7

#define feq(x,y) (fabs((x)-(y)) <= eps)

#define flt(x,y) ((x)+eps < (y))

#define fle(x,y) ((x)+eps <= (y))

#define fgt(x,y) ((x) > (y)+eps)

#define fge(x,y) ((x) >= (y)+eps)

using namespace std;

int T,n,r,c,w,ans;

int main(){

    scanf("%d", &T);

    for(int qwe=1; qwe<=T;qwe++){

        scanf("%d%d%d", &r,&c,&w);

        ans = (r-1)*(c/w);

        ans += (c - w)/w + w + (c%w != 0);

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

    }

    return 0;

}

B: (String, Probability, Expected Value)

這題是這一Round最難的了 (如果考慮Large的話)

這題有我最苦手的Probability / Expected Value的問題...

幸好結果來說我有學到東西了...

題目有點複雜就不說了 直接說分析

Small是很簡單的Brute Force, 隨便寫Backtrack都可以

Large就需要數學技巧了...

首先題目有點賤

題目要找的是: Expected Number Of Banana Left 

首先我來說一下我對Expected Number 的理解:

很白痴, 我只懂最簡單的definition: Weighted Average of Possible Result

也就是 E(X) = P(a)*v(a) + P(b) * v(v) + ...
where P() 跟 v() 是 probability 跟 Value of 所有Possible outcomes

然後因為之前某場CF, 我也得知了一個經常會用到的Property叫
Linearity of Expectation

這個是這條題目的重點, 是很方便很強大的Property, 可惜我對他的理解等於零

在CF上面厚顏地開了Post求問, 有人給了一些很好的Reference, 看了之後才開始有點理解
http://codeforces.com/blog/entry/18025#comment-228851

這個Property, 引用Wiki的說法: 

即使 X , Y 是 dependent 的Random Variable!!

先不詳細說這個東西, 回到題目上面

設 C為你會準備的Maximum # of bananas, 

那麼題目就是求 E(X) = E(C - X)  = C - E(X)  where X  = expected # of bananas give out

那麼題目就分兩部分了: 找出C跟找出E(X)

先說找 C

首先跟KMP一樣, 要先找出Pattern 的"最長前後綴"
由於string很短, 不用failure function找也可以...直接substring()找就行了...

有了這個之後..就可以直接用String的長度 S
去算出所有可能性裡面包括最多Pattern的String究竟有多少個Pattern

是為C

重點還是要在算E(X)上面吧

首先說一下不懂答案思路之前的想法:

跟上面說的一樣, 我只會最基本的Definition

所以很自然就會去想 

E(X) = P(Exact 1 banana)*1 + P(Exact 2 bananas)*2 + ...

(詳情我CF那個Post有說, 可以自己去看)

但當然這樣算沒有好處, exact X banana這些event 明顯就不是independent的

無限double count, 也不知道怎用 (知道也不會用, 想也知難code) inclusion-exclusion principle

總之直感也知道不是這樣直接去數的, 用Counting之類的數法是不行的了

然後...答案竟然是很直接的...

設P 為 Pattern在某一個位置出現的機率, 這個易算, 直接用Product Rule乘起來就是了

然後重點是:

By Linearity Of Expectation, E(X) = P*(S-L+1) As there are (S-L+1) possible starting point for Pattern

這句是如何來的...!?

看了CF那個Post後...我終於有了以下的理解 (還不知道對不對, 最少我信了)

先說一下Random Variable

它們只是一些有不同值的Variable, 每個值都associate 一個probability, 當然加起來就是 1

視乎情況, 這些值可以自己define出來的, 最常見的就是 1 跟 0 (某些desire result就設1, with some probability P, otherwise 0 with (1-P))

由於他們是variable, 可以照樣自己設立一些equation

例如設 Z 為 # of bananas giving out, 我不知道Z 的所有Value跟它們的probability 

但照樣可以寫一個equation

Z = A_1 + A_2 + A_3...
A_i 是 # of banana when pattern start at position n

A_i 我們倒是知道的, 沒錯就是最常用的 {1 with some probability p, 0 otherwise}

這個 some probability p 就是solution中算的 P, 所有A_i 的 p 都是一樣的

現在不難發現A_i 互相也不是independent 的!

在某一個位置假設出現了pattern, 某些位置就不可能出現了...

這就是Linearity Of Expectation 發光的地方了!

即使 X , Y 是 dependent 的Random Variable!!

Z = A_1 + A_2 + A_3...

==>

E(Z) = E(A_1 + A_2 + ...) = E(A_1) + E(A_2) + ...

= P*1 + P*1 + ...

= P*(S-L+1)

嗚啊...即使不是Independent也還是可以直接這樣做, So 變態...

這個技巧不用真的很熟悉Probability...也可以照學起來吧, 思路而已...

這題做不到真的不可惜, 因為回頭看根本不是能做到的東東

還有要知道: 不恥下問真的很重要, CF真的是很好的平台 :)

PS: 最後糾結的是...比較 P 跟 0的時候 不知道為什麼不能用eps, 不是應該要用才對嗎? 用了反而會錯, sample case都過不了...eps這個東東也是要認真面對一下了

#include<bits/stdc++.h>

using namespace std;

int T, L,S,K;

int alphabet[300];

string kb, pat;

int main(){

    scanf("%d", &T);

    for(int qwe=1; qwe <= T; qwe++){

        scanf("%d%d%d", &K,&L,&S);

        cin>>kb>>pat;

        memset(alphabet,0,sizeof(alphabet));

        for(int i=0; i<K; i++) alphabet[kb[i]]++;

        // O = maximum overlap

        int O = 0;

        double maxBanana = 0, expectedBanana = 0, P_fixedPoint = 1;

        for(int i=0; i<L;i++) P_fixedPoint *= (alphabet[pat[i]]*1.0/K);

        if(P_fixedPoint > 0){

            for(int i=1; i<L; i++) if(pat.substr(0,i) == pat.substr(L-i)) O = i;

            maxBanana = 1.0 + (S-L)/(L-O);

            expectedBanana = P_fixedPoint * (S-L+1);

        }

        printf("Case #%d: %.8f\n", qwe, maxBanana - expectedBanana);

    }

    return 0;

}

C: (Ad-hoc, Greedy)

這題真的太太太可惜了...回頭看真的應該要做到的..

題目是說:

給了 D 種錢幣, 每種錢幣可以用C個, 現在要你合出 [1, V] 所有的value

當然有機會合不了, 所以你可以額外增加某一些種類的錢幣, 當然它們也只能用C個

問最少要另外增加多少種類的錢幣?

這兒我的思路, 一下子就飛去 Coin Change的 Classic DP去了

這個就是我開首說的壞習慣...

由Day 1 開始玩比賽到現在, 我每次看到題目有一點點像我聽過的Classic Problem
就會往那方向去想, 以為是一些簡單變種還是什麼

但其實by experience, 很多時候都是錯的...

有時候, 根本不用想那麼複雜(像這題)

有時候, 有一點點像, 但其實差很多很多 (特別是Graph類的題目)

總之這樣的"聯想式"的思考好像不太有效呢...很多時把自己帶進死胡同

這題結果也是這樣的, 其實跟Coin Change沒有關係...(當然如果會的話會有幫助)

整道題目只考你一個發現:

能合到的value像一條條segment, 是有range的

例如你不增加種類, 可能合到 [1,5], [10,12]....

這樣的話 其實 "6" 是一定要增加的了, 因為用現在所有種類都合不出來, 

也不可能用比6 大的種類合出來, 對吧?

這樣的話就是Greedy的想法了

我們想 maintain X, where X 是 最少的value such that [1,X] 都是你能合出來的

那麼X+1怎樣合出來呢?

可以試用 現在的種類(如果有還沒用的話)試試合不合到

不能的話只能增加合成種類

當X >= V 的時候 算法就完成了

When we add a new denomination X to S, the new set of values we could produce include each of the values we could produce with the existing set S plus between 0 and C of the new denomination X. If X is at most N+1, then this new set of values will be the set of all values from 0 to N+X*C, so we can update N to N+X*C.

這段借用solution的解說, 說明了增加/ 使用某一種類的錢幣時, 可以很簡單直接地update X (solution的notation跟我用的有不用, 注意一下)

由於只有D種現有錢幣, 而增加種類即使 X 變為 X+C*(X+1) = X(C+1) +C

C最少是 1 , 所以 X 最少是2倍2倍地增長, 直到 V, 最多就是O(lg V) 次

TOTAL = O(D + lg V) 的LOOP

這樣的分析..跟Facebook Hacker Cup 某題有點像, 也是不用嚴格地分析, 只要證明了

最少是2倍2倍地增加/減少, 就可以得出 O(lg X)的bound, 用來說服自己很有用

說起來, 這題的難度全部在於發現如何update X, 分析複雜度

至於Greedy地增加種類..是很直接的, 當時我是這樣猜, 但不能很系統地說服自己Greedy是正確的, 結果根本就是很明顯嘛...

int T,n,c,d,v,ans;

LL up, used, D[105];

int main(){

    scanf("%d", &T);

    for(int qwe=1; qwe<=T;qwe++){

        used = up = ans = 0;

        scanf("%d%d%d", &c,&d,&v);

        F(i,0,d) scanf("%lld", &D[i]);

        sort(D,D+d);

        while(up < v){

            LL X = up+1;

            if(used < d && D[used] <= X){

                up+= c*D[used++];

            }

            else{

                up += c*X; ans++;

            }

        }

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

    }

    return 0;

}

終於終於 都把GCJ Round 1 的東東都搞完了...

剩下的就是String的文章, 還有Kattis那邊的"Lecture"吧?

String也是我拖太久 看到題B要用到的時候我已經打了自己兩巴 ...

(雖然根本重點在Expected Value)

GCJ, 下年再見吧 :/