SRM 475 ∩ Individual Training

本篇 entry 不是解題報告...

---

今天是 coding training
碰巧是 (非常棒的) SRM time slot
於是把 SRM 當作這次 training

大家一起在 lab SRM... 挺有氣氛的

在 SRM 開始前... tc 的 server 還是有點問題...
還好，最後大家都能順利登入

當分房完畢，按下 "Enter" 後...
發現同房有一個 target 紅色... 然後過了半秒才反應過來...

「又係 rng_58 ?!」

坐在我身旁的 those 很冷靜：「e? 入得喇？」
過了半秒，他亦驚呼：

「rng_58 ?!」

在比賽開始前 1分鐘
rng_58 突然說： "unsual point values..."

噢... 三條題目... 分數分別是 300、600、900...

---

今場比賽 RP 實在太高...
一/兩次編譯便通過 sample
然後，隨便打了一段 長度 16 的 string 及 選擇 r = 8
發現運行時間不長... 猶疑了一下便毅然提交...

開了 600... 很絕望...
再看 900... 更難... 簡直無從入手

今次的 600 連超超也沒辦法... 可想而知... 題目很深

---

最後結果是：
全房只得 rng_58 一個提交 600
其它只提交 300 或者沒有任何 submission

而在整個 Division 1 當中
600 及 900 分別只有 寥寥可數 的 42個 及 18個 submission
而當中很多都掛了...

我的 300 以 22x 分安全通過
拿了 rank 65（久違的高名次...）
rating 上升了 137，創了新高！
──實在太感動了... 終於打破了 rating 收險的命運... T_T

今次的題目特別難...
而且全部三條都以 rabbit 作為故事主角...
（很自然令人聯想起 rng 那道 三隻兔子 神題...）
──以題目難度來說很奇怪... 明明 rng_58 及 Vasyl[alphacom] 都有參賽... 究竟...
──未知 rng_58 看完 rabbit 以後有何感想？

---

300

n ≤ 17， r ≤ N
窮舉 nCr 種狀況
分別進行 O(n²) 模擬

從 those 及 nichehole 的代碼中
學習了應用 next_permutation 窮舉 nCr 種狀況：

int ch[n]; // ch[i] = 1 ⇔ i^th is chosen
int a[r];
FOR(i, 0, n) ch[i] = i < n - r ? 0 : 1;
do {
　　int m = 0;
　　FOR(i,0,n) if (ch[i]) a[m++] = i;
　　// Now, a[r] is the desired list
　　// ...do simulation or wtever
} while (next_permutation(b, b+n));

以後時限許可便不用寫 DFS 了 @@
（這段 code 亦可以擴展至窮舉 nPr 種狀況）

另外，此題存在一個非模擬的方法...
有興趣可以參考 rng_58 的 O(nCr * n) 的 solution
究竟他怎麼想出來...？
──或者在 practice room 看 writer 的 solution...
原來 rng 的 solution 非常接近 writer...）

---

600

完全沒有Idea...

主要卡在不知怎樣在 mod M 的同時
記錄 兩個值 的相對大小...
有想過應用 Java BigInteger 及 matrix multiplication 硬做
不過 digit 數量太多... 會超時吧...

賽後發現通過的選手 大多在計算過程
分別 對 M 及 1<<60 (或其它很大的數) 分別取模 (Mod)...

按：剛剛在 Practice room 看完 Writer 的 solution... 只是 mod M 也行呢...

---

1000

更不用說了...
應該是比較難的 DP...

---

謎底經已揭終... 這次的出題者是 lyrically
.....你們也太喜歡 rabbit 吧？

以後... 我們該怎麼應付如此厲害的對手？