Thursday, 30 September 2010
SRM 483
今次的SRM十分刺激, 過程峰廻路轉
一入房, 沒見到甚麼勁人
分數的分佈是 250 500 900
看完250, 由於 maxDen 十分小, 因此立即想到窮舉 A,B
搞左一輪, 慢慢的解決掉 (203)
之後不知為甚麼想先開 900, 看完題目後感覺不難
但有想過 900 不會這麼簡單, 懷疑佢 valid 的 range 並不是 [x,INF) 的 form, 於是寫左個 program generate test case 試, 得出來的結果又好像 work
又見很多人 submit 了 900, 於是便開始 code, 過程十分順利, 幾乎沒有錯, 過sample便submit了 (636)
由於做到900 心情很好, 便滿有希望地開 500
看完題目第一件想到的是 greedy 唔 work !
呃..
之後朝著 dp 的方向諗, 又真係好似可以用 dp
Define dp[i][left][right] = 第i個有left influence傳去左面和right influence 傳去右面
由於 500+500/2+500/4+... <1000, 所以大約是 N*10002
看起來很合理, 剩下15-20分鐘, 便很興奮地揼.. 啪啪啪
很順利的把 sample 都通過了, 在完場前3mins submit
做500的時侯已經想到很多人會用greedy做500!
所以 intermission 時已經出定 greedy 的 exceptional case
一開
果然有不少一看便知道不正確的方法, 不過估唔到連greedy都有好多種.. 有對 influence greedy 的, 有對影響人數 greedy 的, 有雙重 greedy 的.. 真係諗得出都有
看到一個用"double greedy"的, 睇明佢段 code 再諗左個反例, 由於做左3題, 因此當時很勇敢的 cha 下去
Challenge success
+50! 還想如果3題全過再加上 challenge 的分數就是一場完美的 SRM 了
可是, 突然發現自己的500被cha掉了, 灰哂
不過仍然無阻繼續嘗試cha別人的 code
差不多夠鐘時看到一個肯定錯的, 但又不太明白他在幹甚麼, 於是gen左一個大數據去cha佢, 可惜失敗, -25
最後以剩加分25結束
看divison summary, 很多人都提交了500級900, 其中900的submission比500還要多
而且自己也莫明奇妙的入了頭100(好似係)
system test 開始後不久, 就發覺唔係好妥.. 900果行放眼盡是 failed system test
再看看自己也是同一命運, 但很幸運地有+25 的優勢 (突然變得非常重要, 因為突然大剖份參賽者只pass了250), 居然還可擠進頭100
Rating 的升幅也是近數月來最大的, 而且創了新高
很莫明奇妙的一次SRM
Coding Phase
一入房, 沒見到甚麼勁人
分數的分佈是 250 500 900
看完250, 由於 maxDen 十分小, 因此立即想到窮舉 A,B
搞左一輪, 慢慢的解決掉 (203)
之後不知為甚麼想先開 900, 看完題目後感覺不難
但有想過 900 不會這麼簡單, 懷疑佢 valid 的 range 並不是 [x,INF) 的 form, 於是寫左個 program generate test case 試, 得出來的結果又好像 work
又見很多人 submit 了 900, 於是便開始 code, 過程十分順利, 幾乎沒有錯, 過sample便submit了 (636)
由於做到900 心情很好, 便滿有希望地開 500
看完題目第一件想到的是 greedy 唔 work !
呃..
之後朝著 dp 的方向諗, 又真係好似可以用 dp
Define dp[i][left][right] = 第i個有left influence傳去左面和right influence 傳去右面
由於 500+500/2+500/4+... <1000, 所以大約是 N*10002
看起來很合理, 剩下15-20分鐘, 便很興奮地揼.. 啪啪啪
很順利的把 sample 都通過了, 在完場前3mins submit
Challenging Phase
做500的時侯已經想到很多人會用greedy做500!
所以 intermission 時已經出定 greedy 的 exceptional case
一開
果然有不少一看便知道不正確的方法, 不過估唔到連greedy都有好多種.. 有對 influence greedy 的, 有對影響人數 greedy 的, 有雙重 greedy 的.. 真係諗得出都有
看到一個用"double greedy"的, 睇明佢段 code 再諗左個反例, 由於做左3題, 因此當時很勇敢的 cha 下去
Challenge success
+50! 還想如果3題全過再加上 challenge 的分數就是一場完美的 SRM 了
可是, 突然發現自己的500被cha掉了, 灰哂
不過仍然無阻繼續嘗試cha別人的 code
差不多夠鐘時看到一個肯定錯的, 但又不太明白他在幹甚麼, 於是gen左一個大數據去cha佢, 可惜失敗, -25
最後以剩加分25結束
System test
看divison summary, 很多人都提交了500級900, 其中900的submission比500還要多
而且自己也莫明奇妙的入了頭100(好似係)
system test 開始後不久, 就發覺唔係好妥.. 900果行放眼盡是 failed system test
再看看自己也是同一命運, 但很幸運地有+25 的優勢 (突然變得非常重要, 因為突然大剖份參賽者只pass了250), 居然還可擠進頭100
Rating 的升幅也是近數月來最大的, 而且創了新高
很莫明奇妙的一次SRM
Saturday, 25 September 2010
CodeForces Contest #30
題目
Scoreboard
很久沒有打 CodeForces 了, 今次見佢係新 style 又夾時間就玩下
server 還是很慢, 但至少還在可接受的程度
所謂的 CodeForces style可以看這
題目:
A - Accounting
解 A*Xn = B, 給出 A, B 為 -1000 到 1000 之間的整數, n 為 1 至 10 之間的整數, X 也要是整數
B - Codeforces World Finals
和日期有關的data processing
C - Shooting Gallery
普通的dp
D - Kings Problem?
看起來很有趣, 不過沒有精神去想
E - Tricky and Clever Password
沒看題目..
戰況:
今次的題目都比較直接, 不用想很久就有整個算法的 outline
但仔細做的時侯, 發現A有不少地方要小心處理, 所以完成時間比較慢, 而且還要錯了2棍 (有一棍 submit 錯 file )
由於 B 的題目太長因此跳過, 發現 C 是比較簡單, 少 trap 的 dp, 很輕鬆地完成了
看題 B , 其實也不太難處理, 只要小心一點就可以了, 大約一小時完成了三題
由於看到題 D 和 E 比較絕望, 以前的話一早去做其它事
但 CodeForces 的特點之一便是 coding 和 hacking (即 challenge) 是同時進行!
把 3 題都 check 一次便 Lock 起它們 (即不再 resubmit )
才可看別人的 code
看了幾個 A, 都有 overflow 的情況出現, 但找不到數據去炒佢
找到一段 A handle 錯了 X 為負的情況, 見佢幾短便打落自己部電腦試, 勇敢地按下 hack
Successful hacking attempt
+100, ranking 頓升了不少, 發現 hacking 是一個分數的重要來源 (比SRM 的+50分更有影響)
在臨完場時, 又發現有人沒有處理 B%A!=0 的情況, 又多100分
最後排52
感想:
比起 SRM, challenging 別人的 solution 的壓力似乎比較小
因為自己的 code 已經 pass 了 pre-test, 對自己的方法有一定信心
而且也不太需要擔心別人搶先 hack 掉, 因為一間房比較多人而且別人不一定在 hack
總括來說 hack 人頗划算的
不過今次要把別人的 code 打來試, 應該更有信心 hack 才是
Scoreboard
很久沒有打 CodeForces 了, 今次見佢係新 style 又夾時間就玩下
server 還是很慢, 但至少還在可接受的程度
所謂的 CodeForces style可以看這
題目:
A - Accounting
解 A*Xn = B, 給出 A, B 為 -1000 到 1000 之間的整數, n 為 1 至 10 之間的整數, X 也要是整數
B - Codeforces World Finals
和日期有關的data processing
C - Shooting Gallery
普通的dp
D - Kings Problem?
看起來很有趣, 不過沒有精神去想
E - Tricky and Clever Password
沒看題目..
戰況:
今次的題目都比較直接, 不用想很久就有整個算法的 outline
但仔細做的時侯, 發現A有不少地方要小心處理, 所以完成時間比較慢, 而且還要錯了2棍 (有一棍 submit 錯 file )
由於 B 的題目太長因此跳過, 發現 C 是比較簡單, 少 trap 的 dp, 很輕鬆地完成了
看題 B , 其實也不太難處理, 只要小心一點就可以了, 大約一小時完成了三題
由於看到題 D 和 E 比較絕望, 以前的話一早去做其它事
但 CodeForces 的特點之一便是 coding 和 hacking (即 challenge) 是同時進行!
把 3 題都 check 一次便 Lock 起它們 (即不再 resubmit )
才可看別人的 code
看了幾個 A, 都有 overflow 的情況出現, 但找不到數據去炒佢
找到一段 A handle 錯了 X 為負的情況, 見佢幾短便打落自己部電腦試, 勇敢地按下 hack
Successful hacking attempt
+100, ranking 頓升了不少, 發現 hacking 是一個分數的重要來源 (比SRM 的+50分更有影響)
在臨完場時, 又發現有人沒有處理 B%A!=0 的情況, 又多100分
最後排52
感想:
比起 SRM, challenging 別人的 solution 的壓力似乎比較小
因為自己的 code 已經 pass 了 pre-test, 對自己的方法有一定信心
而且也不太需要擔心別人搶先 hack 掉, 因為一間房比較多人而且別人不一定在 hack
總括來說 hack 人頗划算的
不過今次要把別人的 code 打來試, 應該更有信心 hack 才是
Subscribe to:
Posts (Atom)