Codeforces Education Round 1

經過N個月, 公司的Project 終於見到尾聲...趁住扮工時間的空閑, 隨便找了一下CF的比賽來玩

很久之前看到CF推出的Education Round 系列已經感到興趣, 決定玩下 Round 1

看名字覺得是for 新手學習用, 所以很想玩, 但竟然...此Round 無Editorial...

究竟無Editorial 點樣可以Educate到人呢 ?

Anyway 這場有A-F共6題, 難度我覺得也是D2至D1尾吧? 最後AC了5題, 最後一題有點想法但Code不出來

要說學習了什麼, 倒不如說溫故知新, 特別是問了Peter神及GG 一些埋藏多年的白痴問題

Codeforces Education Round 1

題目: http://www.codeforces.com/contest/598/problems

A: (Math)

題目就不詳說了。
數據很小, 題目也很直觀, 基本有bitwise operation的底子可以直接code出來。
要是沒有的話其實暴試, repeat squaring之類的 怎樣也能AC。

B: (String, Ad-hoc, STL)

這題是Given 一條 string S, 然後 有一堆range query [l_i, r_i] 及T , 代表在這個range (inclusive) 內的substring 要向右rotate (shift ) T 次.

老實說這條應該是想最久的吧...因為比題目結構嚇倒了, 直接想到什麼range query什麼segment tree都出來了。

結果第二天扮工時間再看題目, 發現數據根本很小, 直接暴力做就可以了...

當然T 可以很大, 但由於 rotate 多過range的長度等於重置一次, 直接T%L (L = r_i - l_i + 1) 就好了。

我是用最慢但應該最易看的白痴寫法: C++的 STL, substr() 了很多次, 左拆右拆的, 一樣能AC。

只是看了Peter神跟 Gary神的 Code, 他們都不需要用C++的東西, 有點慚愧...

D: (Graph: DFS)

容我先跳過C, 因為題C數據上是最少人AC的, 我也最後才做, 也是相對學習得較多的一題。

題目很有趣, Given 一個2D Grid,  每格可以是路, 可以是牆。 如果是牆的話上面會有名畫一張。 然後Given m 個起始位置, 問如果你由該位置開始一直行, 怎樣行都可以 (除了穿牆), 你總共能看到多少名畫。

這樣想吧, 其實連續起來的路是一個component, Grid入面就有數個disjoint 既 components, 每個component入面不論那點作為開始, 看到的數量也是一樣的。

每個component 就像是圍棋內的一塊棋, 他們的「氣」就是名畫的數量

扯遠了...其實沒什麼關係XD

所以做法很簡單, 直接DFS, 把每個位置都歸入某個component內, 順便計算該component能看到的名畫數量。如果某點已經知道屬於那個component, 那便不用再花時間DFS了, 直接output 答案便可。 每個格子能看到的名畫數量可以在DFS前先計算好。

思路不難想, 算是鬥快寫DFS吧?

AC Code: http://www.codeforces.com/contest/598/submission/18879479

E: (DP)

這題老實說, 對我來講算是開始有難度了...雖然我知還是很簡單的題目。

題目是這樣的:  有朱古力一條, 有N*M 格,  現在你可以拆斷它, 但一定要直線或橫線, 整數地拆。每拆一次 cost 為該線的square, 問如果你想要exactly k 格朱古力, 最少cost 的拆法要多少

這類題目我有陰影, 總是想起從前有條POJ 好像叫Stick的題目, 當年覺得完全沒有思路, 不可能做得出, 然後Leo好像淡淡說了句: 呢條唔係Search ja咩? 

自那時起我都以為Search是一類特別的題目Category...
其實到現在也不太清楚他講乜春, 但這條的確是Searching, 雖然實作上是用DP做啦 (可以這樣說吧?)

數據很小, 其實也明顯是要你直接用DP做的了, 數據小到DP的方法也很直接

DP(N, M, K) :=  Minimum Cost to get K chocolates out of N*M one

