2015年4月13日 星期一

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


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 前幾百名, 根本不太可能實現了






沒有留言:

張貼留言