2010-07-20 Team Training - CEPC 2002

(CEPC 是當年的簡稱)

今天是久違的 team training
雖然人未齊

最後我們 team （= Joe + Kn） solve 了 4 題
超超 solve 了 5 題
（scoreboard後補）

總而言之，今天表現很差（未至極點，但差不多了...）
寫出來的 code，code length 差不多是正常版本的 2 倍
我做到的 2 道題目，分別是 standard 到不行的 BFS 和 Shortest Path...
卻總共錯了 5 棍...

雖然沒有從口裏說出來
但我確實拖累了 Joe
讓他沒有時間想／code／和我discuss 第 5 條題目...

愚以為不是 coding 能力的問題，而是不夠冷靜的問題...

Joe 又道出一個慘痛的事實：我們敗給 8 年前的 Warsaw !!
（而超超則單挑奪得亞軍）

---

Problem A: ICPC 2662 Family
解：頗直接的 High precision＋Topological sort
可 Live Archive 不能提交 BigInteger／BigDecimal

──講起我就扯火：

在若干年前，我幾經辛苦（１～２ hr）

用 BigInteger 把這題 DP code 好並通過 sample
提交時竟然返回一個 Compile Error ........

如果可以用 Java BigDecimal 我絕對會上...

---

Problem B: ICPC 2663 Intervals
解：Binary indexed tree／Greedy
被 Joe 輕鬆解決

---

Problem C: ICPC 2664 One-way traffic

沒有 idea...

有 flow 的感覺
應該是先把所有 SCC 找出黎，然後... dunno
(2010-07-21更新： 題解是做一次DFS... 詳細未看)

---

Problem D: ICPC 2665 Rhombs

沒有 idea...

他們聽過超超複雜的解說
以及看完了他極短的代碼以後
判定為 mission impossible（雖然這題 AC 的比率極高）

---

Problem E: ICPC 2666 Servers
沒有(時間)認真想...
這條題目我沒有參與閱題

後來發現光是理解 interesting 的定義已經要花點時間
Joe 在 training 時讀漏了一項 constraint - this sum does not exceed 30n
他說，若果當時有發現應該能頗輕鬆地解決
(2010-07-21更新： Joe 以 shortest path 輕鬆解決)

---

Problem F: ICPC 2667 Solitaire
解：Bidirectional BFS
其實我想過 64C4 ── 只是一種不同的形式 ── array of pair<int,int>
最後選擇使用 long long int 做 encoding
是因為可以減省 code length
另外，因為 range 比較小，關於運行時間上問題應該不大

coding 過程卡了很久...

1. 閱讀題目漏了 step ≤ 8 ...
2. 用 single source BFS 單是運行 sample 已經要花 1.0 sec
   在頗後期才想到可以雙向搜 ...
3. Logical bug:
   Incorrect:
   while (h != t) { if (current > 4) break; exp(node);}
   Correct:
   while (h != t) { if (current >= 4) break; exp(node); }

都是不可原諒的過錯...
而且還一次過出現三項...

---

Problem G: ICPC 2668 Timetable
解：Variation of Shortest Path
state[city][time] := 由 city 在時間 time 出發，抵達 city N 的最早時間

具體實現方法：
先把所有 <N, time> push 進 queue／priority_queue
然後用你最喜愛的 shortest path algorithm往前搜
──建議 SPFA/Dijkstra with heap，因為數據規模較大

這道題也卡了很久... 做了一個懶醒的「優化」導致 WA
（後來發現這優化在 worst case 時幾乎起不到作用）
添加了不少不必要的行數...
(2010-07-23更新： 同一算法提交至 PKU1203 → TLE)

---

Problem H: ICPC 2669 Voracious Steve
解：Game／DP + 打表
Joe 和 我 都沒有想出好的算法
Joe 最後用 O(100⁵) 時間打表提交

（打表大約花費 1.5 minute）

---

On-site champion 解了 7 題
1st-runner up 解了 5 題

若果有 BigDecimal，大概一定能解掉 Problem B
我當時的算法錯了...

如果 CTLi 在場，或者可以更快地解決 H
（他可以解決 D 嗎？我想應該可以）
那 Joe 便有時間想 C 或 E

不過考慮到這是 8 年前的題目... 我們怎麼都是輸了...

---

感想：還是不夠冷靜吧...

倘若能夠把平日 Training 剩下的題目全部...
不，一半
做好，已經可以變得相當厲害了...

我要變強呀......!!

至低限度... 要能夠二人合力擊敗超超!!

---

完全 Offtopic：偶然間發現... 在 vision / graphics 界的 research 頻繁濫使用的 Kd-tree
~= k維 的 Segment Tree （好似係）

---

（2010-07-30 更新）
剛才就問起 CTLi 有關於 Problem D:

kn 說:
*is that rhombus problem intuitive to you?
Ivan the Terrible 說:
*quite
kn 說:
*i see