HKG Time - 2300 to 2500
- 題目在這
- Standings（大scoreboard）
- Room 10 Scoreboard（My room）
Codeforces format：
留意標題後的括號 - Codeforces format
比賽模式跟 SRM 很相似：
- 難道不同的題目分數不同：
(A,B,C,D,E) = (500, 1000, 1500, 2000, 2500) - Submit 時間愈早分數愈高
- 比賽完結時才進行 System Test
- Submit 後即時得到 Pre-test feedback
- System Test 的順序是按 Submission Time 進行
（這在設計上比 SRM 好！) - 容許 multiple submission
每個多餘的 submission -50 分
──e.g., 提交了 3次，分別是 WA、AC、AC，那便會扣減 100分
- Hack 和 Code 同時進行
- 要 Hack 某題，得先通過 Pre-test ，並 Lock 起該題
i.e., 下定決心以後不再 re-submit 該題 - 若果某題的 code 被別人成功 Hack 了
而你沒有 Lock 該題，你會得到被 Hack 的 prompt - 當某題被 Hack 而你沒有 Lock 該題，你可以 re-submit
- 成功的 Hack +100分
- 失敗的 Hack -50分
先來簡單題解... 再來詳細戰況記錄...
最後說說 System Test...
題解概要：
A： Prime Sieve 變種
B： 簡單貪心
C： 貪心、稍為麻煩的 Simulation
D： Catalan Number 變種
E： 直接構作+貪心...?（只是比賽當時的想法，沒時間完成 coding）
戰況概要：
我把 題A, B, C 解了...
另加一個 success 的 hacking
最後 全3題 亦成功通過 System Test
得了個不錯的rank - 53位
題D 觀乎 數據規模，只能用 closed-form 做
可我一點也沒有聯想起正解： Catalan Number...
開始 code 題E 的時候比賽只剩 40 min
敲到中途又發現有些情況很難 handle... 沒時間修補
戰況：
在提交 題A （題目不難，是 Prime sieve 的 variation）以後
發現分數... 怎麼不是時間, 而是數字?!
看清楚一點... 發現這次是 Codeforces format...
然後... 我發現在題目版面 紙飛機 Icon （表示已提交）旁邊
有一個 Lock icon
按下後... instruction 說把 submitted code Lock 了以後
便可以 Hack 其它 submission（~= SRM 的 Challenge）
──Lock 了以後此題便不能再提交
這時看看大 scoreboard，排名不後
過幾分鐘後再看，發現分數好像下降了?!
心想：難道沒有 Lock 的 Submission 分數會不斷下滑
i.e., 按下 Lock 才算真正 Submit?!
──到比賽完結後，跟 chin 討論才知道，其實不是這個意思...
那... 沒辦法... 只好細心 check code 然後再 Lock
現後我看 題B...
怎麼 N 的範圍那麼大?
沒有想法...
只好看 題C...
發現是 Greedy
但情況數目比較多
最後的算法，是按 m 及 n 的奇偶性分 4 種情況逐一考慮
──具體處理方法如下
- m, n 皆為 odd，顯然無解
- m 為 odd，最少要使用 n/2 塊 2 x 1 的 tile
- n 為 odd，最少要使用 m/2 塊 1 x 2 的 tile
- m 和 n 皆為 even
情況 2, 3 做了如上述的處理以後
問題便會化簡為 情況 4.
而對於情況 4. 其實問題等價於
能否以 2 x 2 的 tile 密舖 m x n
其中 2 x 2 可以由兩件 2 x 1 或 1 x 2 的小塊s組成
（詳細就不再說了，反正不難想... 而且寫出來會係累贅）
縱然花了一段時間 simplify code
最後敵出來還是比較長...
Submit 第1次 兼通過 Pre-Test 後
自己再針對上述四種情況分別生成 test case 逐一測試...
發現 bug、 debug、提交
最後，在提交 第3次 時決定把 code Lock 起
──我還是以為要 Lock code 才能停止分數流失，而且還白白加了一次 submission 的 penalty
再看 題B... 還是沒想法... -_-
無事可做之際
隨便 double-click 開了某同房參賽者的 C
他寫了..
for (int i = 0; i < strlen(s); i++)
...
看見這樣的反應，當然立即 Hack...
為求保險，我依著他的 Source Code
在本機照著打一遍然後 Compile → Run
──其實沒這必要，這錯誤太明顯...
然後...便發現 Codeforces 設計很好
居然可以提交代碼生成 test case
可是，第一次 Hack 失敗了...
System 說：
Invalid input
看了 Scoreboard... 發現 沒有增加罰時之類
便 搜尋說明... 找到了 Codeforces Contest Rules
然後再仔細檢查程序... 原來自己漏了一個 '\n'
Successful hacking attempt
分數加了 100!
我很貪心地檢查每一個同房的 submission
發現原來第一個開啟的代碼含這 bug...
然後再看 大scoreboard
發現全房幾乎都提交了 B...
而且有很多提交時間是 1X 分鐘
立刻得出結論：算法一定很簡單
畫了幾個 sample... 終於想出了：是簡單貪心
... 可惡
不過這也算了...
Codeforces 跟 SRM 不同的地方在於
AC 所獲的分數
跟開始閱讀 problem statement 的時間無關
可能先做 C 得分會更高...
所以... 我同房那個 red 由 E 至 A 倒著做
其後我閱讀 D 和 E...
發現 D 的 range 很大，不能直接 DP
而 E... 貌似很麻煩（同房 red WA 了好幾次）
但 D 真的一點想法也沒有...
我只有選擇做 E
想了一個直接構作方法...
至比賽結束前約 10 分鐘發現一個很難 handle 的 case
只好放棄...
System Test：
↑我也忘了... 是甚麼時候開始 System Test
這時看到 Scoreboard...
甚麼... 沒有人通過 C?!
↑看清楚一點...
按下 My Submission...
原來 System Test 還在進行中...
↑System Test 是按 Submission time 順序進行
由於 Testing 不是舜間完成
大家可以重溫 實時真實排名升跌
感覺很不錯 =v=
↑這是我房的 final standing
感想：
融合 SRM + ACM 的 Codeforces format 比賽感覺挺特別
(例如, 被 Hack 的 code 可以"復活")
可能是由於「Hack code 前必需 Lock code」
感覺大家都不太積極去 Hack 別人的 code...
也許，當將來競爭更激烈的時候
大家會更踴躍地 Hack
BTW... 倘若不是誤解規則...
在這場比賽或許我會進入"亂隊"模式...
沒有留言:
發佈留言