GCJ 2010 Round 1A

朝早九點開波..

A - "K"子棋, given current state, 問 rotate 90^o 後邊一邊會勝出 (可以both/neither)
但開頭 score 分佈出錯左, 以為有 trap, 所以無即刻揼.. 決定睇埋B,C先

B - given sequence {An} in [0,255], 可以 add/delete/change (各自有 cost) , 目標係試 neighbour 的 difference <= M, 求 min cost

C - 兩人玩的game, 一開始有兩個數 (A,B), 每一個 step 可以改為 (A , B-A*k) 或 (A-B*k , A) , k 是正整數, 問某個 range 入面有幾多 pair (A,B) 是 winning state



analyze下, B 明顯係 DP, 應該幾輕鬆 ; 但 C 疑似 Nim game 果類, 基本上係未 code 過
之後佢出 clarification 改返分數, 發現 A 佔分最少, 於是放心去寫A, 大約 30 mins 時 A-small  Correct!


今次打算用一個 strategy - 唔隊 large 住, 之後有時間再 double check 多次, 因為 large 得一次機會同埋GCJ 計時間係計最後 submission, 對penalty無咩影響 (如果之後會再 submit 的話)
寫 B - DP, change 同 delete 好易 handle, add 諗左一陣, 確定係 round up 除法, 過 test case, Correct!


之後就朝 C 進發
C - 睇多睇又唔似 nim, 於是用 memorization 的方法去打個表搵observation, 得到
 123456789
1*........
2.**......
3.***.....
4..****...
5...*****.
6...******


很明顯地有 pattern -- 之後就陷入一小時的掙扎
一開始以為係好簡單既 pattern, 但試左幾個 sequence 後後面又總係唔 work, 於是出動武器 - KMP 用電腦去搵 pattern, 但 turns out 佢係無一個 "repeat" 既 component ..!
唔忿氣, 出動埋 guassian , 話唔定係一條 polynomial , 入左頭 5 個數落去就知唔 work - solve 出黎的 coefficient 唔係 integer ... 睇黎條 sequence 唔係 polynomial ..


諗
諗
諗


剩返 20 mins 果陣, 突然發現

 123456789
1*........
2.**......
3.***.....
4..****...
5...*****.
6...******



每一行/列 * 的數目 等於 果行/列 的篇號!
諗深一層, 其實係同 self-describe sequence 差唔多  突然感覺到離答案只差一步

揼... 揼... 揼...

大約剩返 8 mins 時揼好, submit, Incorrect
灰左一灰, 但立即想到是 BIT 越界問題, 改, Correct!




Result ..

113

gagguy Me

100

2:30:38

32:50

1:36:12

50:27

1:39:01

2:26:02 1 wrong try

2:26:38

不過最滿足都係做到條 C







後記

睇返 official report, 原來 B 有 O(NM) 的做法, C 和 golden ratio 有關
GCJ 牽涉的範疇真的很廣泛, 學多d野才是上策