Member SRM 485 - 被MO屈機

250 開始得好慢
再一次是，挺快想出算法
但 code 的時間花了很久...
Rush 250 的速度居然比以前了，為甚麼呢？

不管如何，這個奇怪的算法...
是 based on 一些 observation
但後想清楚，我只是碰巧想對了：
我當初想漏了一些條件
但因為有 odd/even 的限制，我的算法才正確

---

500... 全間 904 都沒有人能做出來
對我而言，只能想出暴力方法
不過顯然對於 W, H <= 50 而言，暴力太慢了...

waihon 則直覺認為暴搜能過，因為 RectangleAvoiding 條件苛刻

後來我們找超超(他沒有參與這場 SRM)
他一開始便說：我知道當 M >= 3 及 N >= 7 時無解，因為我在 MO 某條題目證明過
（然後再給我們證明 min(W, H) >= 5 時無解)

再看一看 rng_58 的 500
曾經是 IMO 第一的他也有這樣cut case：

• if(W >= 3 && H >= 7) return 0;

後來又看了其它人 (包括 wata) 的 code，發現正解是：

• 當 min(W, H) >= 5 時，無解
• 當 min(W, H) = 2 時，特殊處理
• 當 min(W, H) = 1 時，特殊處理
• 其餘情況，暴力枚舉 ── 複雜度 ~O(2²⁴)

實在比較難想出這個方向...
果然被 MO 屈機了... T_T

---

在 250 很慢... 以及上次 Rating 大挫的條件下
是次 Rating 微升 17...

我堅信，Rating 高低未能完全表示一個人的實力
不過時間愈長，Rating 愈會是一個比較有力的指標

無可否認，數學能力對 Topcoder 來說很重要呀...