Google Code Jam 2010 參賽心得

這是我第一次參加CodeJam
運氣很好有晉級到Round2, 因為出國玩的關係就沒有繼續比下去了
有一些心得可以跟大家分享一下

1. 資格賽的部分, 時間很充裕, 只要完整回答一整題就可以晉級
    不過每一題都要解兩次, 第一次的輸入值會比較簡單
    第二次通常都需要對演算法作一些加速才能在時間內跑完程式
    而且第二次不像第一次一樣, 程式寫錯了, 可以一直重試,
    第二次的解答只有執行一次的機會, 所以一定要再三確認程式沒有問題才去執行
    很多人都是因為第二次的輸入值太大, 程式跑不完, 而Timeout, 要小心!

2. 正式比賽就是比誰寫的快了, 至少要快速的完整解完第一題, 才有機會晉級
    通常, 第一題是最簡單的, 最難的是第三題,
    所以千萬不要因為後面的分數比較高, 就跳著做,
    也不要把所有題目都看完才決定做哪一題, 那一定來不及

3. 有時候, 正式比賽的第一題會比較簡單, 所以必須趕快去解答第二題或第三題
    因為每個人學的領域都不一樣, 建議可以快速的看完第二題或第三題的題目
    選擇有把握的來做, 先做簡單的解就可以了

另外, 這次比賽有個比較特別的地方, 就是用到了Big Number的處理
因為我本身是用JAVA, 在處理大數的部份就非常簡單
我想以後的考試, 可能也會要大家去使用一些基本的API,
建議大家在選擇用哪一種程式語言的時候, 也要考慮到這個問題


=====


Our sincerest apologies!  An email was sent to you in error that indicated that you hadn't advanced to Round 2.  You DID advance; there is no part of our system that thinks you didn't; and we're very sorry for the confusion!  Here is the email you were supposed to receive:


=====

Subject: Congratulations - You're on to Round 2 of Google Code Jam 2010!
Congratulations!  You've proven you're one of the best 3000 contestants in Google Code Jam 2010!

Having placed in the top 1000 in a Round 1 subround, you're now eligible to compete in Round 2.  Round 2 will last 2 hours and 30 minutes, and will take place on Saturday, June 5, 2010 at 14:00 UTC.  Visit http://code.google.com/codejam/schedule.html to find that time in your own time zone, and good luck!

If you have any questions, please visit our FAQ at http://code.google.com/codejam/faq.html, or email us atprogrammingcontest-feedback@google.com.

Congratulations!
The Code Jam Team

=====

Sorry for the mixup, and congratulations again!
The Code Jam Team

Google Code Jam 2010 Qualification C

Problem C: Theme Park

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p2&a=2
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=2

這題是最後一題, 應該也算是最簡單的一題

不過有點Tricky, 想答對Large的難度, 要做點最佳化才有辦法

題目是說, 一般遊客去做雲霄飛車的時候, 都習慣一群一群人一起坐上去, 如果有人做不上去的話, 就會等下一班車. 然後, 每個人坐一次會付1元, 我們要算出雲霄飛車一天可以賺多少錢.

例如:

雲霄飛車有 6 個位置, 每天會開 4 次, 遊客有 4 群人, 每群遊客依序有 1, 4, 2, 1 人, 而這些遊客會整天一直排隊坐雲霄飛車.

所以, 第一次雲霄飛車會載 [1, 4] 人 (因為不能插隊, 所以不會把後面一個人的往前補)

第二次會載 [2, 1, 1] 人

第三次會載 [4, 2] 人

最後一次會載 [1, 1, 4] 人

因此, 最後一共賺了 21 元

在解法的方面, 應該都大同小異

我是用一個 Array 存了遊客人數 [1, 4, 2, 1]

另外還有一個相對應的快取 Array 存了計算過的結果 [5, 6, 4, 6]

快取Array, 初始為[?, ?, ?, ?] 
第一次載完 [1, 4] 人, 所以是 [5, ?, ?, ?]
第二次由第三群遊客開始, 載完 [2, 1, 1] 人, 所以是 [5, ?, 4, ?]
第三次載完 [4, 2] 人, 所以是 [5, 6, 4, ?]
第四次載完 [1, 1, 4] 人, 所以是 [5, 6, 4, 6]
第五次之後, 就不需要再計算, 而是直接使用快取的結果
速度上來說, 已經足以解決這個問題

官方提供了三種最佳化, 有興趣的人可以在上去看看

Google Code Jam 2010 Qualification B

Problem B: Fair Warning

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p1&a=1
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=1


這一題的題目很有趣, 但是解起來就不是那麼有趣了, 因為牽扯到大數的問題.
還好我是用JAVA解題, 內建就有大數的函式庫可以使用

題目是說, 在Jamcode星球上, 有一種預言, 西元前發生的幾件大事件, 會暗示哪一天是世界末日

例如:
西元前26000, 11000, 6000年發生了大事件, 則西元4000年會導致世界末日.
因為西元4000年, 離這三個事件分別是30000, 15000, 10000年, 都是5000的倍數, 並且, 5000是一個最大的因數

以這個例子來看
(26000+4000) % 5000 = (11000+4000) % 5000 
(11000+4000) % 5000 = (6000+4000) % 5000 
(26000-11000) % 5000 = 0
(11000-6000) % 5000 = 0

所以
(a + y) % T = (b + y) % T
(a - b) % T = 0

因此, 所有年份的相差值中, 去取出最大公因數, 就是解答

Google Code Jam 2010 Qualification A

Problem A: Snapper Chain

Question: http://code.google.com/codejam/contest/dashboard?c=433101#s=p0&a=0
Answer: http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0

這題蠻有趣的
題目是說, 有一種聲控的延長線
只要你一拍手, 有插電的延長線就會開啟或者關閉

我們以0代表關閉, 1代表開啟
如果有兩條延長線, 由左至右連接
則一開始的情況依序為
[0 0]
再做了一次拍手之後, 則變成
[1 0]
接著為
[0 1]
[1 1]
則使得延長線為通電的狀況

如果有四條延長線, 則為以下的情況
[0 0 0 0]
[1 0 0 0]
[0 1 0 0]
[1 1 0 0]
[0 0 1 0]
[1 0 1 0]
[0 1 1 0]
[1 1 1 0]
[0 0 0 1]
[1 0 0 1]
[0 1 0 1]
[1 1 0 1]
[0 0 1 1]
[1 0 1 1]
[0 1 1 1]
[1 1 1 1]

所以聰明的你
是不是發現, 每16次會通電一次

因此可以歸納出
每2的N次方, 會通電一次

這個歸納, 應該比官方的快一點

簡單吧!!