2010-09-25 Team Training - Shanghai 2009

2010-09-25Sat
HKG Time - 1330 to 1830

因為星期三中秋, 冇咁一次 training
所以星期六 (我地呢team) 約番黎打 Code!!

• 題目
• 題解
• Frozen Scoreboard (我地 4 hr 時開左呢個黎睇, 雖然都冇乜理到)

---

Joe 話, 呢個 site 堅難
有幾難? 事前佢只係透露
出線所須題數, 同 champion 既題數相差一倍

最後, 我地喺犯下無數低級錯誤既情況下
做出出線既題數 (4題) 之中, penalty最低既一隊

照咁講, 即係出到線...
...但係... 今日表現真係太過...差

(好rough 咁 estimate)
如果上年 Intuition 唔覺意去左呢個題目咁難既 site
按道理應該都出到線既....

---

打開題目, 見到條音樂 game!!! (Problem J)
即刻好有興趣!!
因為有打開音樂game, 所以要睇明題目一啲都唔難
諗左一陣, 都知點樣做 - bit DP

轉個頭諗一諗, CTLi 同 Joe 好似冇乜打開..
而佢地又有題目忙緊
所以都係我做啦

── 但我錯了... 我 20min 開始起手CODE, 去到2:30先 AC............
(亦係今日自己唯一一題AC)

唉...下次DP都係交俾佢地!!

呢題既難度主要在於 handle 長音 (呢度kick左一排)
同埋... 稍為有一個 trick... 可以由 O(2¹⁴ * 1000) 加快到→ O(3⁷ * 1000)

以下係 Joe 話 Well-known
但就我而言, 係首次 realize 既一樣野：

如果 DP[bit] depends on DP[s], where s 係 bit 既所有 subset
咁樣 對於 length = k 既 bit-pattern, total 呢 2^bit 個 DP state
一共只會有 3^bit 個 DP Transition

---

另外... 我地由 Problem C 既題解 realize 到...
對 string 做一個 naive hash... 唔易撞!
(hash = a_0 + a_1 * s_1 + a_2 * s_2^2 + ... a_n * s_n^n)
其實原理同 Polynomial Identity Testing 差唔多!!

(以前我唔服呢個人寫 寧波2009 題G 段 code... 而家我服了...)

---

總結全日錯誤如下：

• 我既 Problem J 做得超慢, 成 2粒幾鐘：完全 unacceptable
  如果交由 CTLi / Joe 做, 一定可以快過我好多倍, 下次DP一定要靠佢地喇!!
• Joe 既 Problem I 都犯左唔少低級錯誤... 包括, 用錯 comparator sort,
• CTLi 既 Problem D： Algo 啱, 但係... code 不斷犯錯...
  包括唔記得將 counter re-init 做 0 (兩次)
  包括掛住處理 Leap-Second, 而忘卻左 Leap-Year (....)
  包括人手寫既 EGCD 寫錯
• Problem H 既 算法方向完全錯左
  我完全冇質疑過 Joe 既算法：
  佢覺得 Blocking 呢個 relation 係 directional
  查實自己原先諗覺得係 bi-directional (大家有責任)
  不過 anyway... 3D Geom 呢一 part 我寫左好耐都未寫好
  所以 training time 入面點都係做唔到
  (有關於 3D Geom 呢一步, 後來同 CTLi 一提起
  (佢諗左10秒左右, 導出一個極精簡既 Algo...)佢個 Algo 有問題... handle 唔到 case :
  2
  -100  100 1001 100  100 1001 0 -200 1001
  -100 -100 1002 100 -100 1002 0  200 1002

總結今日... Overall...
起步慢... 中間大家又不斷 kick 住無聊 bug (還好 CTLi 既 Problem B 速度 fair)
好慢咁做到4題...
居然係 penalty 最低果一隊, 勉強出到線...
所以都叫做 OK既....
不過咁既表現真係唔得............ 堅信可以再做得好啲