DP(N, M, K)  = Min ( DP(N_1, M, K_1) + DP(N_2, M, K_2) + M*M,   DP(N, M_1, K_1) + DP(N, M_2, K_2) + N*N) for all N_1+N_2 = N, M_1+M_2 = M, K_1+K_2 = K

說白了, 就是每條邊, 和K的每種可能性 (K=4的話, 左邊0粒, 右邊4粒 / 左邊1粒, 右邊3粒...)都試掉, 看那種最優。

Code是不難寫的, base case小心點處理就好了。我是用Top-Down的寫法, Peter 神是用Bottom-Up的, 分別也不太大。

唯一WA了一棍...是被白痴位陰掉了...他有很大量的Query數目...但其實DP State pre-compute一次就行了, 第一棍把DP 放進 Input Query 的loop 裡了, 吃了TLE。

要說這條的學習, 我總是在想要是數據再大一點, 不能直接DP時, 會不會有其它做法, 這個還未有答案。

另外就是我對於分析這種Recursion + Memorization 的Complexity 很弱, 完全不知怎樣分析, master theorem好像也不能apply, 當然靠經驗感覺我知道肯定不會TLE, 但從來不知道正確及General的分析方法, 究竟是Big-O of 什麼。

有關這個, 我在Stack Overflow上問了一下, 好像也沒什麼特別的答案
http://stackoverflow.com/questions/38215549/how-to-analysis-the-time-complexity-of-this-code/38240874?noredirect=1#comment63937690_38240874

倒是Peter神的想法是把DP state的tree 做一次DFS, 所以是O(|V|+|E|), 然後看題目決定|V|和|E|是什麼, 這個想法當然好, 但我不肯定是不是General所有DP 的solution都可以這樣想, anyway仿然要#Adore#一下

C: (Geom)

最後解到的這題, 只有63個人AC了的這題, 其實不難理解。

題目本身不算難...但是一碰到Geom, 就一定會弄到精度問題, WA也不為過 

我沒有為自己WA了 13棍而開脫。

好吧先說題目 :)

題目是Given 10^5 個 vector, 全部連住Origin的。問那兩支vector的角是最小的, 這裡說的角沒有方向, 總之是該兩支vector的+角或-角magnitude 最小的 就ok。可以print出任何答案。

話說這樣的數據量, 基本上是要O( N lg(N) )的了, 看完題目基本就是Sort by Angle了吧

印象中Sort by Angle有兩種方法做, 但我只記得一種: 用atan2() 來sort.

