Topcoder SRM 492

這次是早上10am的SRM (感覺上好像早上的SRM我表現會比較好)
題目分數是250, 550, 1000 (感覺上對我不利, 因為通常我最多只能做450/500)

先看250, 是計算幾何問題
還沒有plan好便想開始code, 一開始亂了一段時間
最後還是窮試兩點和最左/右邊為0的情況
頗慢地完成了, 得到188.xx分
交完還是作了數個test case才放心少許
看看division summary發現排名大約100左右, 心情不錯

然後開550, 看明題目後沒有甚麼想法
搞了一會發現有些括號sequence的感覺, 再想想就相信可以用DP
不難想出一個n^5的DP, 不過認為過不到, 便再想去降低一個dimension
一開始想了一個錯的方法, 覺得雖不中亦不遠, 覺得腦袋又有些累就開始code, 這時還有30分鐘左右
code好發現差一個sample, 細trace一下發現我之前降低dimension的方法是錯的
再想想覺得沒有甚麼好方法, 便把1個DP function拆成2個DP (其實好像可以更優美地做, 不過當時沒有心情想了)
再搞兩搞過了sample便交, 得到27x.xx分, 這時好像還有7-8分鐘
作兩個test case渣一下灘便完了coding session
我的房裏只有兩人(包括我)交了550
看division summary當時排名好像是40左右

到challenge session很緊張, 很怕被cha死
由於我的550沒有信心, 250又不太有信心, 於是便決定基本上不作出challenge
雖然如此, 我還是看看其他人的code, 由於沒有心情看的關係看不到有誰的code感覺會錯
不久同房另一個550被cha死了, 令我更加緊張

到最後被呆等challenge session完再等system test, 這時看division summary排名大概是30

到system test很緊張, 看着上面的1000一個又一個的炒, 我自己的排名一個一個地升上去
終於看到自己pass了system test, 最後總排名16


Current Rating: 1810
不過rating這個東西還是easy come, easy go, 所以下次要繼續努力

Topcoder SRM 481

亦是慘烈的一次SRM, 亦再一次見証到topcoder的sample越來越弱

最近想算法好像有些慢, 頭腦不太靈活
不過不要緊, 只要ACM regional時去到最高狀態就可以了
現在最重要的是學更多東西令自己知識量增加, 狀態現在好也沒有用

入房發現和waihonhon同房, 當時還想不到這會對我有幫助 = =

250
有雞先定有蛋先的問題, 有人講大話, 有人收到流料, 很混亂
搞了一段時間只想到一些很不確的的方法, 類似看看difference然後再check parity
第一次submit只有16x分, 但心中仍很不確定algorithm的正確性
去洗手間時突然想起題目input的range不大, 可以用一個loop去試所有可能性
覺得這個方法一定正確, 比較有信心, 所以重新code了一次再resubmit
最後只剩11x分, 但對這段code非常非常有信心

500
又是expectation的題目, 有關process scheduling的
一開始花了少許時間證明了同一個user的process一定會group在一起的process
之後就是要計算任何permutation schedule的expected finishing time
這裏想了很久也想不到, 初時傾向DP, 但又不行, 搞了很久在最後7-8分鐘左右寫了一大堆公式, 把數拆開來算又搞了很久, 終於可以用有關2^n的formula算出expected value
寫完再處理整group有相同duration sum的人的排序, 但過不到sample
還有3分鐘, 找不到bug這樣就完結了

challenge phrase:
當coding完後gag guy大叫 "無用long long!" 於是我們便準備要用long long的test case
challenge一開始, 我由上至下看一次 (傻了)
前面的都有用long long/double, 看最後一個時好像有一個中間的variable沒有用long long
當我細心研究時已經被人cha掉了

之後傳出超超和chin的250被cha, 而我亦早覺得250危機四伏, 但我對自己的code還是很有信心
最後五分鐘突然想起我和waihonhon可以出test case互試, 如果不一樣就cha
leo頹說一個6, 5, 4, 3, 一試發現我和waihonhon不一樣!
再問問leo和gagguy的output, 再加上對自己的自信, 應該是我的正確waihonhon不正確
把這個test case對waihonhon作出challenge, challenge success!

分數由117升至167, 排名亦升了100左右
最後system test過了, 排名大約是250


PS1: 事後把第一次submit 250版本再交上topcoder practice room, 發現pass不到system test
PS2: 最後500的bug原來只有一個, 就是一開始把同user的process merge在一起考慮的時候搞錯了i和j, 把一個character改後立即過sample, 交上practice room亦pass了system test
PS3: 我500在比賽時搞的一大堆公式原來化簡後就是超超所說的1/2 probability亦是題目的重點

