2010-08-10 Team Training - NWERC 2002

2010-08-10 Tue
HKG Time - 1900 to 2400

• 題目在這
• On Site Scoreboard
• Official Solution

---

這次的題目不算太難（8年前的舊題目...）
在訓練前預先知道這份題目當中有一道難題（題E）
略過此題，其它的幾乎全部做了出來

今天我們 team （= Joe + Kn + Bill） solve 了 6 題
另一 team （= Chin + Danny + Hao + Jian）也不錯，同樣 solve 了 6 題
而超超到後期不肯做題... - -

飲恨是 Joe 的 題G... 我沒能幫甚麼... 他只差一點點

---

Problem A: ICPC 2670 Euro Efficiency

解(Joe)：簡單 DP

令 DP[X] := 完成 $X 的交易，所需最少的硬幣個數（包括「給」和「找」）
注意：需要計算 DP[1..N]，其中 N > 100

沒有仔細想 N 最 tight 的上界... 當時隨便選了 40000 便算了

---

Problem B: ICPC 2671 Markov Trains

解(Kn)：超暴力 DFS!!

DFS 窮舉所有 strategy（即規劃路線）
分別計算各種情況（窮舉班次 miss / arrive 的可能性）下
最後以 map<string,int> 記錄 probability
── 每次 DFS至目的地時，遞加：map[s] += prob;

想過 DP，但題目對 strategy 的定義...
例如 路線容許 重覆經過同一個 city、班次開出與否有 uncertainty

似乎不太可能發現 strategy 的無後效性

當時 Chin 的 team 把這題 AC 了...
然後還一度以題數超越了我們
所以我們也一定把此題做出來

正當我在擔心這算法能否在時限內水過之際...
居然 0.016 sec 極速 WA（然後也極速 AC） 了...

---

Problem C: ICPC 2672 Hansel and Grethel

解(Kn)：簡單 2D 幾何

兩線段相交
沒有 degeneracy

---

Problem D: ICPC 2673 Floors

解(Joe)：離散化 + 模擬 + 貪心

有得切就切！

對每一塊 tile
在有限的切割點（即離散化座標）
嘗試沿 x 或 y 方向切割

留意到切割順序與最終答案無關

每塊 tile 最多被切割 O(N) 次
而 tile 最多有 O(N) 塊

時間複雜度：O(N²)

具體實踐可以用 recursion：

• int f(int sx, int sy, int ex, int ey)
• 對以 (sx,sy) 及 (ex,ey) 為對角座標的 tile
  進行切割後
  return 得出最大的一塊的面積

---

Problem E: ICPC 2674 Picnic

解：幾何 DP

很難... 無論給我多少天

都似乎不太可能想出算法

---

Problem F: ICPC 2675 Pearls

解(Bill)：簡單 DP

有時間再看...

---

Problem G: ICPC 2676 Huffman Trees

解：搜索

Training 期間沒有做出來
後來 Joe 為 cut case 寫了 線段樹 AC 了

---

Problem H: ICPC 2677 Input

解1(Kn)：離散化

離散化座標
統計每一個 Cell 被覆蓋多少次

解2：直接檢查 tile 的 overlapping

感覺挺不錯的 AC代碼

---

很辛苦打了整篇 blog entry

正在做最後期的 fine-tune（檢查 link 有沒有連錯，有沒有離譜的 typo）

快要 submit 之時，感到 Firefox 快要 hang

我趕緊按下發佈文章...

然後... 重啟 Firefox 後...

發現整篇 entry 變成空白......

...沒心機再打了................

虛驚一場...
感謝 Google search engine 的 頁檔存庫...