當然n年沒有code過 geom題目的我, 一定要google atan2的用法...那些就不說了 :(

題解就是sort 完, 然後每一支vector跟前一支 (或後一支) 計一下角度, 然後找最minimum 那一pair 就好了 (最minimum 那一pair 在sort 完後一定是相鄰的, 對吧?) 

小心最後一支也要跟第一支比較。

問題來了, 一直WA一直WA, 完全不知錯在那裡。看完TEST CASE更加相信是精度問題...

所以這題的99%難度在精度問題。 以往我只知道要用eps, 但怎樣用, 為何要這樣用我也忘光了。所以我發射飛彈, 試了eps 由  e-6 開始到e-18 都試過了, 全部都WA....

終於最後, 忍不住, 隨手打開第一名那個的Code看...根本與我沒分別...唯一的分別, 在於他是用long double, 我是用double!!!!

我改完之後, 果然AC了.....!

究竟何時要用long double, 何時要用double? 我也不知道, 這是一個謎...

另外之後我問了GG, 究竟何時要用eps,  現在有一個更好的concept了....

原來eps的原意是比較2個double variable是否一樣, 而當你想 differentiate 它們的時候, 就要用上eps 來比較 ( <= 或 >= ). 在這題中用不上, 因為我們只考慮角度, 有些題目可能也要考慮長度, 那麼可能就有分別了 (sort by 角度, 角度一樣不等於"一樣")

而eps 通常是set e-8, 是-8,  至於為什麼, 連GG也說不知道 =.=


F: (Geom?)(最後一題的思路有時間後補吧...)

回到家打果然比在公司偷偷打要好得多。

這題的題目光用看的也感受到變態程度, 直到現在更只有 2個人AC...

題目大意是Given 一個 N-Side polygon, 可以Concave, Input格式為N 點, 點可以同線。
然後Given 一堆query, 每個query 是一條線, (可能) intercept with this polygon.
問, 在這條線在polygon 內的總長度是多少?

好吧我的確沒什麼完整的思路, 但腦海中立即出現的是當年CSC326 學的 Ray-Casting Algorithm (好像是叫這名字?)

好像是Given一點, 向住某一條線"射"出去, 看看穿過多少條polygon的邊。按照單雙數, 可以得知該點是否在Polygon內。

或許當中有某些思路可以apply? 沒什麼方向。 結論是為何Education Round沒有Editorial??

---

PS (Bonus)

雖然很慢, 但有感覺自己一直在進步, 可能一些以前沒有學懂的現在都會主動去學而且大約都能學會。但實在是不夠時間用, 在教會也開始要幫忙作鼓手跟導師, 工作上也愈來愈忙 (雖然快將轉工了應該), 加上要做Gym還有一大堆聚會要去, 有種感覺是一天24小時真的太少了....

另外之前在FB 路過看到一條好像是數學Olympic的題目, 對於0數學底的我, 也有些想法, 跟Peter神討論了一下, 可惜還是沒有答案~

以下是完全沒有數學底子 我的想法, 正確答案在Facebook 這幅圖的top comment已經有了 (按照那個like的數目來看)  好像是用一些我看不明白的number theory 的argument

所以這兒的想法只是自己的FF

首先證明 y = x^3 + 37 (mod 3)

By Fermat's Little's Theorem, y^2 = 1 (mod 3), So L.H.S. = y^2 ... y^2 * y (mod 3) =  y (mod 3)
R.H.S. = x^3 + 37 (mod 3),  So  y = x^3 + 37 (mod 3), Q.E.D.

然後下面是一些完全9 up 的東西, 是關於Chinese Remainder Theorem的。
從 Wiki 可以看到,

Suppose n₁, ..., n_k are positive integers that are pairwise coprime. Then, for any given sequence of integers a₁, ..., a_k, there exists an integer x solving the following system of simultaneous congruences.

這兒我重點關注 any sequence of integers a_i 這句。
我想, 這是不是等同說明

Given y = x^3 + 37 (mod 3)
There Exist some a' = x^3 + 37 (mod 5)  such that 
 y = a' (mod 5) 

因為 3 跟 5是co-prime嘛, 然後x^3 + 37 也肯定是integer for any x
同理 其它 prime number 也跟 3 是 co-prime, 所以 y = x^3 + 37 (mod p) 

然後L.H.S 跟R.H.S. 一同自乘 37次 就行了...


但這只是我的狂想, 因為我根本不了解Chinese Remainder Theorem, 特別是我覺得以上的argument 有違

A solution x exists if and only if

${\displaystyle a_{i}\equiv a_{j}{\pmod {\gcd(n_{i},n_{j})}},}$

所以也就沒再深究下去了。(後註: 後來想下去果然還是錯得很離譜XD)

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, 下年再見吧 :/

Google Code Jam 2015 Round 1B

幾經辛苦,  終於把GCJ 1B的題解都看完, 理解後又做完了

說是全部做完也不太正確, 我最後還是沒做A-Large 以示我的不滿

話說近幾天我開始思考, 為什麼前些日子, 某些比賽/題目

做完之後即使沒想法, 看完題解還是自我感覺良好 很有得著

反之GCJ (還有近來一些CF)的題目好像沒有這樣的感覺?

是我熱情又下降了還是怎樣

最後得出的結論是: 題目的Ad-hoc程度

之前很有得著的題目, 全部都可以很實在地學到一些明顯以後都會用得上的Trick /技巧

例如我還得有一個是用Matrix Multiplication做 N很大的DP

還有前幾篇說的用BIT 數Total Inversion Number的做法

用2個BIT 做Range Add, Range Query的方法

留意題目可能有 SQRT(N) 的暴試方法等

我叫這些做 "性價比" 很高的Tricks, 感覺很多時都會用得上 (而我以前又完全沒學過的)

但就是有些題目, 完全是Ad-hoc的, 可能需要即時的觀察, 推斷, 證明一大堆東西

才會有一個算法出來  但由於題目是Ad-hoc的,  解這些題目中所用到的技巧 根本以後都用不上

我個人不太喜歡這些題目...因為感覺上如果即場做不到, 事後看題解再做也沒意義

反正題解的方法也就只適用於該題目....對吧?

而很不巧的...GCJ 1B 跟1C的題目我認為Ad-hoc度很高, 就是說即使事後明白了也好像沒什麼實在的得著....姑且先寫一下GCJ 1B的題解

Google Code Jam 2015 Round 1B

差47名....但不可惜的, 因為不是時間問題

我看了一下第1000名的分, 起碼要做到多一題才能上頭1000名

題目: https://code.google.com/codejam/contest/8224486/dashboard#s=p0&a=1

A-Small: (Ad-hoc, Greedy)

題A可以說是我最不滿的一題了

題目要求把數字A轉去B, 當中可以用2種Operations:

1. 把A+1
2. 把A Reverse (eg: 123-->321)

問最少要多少Operation才能由A到B?

太多事要證明了, 而官方答案也沒好好的證明題解

我只能說很多人都是蒙混地AC的...

我在CF上求證明, 也沒人理會, 反而是有人回答我他完全忘了這個Case卻AC了 (他得到很多負評)

我的Small是用DP做的, 就是把全部"path"試一下, 要是步數較少的位則update

(跟Dijkstra一樣)

這兒我有賭博成份: 

如果按我CF上的問題來說: 有一Path A-->C-->B 是最優解where C > B > A

eg:  .....-->18-->81-->82-->28 

那我的DP會錯

但我還是照交了, 證明我當時是多絕望

結果竟然AC了...

A-Large: (Ad-hoc)

再來看Large的數據, 加上AC了Small

我有幾點懷疑:

1. 根本不會出現A-->C-->B
2. Reverse不能把digit數加大 (eg 999-->1000)  
3. 所以可能是由(A-->10-->99-->100-->999-->1000) 這樣的分解去做
4. 每一位數的Range內不能暴試...出題者可能有些很快的方法可以由100-->999
5. 可能每一位數的Range內只會最多用Reverse一次? 其它的都是+1?

我是有這樣的估計, 但完全證明不了, 就是證明了也很煩..所以果斷放棄

而按CF紅字User 加 Google官方題解, 這些都是正確的...

準備的來說, Strategy是把 尾N/2 個digit 合到999..9, 一個Reverse, 再用+1 就可以快速把位數增大...就這樣去由A去到B...

但為何Reverse肯定是這樣用一次是最好的我就不明白了...

我也唯有這題沒回頭再去交了, 這題真的太Ad-hoc了, 即使辛苦AC了也沒學習價值吧...

B-Small: (Brute Force)

這題有意思多了

題目給了一個 n*m 的grid

要安排 k 個人住在裡面  一格住一個人

要是有2個人 adjacent 的話, "不開心度" 會加一

現在你可以任意安排k 個人住在那些位置, 問最少的"不開心度"是多少?

想了一想好像也沒什麼想法

也沒什麼Pattern

所以我直接暴試了 (題目數據也是想我們這樣吧...)

就Bit-wise暴試把k 個人都亂放, 看看那個Configuration 的"不開心度"最少就好了~

由於是暴試, 也沒什麼好證明的, Code得對就能AC

B-Large: (Ad-hoc, Pattern Observe, Greedy)

我特意為了這一題, 開了一個我認為好像很多高級題目都會有關的Tag: Pattern Observe

話說這一題, 是真心唯一一題可恨的, 看了題解後認為這一題是有機會可以做到的...

話說比賽中我已經有了一個正確的方向, 很多題目都會利用這一種思想:

不要直接想把k 個人放在那,  去想那些 n*m-k 個格子不要放人"

就是逆轉思維 GCJ 好像很喜歡這種思路呢

簡單來說就是先假設N*M全部都是人, 然後試試把人踢走

踢剩 k 個人就完結  怎樣踢才是最好的呢?

比賽中我認為這題沒什麼Pattern, 原因是: 明顯地如果 k < n*m / 2

可以梅花間竹地安排住客, 答案是0

但要是一多過, 就完全沒Pattern了...

看完題解後, 才發現, 其實是有Pattern的....

首先要是 k <= ceil (n*m/2) 答案就是0

要是大過呢?

大過的時候, 再把Case分為 1D 和 2D (這個CF也見過幾次, 可能是很常見的分析技巧?)

1D的時候, 不難發現只要隔一個隔一個地踢走人就好了 這樣每次都能減少最大限度的"不開心度" (ie: 2)

2D (n 和 m >= 2)

 .3.2     .3.3.     2.3.2     .3.3.
 3.4.     3.4.3     .4.4.     3.4.3
 .4.3     .4.4.     3.4.3     .4.4.
 2.3.     2.3.2     .4.4.     3.4.3
                    2.3.2     .3.3.

4 x 4     4 x 5     5 x 5     5 x 5

借官方的圖一下, 圖中的數字是"如果踢走該位人士, 可以減走的不開心度"

注意 . 的位置是必需有人住的, 也就是說最多就只能把有數字的位置都踢走住客

然後不難發現, 只要Greedy地把佔最多不開心度的人先踢走...肯定會把答案減至minimum 吧?

然後再發現, 其實不開心度的值只會有"2,3,4" 3種

這兒引入一種 可能很常用的技巧, 把Grid 分為 3種可能性的 Size來Observe Pattern:

1. Odd * Odd
2. Even * Even
3. Odd * Even

以這題來說, 把3種情況都畫一下數一下2,3,4的數量, 跟它們的 n , m 之間的關係

很快就有一個pattern出來了

唯一要注意的是 Odd*Odd的Case, 是可以有2種不同的"踢走人的Configuration"

另外2種Case的2種不同Config是 Mirror, 唯有Odd*Odd是有機會不同

不知按那一種去做才更好, 2種都要試一下

下面的code 的 k 跟上面的定義不同, 自己看comment

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

int T,r,c,n,k,totalScore, subtract1, subtract2;
int p1[5], p2[5];
int main(){
    scanf("%d", &T);
    for(int qwe=1; qwe <= T; qwe++){
        scanf("%d%d%d", &r,&c,&n);
        printf("Case #%d: ", qwe);

        k = r*c - n; // # to removed from full occupied building
        totalScore = 2*r*c - r - c;
        memset(p1,0,sizeof(p1));
        memset(p2,0,sizeof(p2));
        subtract1 = subtract2 = 0;

        if(n <= (r*c + 2-1)/2) printf("0\n"); // ceil(r*c/2)
        else if(r == 1 || c == 1) printf("%d\n", totalScore - 2*k);
        else{
            if(r%2 == 0 || c %2 == 0){
                p1[2] = p2[2] = 2;
                p1[4] = p2[4] = (r-2)*(c-2)/2;
                p1[3] = p2[3] = r*c/2 - p1[2] - p1[4];
            }
            else{
                p1[2] = 4, p2[2] = 0;
                p1[4] = ((r-2)*(c-2) + 2 -1)/2; p2[4] = (r-2)*(c-2)/2;  //p1_4 = ceil((r-2)(c-2)/2)
                p1[3] = 2*((c-2)/2 + (r-2)/2); p2[3] = 2*((c-2+2-1)/2 + (r-2+2-1)/2); //p2_3 = 2*(ceil((c-2)/2) + ceil((r-2)/2))
            }

            int tmp1 = k, tmp2 = k;
            int x = 4;
            while(tmp1){
                if(p1[x]){p1[x]--; tmp1--;subtract1 += x;}
                else x--;

            }
            x = 4;
            while(tmp2){
                if(p2[x]){p2[x]--; tmp2--;subtract2 += x;}
                else x--;
            }
            printf("%d\n", totalScore - max(subtract1, subtract2));
        }


    }
    return 0;
}

這題學到的可能比較有用的是:

1. 要是2D的Case太難想, 先想1D, 可能可以引伸到2D, 又或者1D的Case是Special Case要分開處理
2. 要Observe Pattern時, 把情況分為: Odd*Odd, Even*Even, Odd*Even, 而且可以的話最好邊長 > 2 (4*4, 3*5...etc)

C-Small-1 (Ad-hoc)

C也是另一題比較有意思的題目...做不到也是無可厚非, 因為我對Event沒什麼概念

題目太長了就不另外說了

這題是少數Small Case分 2題的題目

Small-1來說由於只有 2個Hikers

我以人力分析了所有可能性, 由於Herbert 能以光速跑動

直接把它想成能和hiker "差不多" 一起跑就好了

(Just before / Just after hiker)

不難發現如果只有2個Hiker, 最多的Encounter只會是一次

Case有3-4個, 就不詳細寫了

基本思路是算一算Herbert 走完一圈的時間, 跟兩個Hiker走完一圈和兩圈的時間之間的關係

又, 由於Herbert可以跟隨便一個Hiker一起走, 直接分析兩個Hiker 跑到 0 度時的時間就行了

假設Hiker 1 初始距離 比Hiker 2 遠離終點

剛要是Hiker 1 跑完一圈的時間比Hiker 2  跑完兩圈的時間快, 則答案是 0, 因為Herbert可以跟住Hiker 1 一起跑 (以Just before的距離跟住他所以不造成Encounter)

還有其它Case都差不多...就這樣了

寫的時候很混亂, 能AC也是很開心的...

#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 flt(x,y) ((x)+eps < (y))
using namespace std;

int T,n,ans;
vector<PII> hiker;
int main(){
    scanf("%d", &T);
    for(int qwe=1; qwe<=T;qwe++){
        scanf("%d", &n);
        int cnt = 0;
        hiker.clear();
        for(int i=0,tp,tm,th; i<n;i++){
            scanf("%d%d%d", &tp, &th, &tm);
            while(th--){
                hiker.pb(mp(tp, tm++));
            }
        }

        if(cnt == 1 || hiker[0].y == hiker[1].y)
            printf("Case #%d: %d\n", qwe, 0);
        else{
            sort(hiker.begin(), hiker.end());
            if(hiker[0].y > hiker[1].y){
                double t0 = (360.0 - hiker[0].x)/(360.0/hiker[0].y);
                double t1 = (720.0 - hiker[1].x)/(360.0/hiker[1].y);
                if(flt(t0,t1)) ans = 0; else ans = 1;
            }
            else{
                double t0 = (360.0 - hiker[0].x)/(360.0/hiker[0].y);
                double t1 = (360.0 - hiker[1].x)/(360.0/hiker[1].y);
                if(flt(t1,t0)) ans = 0;
                else{
                    t0 = (720.0 - hiker[0].x)/(360.0/hiker[0].y);
                    if(flt(t1,t0)) ans = 0;
                    else ans = 1;
                }
            }
            printf("Case #%d: %d\n", qwe, ans);
        }
    }
    return 0;
}

C-Small-2: (Ad-hoc, Greedy)

要過Small 2 要對所謂Event有一定的概念呢

其實重點是有很多重要的Observations...

首先, 能任意改變速度完全對答案沒有影響...

假設最後答案是X, 在Encounter X 次的條件下, Herbert跑完一圈的時間是在限定的range內

相對來說, 它的跑速也是在限定的Range內, 是constant的speed

所以完全不用想什麼改速度之類的Strategy..

然後X最大也只會是H 次, where H = | hikers |

這很正常吧...因為只要Herbert以光速跑動, 一開始就把所有人Encounter一次回終點, 這樣也是 H 次而已

然後我來想定義一下這題的Event...

由於上面的Observation, 不難發現答案跟Herbert 跑完一圈回0度的時間有關係的

所以倒不如把所有Hiker跑到0度的時間當做Event Point, 看看Herbert在這個Event Point的時間點剛好跑回終點的話會發生什麼事

Call the time at which Herbert finishes his hike X, and the times when the hiker reaches Herbert’s starting point T1, T2, T3, etc.

• If X <= T1, then there is one encounter with the hiker as Herbert passes.
• If T1 < X < T2, then there are no encounters with the hiker.
• If T2 <= X < T3, then the hiker passes Herbert once.
• If T3 <= X < T4, then the hiker passes Herbert twice.
• etc.

上面是官方答案抄出來的

要是 X 比某一個Hiker 第一次回0度的時間還早的話, Herbert 肯定爬他頭了

要是在第一次回0度跟第2次回0度中間 則沒有Encounter

之後每一個range都會把Encounter數 + 1

這些T1,T2...就是所謂的Event Point了...它們把Herbert到達的時間分成很多段

每一段的Encounter都可以算出來

又, 由於答案最多是H

所以每一個Hiker 只需要找出它們頭 H 個Event

把Total H^2 個Event 排一下序 (按時間)

把counter設為H   如果該名Hiker是第一次相遇 (T1) 則把counter -1, 其它時候都+1

再假設Herbert 在每一個Event Just before / Just after 回到終點

看看在那一個Event Point的時間會是最少Encounter

#include <bits/stdc++.h>
#define eps 1e-9
#define flt(x,y) (((x) + eps) < (y))
#define feq(x,y) (fabs((x)-(y)) <= eps)
#define LL long long
using namespace std;
int T,N,ans;
bool meet[500005];

struct H{
    LL D, M;
    H(){}
    H(LL D, LL M): D(D), M(M){}
};

struct E{
    double T;
    int id;
    E(){}
    E(double T, int id): T(T), id(id){}
};

vector<H> hikers;
vector<E> eventPoints;

bool tt(E a, E b){
    return flt(a.T, b.T);
}

int main() {
    scanf("%d", &T);
    for(int qwe=1; qwe<=T;qwe++){
        scanf("%d", &N);
        hikers.clear();
        eventPoints.clear();
        memset(meet, 0, sizeof(meet));

        for(LL i=0,d,h,m; i<N;i++){
            scanf("%I64d%I64d%I64d", &d,&h, &m);
            for(int j=0; j<h;j++) hikers.push_back(H(d, m+j));
        }
        int ANS = hikers.size();
        ans = hikers.size();
        for(int i=0; i<hikers.size(); i++){
            for(int j=0; j<hikers.size(); j++)
                eventPoints.push_back(E(hikers[i].M*j + hikers[i].M * (360.0 - hikers[i].D) / 360, i));
        }
        sort(eventPoints.begin(), eventPoints.end(), tt);
        for(int i=0; i<eventPoints.size(); i++){
            if(!meet[eventPoints[i].id]){
                ans--; meet[eventPoints[i].id] = 1;
            }
            else ans++;
            if(i< eventPoints.size()-1 && feq(eventPoints[i].T, eventPoints[i+1].T)) continue;

            ANS = min(ANS, ans);
        }
        ANS = min(ANS, ans);
        printf("Case #%d: %d\n", qwe, ANS);
    }
    return 0;
}

C-Large (Ad-hoc, Greedy, STL)

最後的最後的C-Large了

其實如果一個人能想到C-Small-2

C-Large就很容易了

最大的問題是, 不能把H^2 個Event全部試, 也不能全部儲起

會TLE + MLE的說...

這兒需要用到最後的Observation:

每個Hiker 可以把答案 減1 的機會只有一次

最多就只會 - H

所以總的來說, 我們只要試2*H個Event就可以了

2*H 個Event以後就沒辦法把答案變成 < H了

(這個Observation再來一次也想不到...)

所以答案呼之欲出了: 只去數頭2*H個Event

用Priority Queue! (Min Queue, 按時間排)

先把H 個 T1 Event 放進Queue, 然後每處理一個Event, 才把它下一個Event push進queue

這樣做2*H次就完結

有一個小Tricky位時, 某些 Event T1 跟 其它非T1 Event的時間是一樣的, 

這時必需先處理非T1 Event (先加1)

原因是physically Herbert不能跟T1 Exactly一樣時間到達終點而使答案減1

它必需比T1 慢一點點 (just after)的時間到達, 所以減1的步驟肯定是最後處理 (不然算答案時可能會比正確答案少!)

Code的時間, Implement STL的Priority Queue (本來是max heap)時 加上 greater<>, 再在struct內加上 > 的overload就可以變成min heap了, 而在overload時我考慮了 Event的cycle (就是T1 還是非T1), 非T1的Priority更高

AC是AC了, 但執行時間還是有點慢呢..(在CF上交是2074ms)

#include <bits/stdc++.h>
#define eps 1e-9
#define flt(x,y) (((x) + eps) < (y))
#define feq(x,y) (fabs((x)-(y)) <= eps)
#define LL long long
using namespace std;
int T,N,ans;
bool meet[500005];

struct H{
    LL D, M;
    H(){}
    H(LL D, LL M): D(D), M(M){}
};

struct E{
    double T;
    int id;
    int cycle;
    E(){}
    E(double T, int id, int cycle): T(T), id(id),cycle(cycle){}
    bool operator>(const E& a)const{
        return flt(a.T , T) || (feq(a.T,T) && cycle < a.cycle); //if same time, then T2, T3...priority before T1
    }
};

vector<H> hikers;
priority_queue<E, vector<E>, greater<E> > q; // default is max heap, use greater comp to make it min heap

bool tt(E a, E b){
    return flt(a.T, b.T);
}

int main() {
    scanf("%d", &T);
    for(int qwe=1; qwe<=T;qwe++){
        scanf("%d", &N);
        hikers.clear();
        while(!q.empty()) q.pop();
        memset(meet, 0, sizeof(meet));

        for(LL i=0,d,h,m; i<N;i++){
            scanf("%I64d%I64d%I64d", &d,&h, &m);
            for(int j=0; j<h;j++) hikers.push_back(H(d, m+j));
        }
        int ANS = hikers.size();
        ans = hikers.size();

        for(int i=0; i<hikers.size(); i++){
            q.push(E(hikers[i].M * (360.0 - hikers[i].D) / 360, i, 1));
        }
        // only test 2*H events is enough, or afterwards all ans will >= H
        // As we implement the comp with cycle, same time is handled correctly (add 1 before minus 1)
        // use priority queue to real time generate event so that we do not need to store all H^2 events
        for(int i=0; i<2*hikers.size(); i++){
            E tmp = q.top(); q.pop();
            if(!meet[tmp.id]){
                meet[tmp.id] = 1; ans--;
            }
            else ans++;
            q.push(E(tmp.T + hikers[tmp.id].M, tmp.id, tmp.cycle+1));
            ANS = min(ANS, ans);
        }
        ANS = min(ANS, ans);
        printf("Case #%d: %d\n", qwe, ANS);
    }
    return 0;
}

總結來說, 發現這場所有題目都有Ad-hoc的Tag了吧...

究竟在這些題目上能學多少實用的東西呢? 我也不知道..

題B跟題C的思路還是可以學習一下的吧? 題A就....算了吧