即是可以說假如250草率一點, 應該可以趕及做500

current rating: 1700
表現還有很多很多進步空間, 感覺上和之前連升幾次rating的時候差很遠

Topcoder SRM 452, 453.5, 454

SRM 452

入房驚見Petr, tourist, crazyb0y, LayCurse, yiuyuho, 心情有些驚嚇

普通速度完成了250, 得了240.x分, 之後看500, 是有些像dp, 又有些combinatorics的題目, 不懂, 就這樣等完場

challenge的時候, 看到petr出手cha掉幾個, 心中有些淆

大家大部份都只交了250, 500又不懂做, 不知道怎樣cha

唯有手打別人的code到自己機上測試, 試了一個測不出錯誤

打另一個的code, 發現有錯, 看看代碼, 好像沒有打錯, 大膽地challenge, 然後是unsuccessful....

由於只做了250, 由240.x -> 215.x... ranking大跌, 就是這樣由原本應該升rating變為跌rating了

細看發現自己打錯了一個constant, 結果改回後又那人的program果然真的好像沒有錯

之後發現petr把我之前手打測試過別人的code cha掉了 囧

最後我cha不到的code竟然過不到system test.....

這個SRM就在petr的氣勢下頹廢地結束了

============================

SRM453.5

這次入房更驚嚇, 有ACRush, Petr, marek.cygan, ahyangyi, rng_58, hhanger.....

強如ACRush也說了句"wow room 1"

250是典型BFS, 心想這次是發揮我coding能力的好機會, 可惜還是有頹bug, 拿了223.x分

450是有關plannar graph的題目, 首先想知道# of vertex為n的plannar graph, 最多有多少edge

立即想起euler's formula的e <= 3v-6, 但我不肯定是否一個tight的bound

上網找了一找, 找不到, 再想想又沒有其他想法, Petr, ACRush等又開始出題, 於是便開始code了

由於試過dp的complexity大約為3000x50000, 心想可能有些勉強, 於是便code了一個BFS

最後這題只拿了311.x分

1000開了題目看, 是lucky number的東西, 立即想起seerc08的一題, 又是由4和7組成的數字

有想過用inclusion-exclusion, 但lucky number又有>1000個, 2^1000恐怕差太遠了吧

再想了想lcm可能會glow得很快, 太大的可以剪枝剪掉, 又想起由大的開始試可以剪多一些

不過再想無論怎樣剪, 2^1000還是太勉強, 信心不足, 沒有開始寫

challenge的時候看見其他人500都是頹dp, 1000都是inclusion-exclusion......

看別人的250, 發現有人開細了array size, 立即gen了一個50x50的case把他cha掉

補償了500做得很慢的失誤, 挽救了我的rating

很感動地竟然可以在Petr, ACRush等人同房的時候還夠快cha到別人 =]

最後給billy看room summary的時候他還以為是division summary......

============================

SRM454

入房, 終於沒有Petr, 沒有其他target, 是比較和諧的一間房

250一如以往也比較簡單, 拿了240.x分

這是hackson msn傳來一句說winger resubmit了兩次, 叫我小心

於是花了些時間看看, 都覺得沒有甚麼問題

500是有關7-segment digit, 又或者是搬火柴砌數字的題目, noi曾經出過這類題目

不久想到了dp的做法, 一開始想hardcode每數字到每數字所需要移動的火柴數目和要增加的火柴數目

hardcode了1/10覺得實在太煩, 想到了簡單的hardcode方法, 把數字的形狀hardcode再去計算所需的資料也很簡單

寫完過不到sample, 花了一段時間發現自己想sprintf寫成了sscanf

還是過不到sample, 花了非常長的時間發現自己hardcode錯了一個number

還是過不到sample, 又花了非常長的時間發現自己hardcode錯另外一個number

過了sample, 試試速度, submit, 只剩下200.13

challenge phrase前計算過自己有本錢去cha人一次

又發現臨結束前2-3秒時有人提交500, 這題的數據又很容易出

於是一開波便看他的code, 看了10秒覺得沒有可能會正確, 決定challenge

很感動地出了一個challenge successful!!!

又補償了我500做得很慢的分數

之後再看其他500, 又好像沒有甚麼問題

發現有幾個人被cha了250, 但看剩下的又沒有甚麼問題

這樣就結束了, 最後剩下的code也全pass system test

============================

current rating: 1990

下次要上2000!!

回香港前希望可以上紅色

不過高處不勝寒, 還是要加強自己的實力

現在做到500是應該的, 要加強快做500的鬥志和信心

已經越來越難升rating了.....