Codeforces #23

依然不是解題報告

---

今次的題目很難呢...
rating 下跌了
但無悔參與了... 因為感覺很有得著

這場比賽題目挺奧妙的... 對算法要求比較高...
Codeforces 的性質就是
總有一兩道非常簡單的題目
題A 激簡單
題B 是簡單題... 但是 trap了 1 hr...（然而 solution 極簡單...orz）
題C 的算法很精妙（現場只有40 人AC）
題D, E... 分別是 2D幾何 及 樹狀dp(?)... 較難

---

題A... 在 2 min 提交... 貌似這是第15個submission
不少人在 0~2 min KO... 此題直接略過

---

題B... 挺奧妙的 graph 題目

題意：
有 N (≤ 10⁵) 個人參加了聚會
在 time=0 時，沒朋友的人離開
在 time=1 時，在剩下的人當中，有1個朋友的人離開
在 time=2 時，在剩下的人當中，有2個朋友的人離開
..
如此類推
問，給定 N，在最後最多可以有多少人剩下來？

──一開始就便寫的不清楚的描述誤導...
我還以為 "Then those, who had exactly 2,3,...,N-1 friends among those who stayed by the moment of their leaving, did the same." 的意思是
有 ≥ 2 位朋友的一次過離開
留意這種 interpretation 無損樣例的正確性... ... orz

在 clarification 返回答覆時，已經跑掉了30分鐘時間...
由於發現不少 1x minute 的 submission
加上這是 題B
判定這題的 solution 一定很簡單...

不斷努力地想，在 1:05 才得出正解：
正確的 Graph 是：在 N-Complete graph 移除 1 條 edge

答案 = (N==1) ? 1 : N-2

...AC之後，我立即回想起 Tehran 07 那道題目 - WonderTeam

因為誤解題目及忘掉 N=1 的狀況，一共 WA 了三下
再加上提交時間...penalty 極大...

---

題C... 貌似簡單，卻是很有玄機的一道題

題意：
給定兩個長度為 2N-1 (N ≤ 10⁵) 的陣列 - A[2N-1], B[2N-1]
現從中要選取 N 個 index
使得
這些 A[i]'s 的總和 ≥ 所有 A[i]'s 的總和的一半
這些 B[i]'s 的總和 ≥ 所有 B[i]'s 的總和的一半
問，可行嗎？選哪些 index？

──當時感覺：必然 possible，並且算法應該跟 sorting／貪心 有關
但想了很久都沒得出算法...

然後剛剛看完 solution 感覺有點無語...
只概歎，當時沒想出來實屬正常！

不過... 即使知道算法亦不表示能夠 code 得到
目前為止 我只想出 O(N²) 的實現... 會超時

另外，亦存在 疑似水過的算法（subgroups of n contiguous boxes, wrapping around）
（剛才查考過一些 AC 的 code ，果真有人如此這般地寫）

---

題D... 是2D幾何

題意：
有一嚴格凸四邊形 (Strictly convex quadratilateral)
其中三條邊等長
給定這三條邊的中點座標 (x, y 皆為 [0, 10] 的整數)
求該四邊形的頂點座標
（要判斷 Impossible）

──這是比賽剩下 50分鐘時決定上的題目... 最後沒做出來

我想出的算法涉及 三角函數 的運算
不過對於給定取值範圍... 應該不會存在精度問題
程序在比賽完結後 30 minute 左右才通過樣例
Debug至今(12/7/2010)仍然無限 WA...

---

題E... 樹狀dp (?)

題意：
給一棵有 N (≤ 700) 節點的 tree
將其之成若干個 connected subgraph
使這些 subgraph size 的 product 最大

──在 contest time 完全沒有時間去想

---

所以... 首兩道題目的提交時間
決定了大部份參賽者的名次 以及 rating 上落

---

插個花：

剛才隨便在 google 鍵入 "SRM" "Codeforces"
看了幾個 blog（都是內地同胞）
發現不少人會在打 online individual contest 跟別人討論...
甚至直接索取公式...（例如 SRM 的 那些概率題）

真是的.........................