Topcoder Open 2010 - Round 2

上一次 Round 1 跟 rng_58 同房
今次 Round 2 跟 ACRush 同房

比較慢地把 250 做出來

而那 500 的算法... Ad-hoc 到不得了
在完結前 2 min 才通過樣例並提交
結果被 cha

瓜了...

諷刺的是 rating 微升...
是因為本來的 rating 就很低的關係吧...

---

250

判定 Connecteness
Connected ⇒ Graph 是 Euler Cycle ⇒ 邊權值總和
(這裏我對於 Odd/Even degree 想了一陣子...)
Disconnected ⇒ Return -1

---

500

有好幾種算法... bsearch, monotonicity, by case 處理...

說一下 bsearch 的...

Generate 所有 由單數 digit 組成的數字 - A[N] (N = O(5⁸))
對於 i := 0 to N-1
(二分)查找最少的 A[j]
使得 A[i] + A[j] >= X
記錄最小的 A[i] + A[j]

⇒ O(N lg N)

──自己居然連如此標準 + 簡單的算法都想不出...
實在要好好反省一下... ... ... ...