2010-07-27 Team Training - CEPC 2003

(CEPC 是當年的簡稱)

• 題目在這
• On Site Scoreboard
• 官網在這

又是被折磨的一次 training

今天我們 team （= Joe + Kn + ytlau9） solve 了 3 題
呀... 還好啦
（Gagguy + Bill + Danny solve了 4題）

Joe 今顯得有點不冷靜... 是因為緊張晚上的 Google interview 吧？
然後他早走了

ytlau9 幫我在好些問題上指引正路
沒有他，我想大概不能 AC 第3題吧...

---

Problem A: ICPC 2922 Easy task?

解：data processing 水題... STL 減省 code length

---

Problem B: ICPC 2923 Bundling

沒有看...

---

Problem C: ICPC 2924 Shortcut

解：排序→掃描

為所有在 path 上的 grid point 記錄以下資料

1. x- 及 y- 座標
2. 時間點
3. 行走方向

然後進行兩次「排序＋掃描」：

第一輪： by-x-then-y 排序
對每連續兩點檢查
若 x座標相等，則有機會是 shortcut
這樣便可以 O(N) 掃描所有 南北向 (not 南北行 or南北杏) 的 shortcut

第二輪： by-y-then-x 排序
類似地，可以線性掃描所有 東西向 的 shortcut

要比較小心的是 length = 1 的相鄰點
── 兩點連起之線段未必是 shortcut，可能在原本的 path 上

我在這個判斷上折騰了好久... 最後經 ytlau9 一提：
兩點時間相差 = 1 ⇔ 不是 shortcut

Subtlety：
兩輪 sorting 不必分開寫：
for (int iter = 0; iter < 2; iter++) {
    sort event point  by x then y
    linear scan
    for each event point

        swap(x, y)
}

---

Problem D: ICPC 2925 Dice contest

還沒有完全想出來... 說說跟 Leo 的討論結果
應該是在起點以及終點局部的地方做 shortest path，然後（後補）

---

Problem E: ICPC 2947 Roof

解：已AC... 稍後再寫

Joe 臨走時沒有 AC，因為算法錯了（好似係）
呀... 他沒有／太怱忙所以沒有告訴我
所有垂直線最多穿越 100 塊斜版

---

Problem F: ICPC 2941 Football

很變態的一道題...我想是... searching？

on site 有兩隊 AC...

在 PKU 上有大量 ~500 Byte 的 AC submission...

疑似存在極簡單的算法 

2010-07-30 更新：
CTLi 的解法是 solve equation，LOC = 18!!

---

Problem G: ICPC 2928 Which is next?

很多隊伍通過的一題...

暫時沒有想法

2010-07-29 更新：
Leo 及 Chin 已解：
給定的 tree encoding 其實是 tree 的 pre-order traversal
當中，每一個 bit 表示一個 node
 1 ： internal node
 0 ： leaf node

而找下一棵樹的方法...
大約是 由右至左找第一個 "100" 抽出來
向左邊找最近的 "1" 插入
最後再將這 "100" 的 右邊重新調整至最小...

---

Problem H: ICPC 2929 Hang or not to hang

解：BFS

很好的題目！關鍵在於減少狀態數目：
由某些 observation，可知最重要的 variable 的數目只有 ≤ 16 個
然後，便可以2¹⁶ BFS 暴力搞了

算法輪廓...
是在 training 完結前 40 分鐘跟 ytlau9 討論得出結果 ＋ 靈機一觸
不過 code length 很長...  現場 AC 的機會頗微

詳參這篇 blog entry

---

Problem H: ICPC 2930 Minimizing Maximizer

解：segment tree + dp

Joe 一開始想錯了算法... 然後便走了

跟 ytlau9 商討確認算法
硬著頭皮做... (自己對 data structure 很沒信心)

最後做到... 是首次在 trianing 做到 segment tree 的題... 不錯不錯

這道題大家都做到... 不錯不錯

---

打 code 時要再冷靜點呀...

---

又是雨天...

如果明天不用回校多好呀...
(2010-07-28 按：次日下午黑雨了...)

Offtopic:
http://news.haedu.cn/SWCZ/634004398439843750.html
Like the last paragraph...