Google Code Jam 2015 Qualification Round

愈來愈忙了, 弄得我計劃好的事(很多)都要先放下了...
6月前看來都要忙死了 :(

但既然我都跟Peter 神說了我自小的夢想, 就是有一件比賽T-Shirt
所以還是擠了時間第一次 (還是第二次?) 打了一年一度的Code Jam

就結果來說, 雖然過了Qualification Round, 分數卻很難看
果然比賽T-Shirt基本實力就是有Div. 1 中上級的實力吧...

話說我一直以為Qualification Round都是很易的
起碼是沒精神的情況下還是能輕鬆過的程度
沒想到這場對我來說這麼難...

比賽有4題, 每題分大小case
即場我交了A1, A2,  C1,C2  而只有前3個AC了, C2 因一個白痴錯誤搞至WA....
至於B, 我知道Solution後才發現自己腦閉塞了, 怎麼我感覺比C難
D是完全沒頭緒, 連小的Case也沒有, 後來問GG 好像是人手找Pattern再Code的樣子

Google Code Jam 2015 Qualification Round

題目: https://code.google.com/codejam/contest/6224486/dashboard

Google的題意大都很有趣, 這點我覺得比FB Hackson Cup好, 雖然很長就是了...

所以寧遠晚點睡還是打長一點

A: (Greedy)

題意是這樣的

有n個人看表演, 每個人都有個毒撚程度叫 a_i,  代表在他之前要有 a_i 個人站起拍手, 他才敢站起拍手。現在要你請五毛, 每個五毛面皮極厚, 不論有多少人已經拍手, 他們都可以拍手, 請五毛要花五毛, 所以求最少請多少位五毛才能使所有人都拍手呢?

基本思路就是, 一位五毛反正何時都能拍手, 不如一開始就拍手, 把他們作為其它毒撚的觸發點。然後假設有毒撚a_i 跟b_i,  a_i < b_i , 則 b_i 比 a_i需要更多人, 而a_i 肯定在其中, 這樣的話, 用for loop 計算所有毒撚還需要多少人才會站起 (假設毒撚度比他低的人都已經站起了, 所以可以扣除他們), 拿個maximum, 就是我們求的五毛總數, 可以把他們全部放在一開始時就拍手, 那麼好像骨牌一樣, 之後所有人都肯定會輪住站起拍手了。

B: (Greedy)

這題很糾結, 主要是....不知道為什麼自己卡了

其實核心思路一早就發現了才對

雖然現實中是因為要上街所以沒時間想很詳細...

直接說一下題目:

有一間餐廳, 裡面竟然有無限人,  但只有1000位人客是在吃東西的

這些人客每個人在吃a_i 樣東西

1秒之間, 可以發生以下任意一件事:

1. 所有有東西吃的人都吃一件東西
2. 所有人都不吃東西, 服務員把其中一位人客的食物, 拿走任意數目, 然後分給另一位人客

求最少時間令所有人把東西都吃完~

首先很直接的, 如果把人客的東西分給別人, 一定是分給沒有食物的人吧 (有無限人啊...)

然後假設有一堆人, 其中最多食物的人客有 k 樣食物, 那麼答案最多也只是 k

廢話說完, 開始說點有用的:

1. 假設有 a 秒 執行動作 1, b 秒執行動作 2,  答案是a+b秒, 肯定先執行完全部動作2
2. 因為順序不影響答案, 所以就可以分開求, 也就是先把 1 或者 2 都執行完了, 才執行另一種

再看看數據, 1000*1000, 其實也很明顯叫你用O(n^2)的算法了

首先 動作 1 (全部人吃東西) 這個可以暴試的, 問題在於動作 2, 好似有點煩

這兒其實是有點logic的,  假設現在 有 a 秒執行動作 1, 執行完就完了, 全部人都吃完了

那麼在執行第一個動作 1之前, 所有人的食物數都不得超過a, 不然就矛盾了...換句話說, 在執行第一個動作 1之前, 我們要執行動作 2 k次使所有人的食物數都不得超過a

所以問題就變成 給了一個數字 a, 求最小的k 使 k次動作2之後, 所有人的食物都 <= a

留意動作2只影響到一個人, 所以其實又可以獨自求...用一個for loop 把所有食物數 > a 的獨立求出最小的k, 這些最小的k 加起來, 再加上a 就是當用上 a次 動作1時的最優答案 用一個for loop 暴試所有a,  總共就是 1000*1000 = O(n^2)了

至於求出最小的k 那一步, 我們要用O(1)來求了

這步才是最難證明的!!

設 a = 5, k = 12,  正解的方法是簡單直接的一直減5減5這樣, 所以是 ceil(12/5) - 1

但怎樣證明其它分解不會更好? eg: 12-->{6,6} --> {1,5,6} .... 

其實我也是事後AC了才回頭想...好像不是那麼直接 (可能我想多了?)

最後我用這樣的步驟說服自己:

設k = X+Y = a + Y'  , X>a, Y>a

然後我們再做多一步
X+Y--> X1+X2+Y ,  a+Y' --> a+a+Y''

Case 1: 如果X1 跟 X2都比a 大, 則繼續, 這時RHS <= a 的數目更多

Case 1: 如果X1或者X2 > a的話, 這樣跟原先的狀態一樣(兩邊扣除一個 <= a 的話), 這是還是RHS比較多 <= a的數字

Case 2: 如果X1跟X2都 <= a,  則LHS跟RHS一樣多 <= a 的數字而已

一個不正式的induction 說服了我自己其它拆法不會比單純地 k 減a,再減a...這樣更好

所以...很簡單地暴試a時, 發現有 數字比a大, 則 k = ceil(b/a) - 1

就是簡單的除法, 真的很直觀的....= =

我還是認為這題不易, 為什麼那麼多人做到=.=

起碼我一開始是想都沒想就認為拆法一定是除2除2 地拆....唉

C: (Math)

這題題意有點複雜, 就不重覆說了, 題目名倒是很有趣, 叫Dijkstra, 但題目自己也說了, 跟Dijkstra Algorithm完全無關 (o:

給了一個類似cross product的matrix,  i.e  i*j = k,  j*k = i,  j*i = -k
然後給一條string, 這條string只有 i, j, k 這 3個alphabet, 這條string 重覆 L 次

問能否把這條重L次後的string 分成3段, 分別的product是"i", "j", "k"

這條反倒我認為是很直觀的說, 麻煩在於有1 和-1的存在, 但基本思路如下:

首先, product 為 i 的string 其實是prefix,  為k 的string 是suffix
然後中間那段肯定要是 j, 要是符合這3個條件的就算是成功了

想到會有數個 product 為 i 的prefix, 好像有點複雜
但其實留意到 自己*自己是-1 這個特性, 可以寫下以下的算式

設 整條 string 的product 為C, 

假設存在某prefix product為i, 某suffix product 為k, 但我不知道中間那段的product, 叫它x
那麼  i * x * k = C

然後做一件中學時常做的事!
i*i * x * k*k  = i*C*k

--> -1 * x * -1  = i*C*k
--> -x * -1  = i*C*k

--> x = i*C*k

看! 這個結果, 代表很多事

首先, 有多少個 頭i 尾k 根本不重要, 因為中間那段肯定一樣, 都是 i*C*k !
所以最重要的是存在頭i 尾k
然後 i*C*k 要是 j 的話, 就成功了, C可以O(N)直接求出來的 :)

這樣就輕鬆過C1了...

至於C2, 不同的是在於數據大很多

根本不可能用直接做, 連O(N)都不行....

這時要用上多點觀察:

由於string S會重覆 L次,

我們現在不能直接求  S*L 的product了...

但我們可以先求S的product

然後發現一個事實(for i, j, k):
i = i
i*i = -1
i*i*i  =  -1*i = -i
i*i*i*i = -i*i = 1
i*i*i*i*i = i ....

看! 一個字母, cycle length 為 4! 第5次開始又等於自己了..可以利用這個來算出S*L的product!

-i, -j, -k 的cycle 也是大同小異, 小心處理即可

這樣求出S*L的Product後, 同樣道理, 我們找頭 i 尾 k 時, 只需要在S*4 裡面找就行了, 因為再重覆就真的重覆了... 注意尾k 的位置可能比頭i 前, 這樣也要當成失敗

很簡單吧? WA了!!!為什麼...

靠, Debug了半天...原來...

S的product除了是 i,j,k, -i, -j, -k, 1 之外 (這些我比賽時都處理了)
還可以是 -1 !!!!

-1的cycle是有不同的....這個處理後...就AC了 (在練習模式)

這個也是急住上街的後果啊...我不後悔就是了

看來我果然還是不太合適那些要一棍過定生死的玩法

難怪我喜歡自己跑去CF打練習賽 (O:

但總結來說這題比B絕對來得易...

D: (???)

看圖識字, 這種俄羅斯方塊類的題目, 看見就不想做, 也不懂做....看看幾年後有沒有興趣學習吧, 反正還有太多基本功要學了= =

總的來說, Qualification Round已經這麼難了...根本不能想像怎樣打Round 1, 要T-Shirt還要Round 2 前幾百名, 根本不太可能實現了