亦是慘烈的一次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的時候差很遠
