亦是慘烈的一次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的時候差很遠
2010年9月11日 星期六
2010年7月31日 星期六
NWERC 2009 - Common Subexpression Elimination
原題: http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4610
很經典的compiler優化
這題解法的algorithm我上compiler課的時候還在想"這麼簡單的東西為甚麼要上課教"
一開始的想法是先build tree, 然後再traverse一次tree去找答案
麻煩的地方是node ID要順出現的次序, 但這題需要construct方法卻是從desendent做起
首先parse input的時候有很多bug, debug了一段時間 (~10mins)
找答案時亦出現了coding細節的小錯誤
之後終於搞好, submit得到TLE
想了想發現可以一個pass做完, 可以一邊parse一邊找答案
改好再交, 得到仍是TLE
之後再搞, 發現output可以不用C++的string, 麻煩地改為C string
改好再交, 得到仍是TLE
再搞了很久仍想不到有效的優化, 放是放棄, download testdata和看solution
發現我的program run official testdata需要4x秒
再run official solution, 最慢的亦只需12秒
於是研究一下official solution, 有自己寫hash, 有用非STL的rope, 亦有看不懂
再細心看看, 有些不明白的地方, 回看題目, 發現每個node最多只會有兩個children!
所以每個node的representation可以用一個long long去encode, 而不一定要用string
改了少許覺得很煩, 又覺得差別不會很大, 於是又沒有改
找會最初最簡單的code從新優化
嘗試把sscanf轉成自己食string, 再run發現program由4x秒加速至7秒!
再交上live archive, 竟然又再次得到20秒的TLE....
於是把之前的優化加上, 盡量少用STL string, 多用C string
再試official testdata, 只需6秒
再次submit, 終於accept了
這題做得太差了, 以這個進度5小時的比賽不會有時間做這題
做得很慢, 很多bug, 而且看漏了題目, 又優化很久才過
很經典的compiler優化
這題解法的algorithm我上compiler課的時候還在想"這麼簡單的東西為甚麼要上課教"
一開始的想法是先build tree, 然後再traverse一次tree去找答案
麻煩的地方是node ID要順出現的次序, 但這題需要construct方法卻是從desendent做起
首先parse input的時候有很多bug, debug了一段時間 (~10mins)
找答案時亦出現了coding細節的小錯誤
之後終於搞好, submit得到TLE
想了想發現可以一個pass做完, 可以一邊parse一邊找答案
改好再交, 得到仍是TLE
之後再搞, 發現output可以不用C++的string, 麻煩地改為C string
改好再交, 得到仍是TLE
再搞了很久仍想不到有效的優化, 放是放棄, download testdata和看solution
發現我的program run official testdata需要4x秒
再run official solution, 最慢的亦只需12秒
於是研究一下official solution, 有自己寫hash, 有用非STL的rope, 亦有看不懂
再細心看看, 有些不明白的地方, 回看題目, 發現每個node最多只會有兩個children!
所以每個node的representation可以用一個long long去encode, 而不一定要用string
改了少許覺得很煩, 又覺得差別不會很大, 於是又沒有改
找會最初最簡單的code從新優化
嘗試把sscanf轉成自己食string, 再run發現program由4x秒加速至7秒!
再交上live archive, 竟然又再次得到20秒的TLE....
於是把之前的優化加上, 盡量少用STL string, 多用C string
再試official testdata, 只需6秒
再次submit, 終於accept了
這題做得太差了, 以這個進度5小時的比賽不會有時間做這題
做得很慢, 很多bug, 而且看漏了題目, 又優化很久才過
2010年7月16日 星期五
NOI集訓隊論文
近日突然發現kn的blog有連結到我的blog, 覺得很久沒有打blog又佔用了連結位置很不好意思
, 於是便隨便打一些東西
最近一個月看了/在看好幾份NOI集訓隊冬令營的論文: (有很多都是略略明白大意/較有用的部份就算了, 沒有細心看)
HBT的minimum cut
QZC的divide and conquer on tree
YHC的matrix multiplication
CDQ的插頭DP
GYH的discretization on circle
CQF的放寬約制
等等, 有些比較喜歡, 有些比較不好看
個人認為要選出比較好看的論文, 主要還是看作者的名氣, 很多強勁出名的選手通常都寫得不錯
又或者是女選手的作品, 也會比較淺白易明
遺憾的是有很多看題目覺得有趣的論文, 作者都有一定程度的語癌
, 於是便隨便打一些東西
最近一個月看了/在看好幾份NOI集訓隊冬令營的論文: (有很多都是略略明白大意/較有用的部份就算了, 沒有細心看)
HBT的minimum cut
QZC的divide and conquer on tree
YHC的matrix multiplication
CDQ的插頭DP
GYH的discretization on circle
CQF的放寬約制
等等, 有些比較喜歡, 有些比較不好看
個人認為要選出比較好看的論文, 主要還是看作者的名氣, 很多強勁出名的選手通常都寫得不錯
又或者是女選手的作品, 也會比較淺白易明
遺憾的是有很多看題目覺得有趣的論文, 作者都有一定程度的語癌
2009年12月16日 星期三
ZJU3280 - Choose The Best
Cannot solve it in contest, and Hackson solve this afterwards.
The idea is observing that in Manhattan distance, the absolute value |x1-x2| can be rewrite as (x1-x2) or (x2-x1). We can do exhaustion on the sign of each dimension, sum up the value of each dimension, and find the maximum and minimum. The maximum difference between them for all cases would be the answer.
An interesting and useful technique to due with problems with absolute values or manhattan distance.
2009年12月6日 星期日
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了.....
2009年11月25日 星期三
PKU3420 - Quad Tiling
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3420
Typical DP problem when N is small.
In this problem, N can be as large as 10^9, so matrix multiplication should be used. Unlike the problem I've done before, this time the matrix is as large as 16x16 (because there is 2^4 number of states at each layer). I write code to pre-generate the 16x16 matrix instead of hard-coding the formula, and then do matrix multiplication as usual.
2009年11月20日 星期五
PKU3135 - Polygons on the Grid
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3135
An exhaustion problem.
The solution is well known, but this is a good problem for me to practice my exhaustion skills.
We can pre-compute the all possible placement on the grids for specific length sticks. In the worst case, there is 36 possible placement on the grids, which is small and we can do exhaustion on different placements.
Here is some skills for cut-case:
1. Fix the longest stick to be the first one, and try permutations for other sticks.
2. Check whether the sticks left are not long enough to reach back to the origin. Otherwise, cut this case.
3. After putting n-1 sticks, the length to the origin must be equal to the length of the last stick. Otherwise, cut this case.
4. We can fix the direction to put the first stick to be in the first region (x,y are positive)
5. Because for the first stick, it is symmetric for (y,x) and (x,y) cases arrangement, we can only try one of them.
Another thing is that do not use STL pair when doing these problems.
An exhaustion problem.
The solution is well known, but this is a good problem for me to practice my exhaustion skills.
We can pre-compute the all possible placement on the grids for specific length sticks. In the worst case, there is 36 possible placement on the grids, which is small and we can do exhaustion on different placements.
Here is some skills for cut-case:
1. Fix the longest stick to be the first one, and try permutations for other sticks.
2. Check whether the sticks left are not long enough to reach back to the origin. Otherwise, cut this case.
3. After putting n-1 sticks, the length to the origin must be equal to the length of the last stick. Otherwise, cut this case.
4. We can fix the direction to put the first stick to be in the first region (x,y are positive)
5. Because for the first stick, it is symmetric for (y,x) and (x,y) cases arrangement, we can only try one of them.
Another thing is that do not use STL pair when doing these problems.
訂閱:
文章 (Atom)