題目連結: http://acm.timus.ru/problem.aspx?space=1&num=1424
CUHK training時隨手選出來的題目, 想不到也挺符合我們這星期的大主題greedy algorithm
題意很簡單, 就是generalized的activity selection
由每個時間只可選一個interval改為每段時間最多可以選M個interval, 問最多可以選多少個interval
同時可以有M個interval, 一共可選擇的interval共有N個
細心想想, 就會知道原來的greedy方法仍然是正確的: 跟據結束時間排序之後貪心地選
一開始想到做M次activity selection, 但這樣的time complexity會是O(MK), 應該會超時
再想就覺得可以維護一個list儲着最後M個interval的結束時間, 然後選最接近而少於現在的starting time的interval去replace
既然要用Binary Search Tree, 就先去想想可不可以用STL的set
發現我們需要的操作有insert, delete, 和query largest integer which is less than or equal to k
STL明顯可以做到這些操作, 由於裏面的數有可能重覆, 所以需要用multiset
留意STL的Binary Search Tree也有upper_bound和lower_bound的功能
只要想清楚upper_bound和lower_bound的分別就可以漂亮地解決
假如想不清楚的話都可以用iterator去在BST中微調而找出想要的element
這題也算是練習Greedy和STL中比較有趣的題目
2011年6月24日 星期五
2011年6月22日 星期三
UVA 12035 - War Map
題目連結: http://uva.onlinejudge.org/external/120/12035.html
此題出自 Bangladeshi national Contest, kn看到後覺得有趣又不太懂做便叫我去做這題
題目雖然不是很難, 但做出來還是很有成功感, 所以很興奮的把這題寫下來
題意很簡單, 就是問從vertex特定的degree sequence可否形成一個bipartite graph
一開始會發現N<=20, 就會從枚舉每點屬於bipartite graph的可能性再試可否形成一個bipartite graph
測試可否形成bipartite graph的一部分不難想到可以用maximum flow去解決
這樣的速度大概是 O(2^n * n^3), 而測試數據有500個, 明顯會超時
繼續向這個方向想, 發現該二分圖的左邊和右邊的degree sum必定相等, 否則肯定不能組成一個合理的graph
加了這個checking後應該可以排除很多case, 做少很多次maximum flow
交這個上去也是得到TLE, 而且經過測試後發現計算所有subset of vertex的degree sum已經用了大部份的時間
這題time limit只有一秒, 時限算是非常緊
這是開始去試一些大的test case, 就像20個點每點的degree都是19, 很明顯不能組成bipartite graph
如果暴力試所有點的subset的話, 就會有很多相同的degree sequence要試 (左邊10個19, 右邊10個19)
但事實上應該可以知道該sequence是一樣而不用再試
因此我們可以把相同的degree group在一起, 在暴力分左右時把該degree某個數量的vertex分到左邊
這樣就可以避免重覆地試相同的degree sequence
以這個方法用recursion有技巧地試就以0.857s Accepted了
再想發現我的program很多時候會試多了一倍的可能性, 因為相同的subset會被放到左邊或右邊各一次
因次再加上假如是在試第一個vertex時, 最多只有一半的vertex被分到左邊, 就可以減少試一半的case
加了這個optimization之後以0.476s Accepted
不知道還有沒有更好的方法解決這條問題呢?
此題出自 Bangladeshi national Contest, kn看到後覺得有趣又不太懂做便叫我去做這題
題目雖然不是很難, 但做出來還是很有成功感, 所以很興奮的把這題寫下來
題意很簡單, 就是問從vertex特定的degree sequence可否形成一個bipartite graph
一開始會發現N<=20, 就會從枚舉每點屬於bipartite graph的可能性再試可否形成一個bipartite graph
測試可否形成bipartite graph的一部分不難想到可以用maximum flow去解決
這樣的速度大概是 O(2^n * n^3), 而測試數據有500個, 明顯會超時
繼續向這個方向想, 發現該二分圖的左邊和右邊的degree sum必定相等, 否則肯定不能組成一個合理的graph
加了這個checking後應該可以排除很多case, 做少很多次maximum flow
交這個上去也是得到TLE, 而且經過測試後發現計算所有subset of vertex的degree sum已經用了大部份的時間
這題time limit只有一秒, 時限算是非常緊
這是開始去試一些大的test case, 就像20個點每點的degree都是19, 很明顯不能組成bipartite graph
如果暴力試所有點的subset的話, 就會有很多相同的degree sequence要試 (左邊10個19, 右邊10個19)
但事實上應該可以知道該sequence是一樣而不用再試
因此我們可以把相同的degree group在一起, 在暴力分左右時把該degree某個數量的vertex分到左邊
這樣就可以避免重覆地試相同的degree sequence
以這個方法用recursion有技巧地試就以0.857s Accepted了
再想發現我的program很多時候會試多了一倍的可能性, 因為相同的subset會被放到左邊或右邊各一次
因次再加上假如是在試第一個vertex時, 最多只有一半的vertex被分到左邊, 就可以減少試一半的case
加了這個optimization之後以0.476s Accepted
不知道還有沒有更好的方法解決這條問題呢?
2011年6月16日 星期四
ACM ICPC World Finals 2011 - Orlando 比賽過程 + 感想
拖了很久,越寫越長,但還是要發出來。比賽過程其實也不太記得清楚,都是看着不同時間的scoreboard回憶起來的。
Final scoreboard: http://cm.baylor.edu/scoreboard/
比賽前心情不算很緊張,只是又要在門口聽Bill叔叔說一大堆廢話。有practice contest的教訓,我和kn特地提醒CTLi比賽的時候專心想題目,有甚麼硬件或機器的問題由我和kn處理。
比賽一開始和平時訓練差不多,kn打code template,我拆題目和把題目分類。看到有坐標的題目便分給kn,發現kn分到了5題,當時卻沒有想過整份題目卻沒有甚麼需要geometry技巧。看到有隊過題K,kn一看便想到做法,立即上機很快便通過了題K。
23 min: Problem K - Simple Geometry (kn)
過K之後不久CTLi上機做G,大家都沒有想過這就是悲劇的開始。這時我看了題H和題D,題H暫時沒有想法,題D很有flow的味道,但暫時沒有想到可行的算法。看到兩題graph都不太懂做,這時有少許緊張。因為最害怕會發生的情況好像有機會發生:有難的graph題目而我不太懂做,kn和CTLi又不熟graph thoery。看看scoreboard我們發現清華過了題C,一看題目就很明顯是kn的類型(data processing + pattern recognition)。kn解明白題目後很快便想到去數空白部份數目的算法,他看清楚後覺得有信心便繼續去想題E。題E是類似打斜45度的正方形的partial sum,我想了想覺得很麻煩,雖然已經有隊過了這題但也沒有再想。回頭繼續研究我的題H。
CTLi的題G搞了很久都過不到sample,貌似是binary search時永遠到出了infinity。這時畫完sample出來後我已經想到題H的做法,就是找出leaf的biconnected component感覺還挺肯定是正確的。CTLi的題G又沒有甚麼進度,於是我便開始上機做題H。上機的途中也不是很順利,中途和CTLi交替了幾次上機和debug,kn也好像在中途開了很多隊已經過了的題C來做。這時比賽到60分鐘左右很多隊已經有三題,而很明顯我們的開局不太順利,但想起立志賽前說當年waterloo都是89分鐘才出第一道題而最後過了7題,又看見對面中山一題也沒有,我還是挺冷靜的。不久CTLi的題G終於通過sample,提交卻得到Wrong Answer(WA)。我的題H也很快過了sample,提交也是WA。這時候終於有機會給kn專心上題C。過了十分鐘發現沒有處理整個graph是一個biconnected component的情況,改完再交還是WA。又過了十幾分鐘kn的題C通過了sample提交也是WA,而CTLi的題G再改還是WA。我的題H幾本上絕望,看了很多次也找不到任何bug。我便轉看有不少隊通過了的題J和繼續想肯定是flow的題D。
kn的題C和CTLi的題G再交仍然是WA,於是我便問一下kn的狀況。他說他發現物件接觸到邊位時有機會會錯,想外加一層空格去處理。我想了想發現kn的方法會處理錯只有一件物件的情況,和kn討論一下得出解決方法。花了一些時間再改再錯多了一次便終於通過題C了。不過題G和題H的WA仍是沒有任何idea去解決。
109 min: Problem C - Flood Fill (kn; 3WA)
之後kn和CTLi討論一會兒後便想開始做題E。kn跟我說他的做法但我聽不明白,而我亦覺得他的做法很麻煩,不過他說他有信心便由得他去做了。CTLi的題G搞了搞還是過不到,而題A又開始有不少隊通過,於是我便叫CTLi研究題A。這時候我看完題J覺得規模很大沒有想法,便一邊看看題H又一邊再想想題D。過了不久kn的題E有bug而CTLi的題A好像想到做法,於是又開始交替地寫。在比賽150min左右(比賽時間的一半了),kn通過了題E的sample,過了sample後好像有些慢,我建議kn將memset改為for loop去initialize。這時候我不知道kn在想甚麼,竟然落機和CTLi討論一大輪後想重寫。[這大概也是我們隊策略和teamwork的失誤,代表這也是我的錯誤] 心急的我很不滿地問他們甚麼情況,然後決定先交一下kn已經通過sample的program,結果得到Runtime Error。他們討論完後kn決定重寫,不久CTLi的題A也寫好通過sample了,在這個情況當然立即提交,得到WA。他們兩人寫了寫又要落機研究,而我又不想電腦空着,所以我便在這段時間開始寫題D的dinic武器。(這個時間我們隊是同時開了五題來做,絕對破了我們自己在任何比賽或training的紀錄)幸好,不久之後kn找到了題E的bug,改完通過sample再交,終於把這題過了。
171 min: Problem E - Coordinate Transform + Partial Sum (?) (kn; 1WA)
這時候我把題J的想法告訴kn,讓他準備用最簡單的DP頹做。我提出實際狀態可能很少,用vector之儲可達到的狀態可能可以大大加速,CTLi卻不太贊成。我也不理太多,認為有這麼多隊通過,算法必然很簡單,而我又找到頹greedy的反例。於是kn便看題目和準備preprocessing的地方。寫完dinic後過不到sample,改了改才發現我理解錯了題目,有一個重要的constraint一時想不到解決方法,唯有落機讓CTLi繼續改他的題A,我亦再看看我們沒有人看過的題I。經過幾次WA,CTLi還是穩住地把題A通過。
200 min: Problem A - Greedy (CTLi; 3WA)
CTLi:“well,終於有少少貢獻啦。”
Joe:“咁你即係話我無貢獻啦。”
CTLi:“well...”
CTLi過了A後,他認為kn的題J寫得有些問題,可能會比較慢,在CTLi不停口說很慢但我又聽不明白他的解決方法下,我便果斷決定讓CTLi接手做題J,然後讓kn幫我再看一次題H。kn看完題H認為我沒有看錯題,所以還是沒有idea錯甚麼,唯有找時間和kn討論我的題H。kn不太明白我的做法,當我解釋時突然就發現了自己的特別處理有問題。立即趕走CTLi搶機來改,這時我緊張得有些手震,改完交後傳來一個WA,淡定想起特別處理沒有用long long,立即再改再交,仍是WA,心情再次受到打擊。而我這時看scoreboard已經可以知道拿牌必定要7題,因此我們除了題J和題H外必須再過多一題。CTLi的題G好像已經放棄了,而kn說題B是簡單的暴力和幾何,於是我便叫kn開始準備去寫題B。不久,CTLi的題J已經寫完但過不到sample。這時其實好像大家腦筋也不太冷靜,在大家的協助和混亂下過了一段時間終於改好通過sample,提交後compile和run了很長時間終於過了我們的第五題。
231 min: Problem J - DP (kn + CTLi)
過了題J後,我說了題I的題意給大家聽,一致贊成立即放棄這題,然後我立即讓CTLi重新研究一開始過不到的題G。我的題H還是沒有頭緒,太沮喪的情況下搶過機來,測試我biconnected component的部份有沒有問題,然後好像發現有一些邊是從來沒有被分到任何一個biconnected component。[註:其實我的武器沒有問題,只是做checking的地方寫錯了] 這時我完全沒有信心去改正我這部份的code,於是想了另一個做法不需用biconnected component讓kn幫我重新寫一次。kn寫完後發現有問題,debug時驚訝地發現連n的數值也錯了。看一看code發現我找n的值時竟然寫了n=max(x,y),而正確的應是n=max(n,max(x,y))。修改後kn寫的新版本還是錯,我修改我舊版本的code再交一次,終於得到了ACM生涯最悲劇的Accetped。
249 min: Problem H - Biconnected Component (Joe; 6WA)
過完題H終於到了6題趕上大隊,只要拚出多一題就大概能拿牌。最後50分鐘kn主力上題B,CTLi中途好像重新有idea錯甚麼,間中搶機改code再交。kn說題B很多細節怕看錯題目,叫我重新看一次題目。題目很長很煩,而我的精神和心情仍是很混亂的狀態,花了一段時間看明白題目,和kn討論後改正了他很多地方對題目的理解。到最後十五分鐘還有接近一半未寫好,預計之後還需要調試,而我又覺得kn某些地方的做法不正確,根本沒有可能完成,於是便叫kn放棄題B,轉而讓CTLi用機怒交題G。很可惜到最後我們的題G都是在WA和TLE之間始終過不到,比賽就始結束。
比賽完結後十分失望,頹坐在椅子或地上坐了很久,直至立志進來。他的印度朋友來恭喜我說我們表現很好,我都不知道怎樣答他。本來在隊中應是最需要穩定和提供支援的角色,到最終卻因為自己的低級失誤拖累了整隊的發揮。這也許是我唯一一次比完賽有想哭的感覺吧。這種失落比08年成都的灰心大很多很多。
雖然對整場比賽哪一隊領先哪一隊表現較好完全沒有感覺,但也覺得清華輸了很可惜,看到Michigan爬過清華的時候周冬他們的表情時,除了為自己的難過外也仿佛感受到他的難過。比賽前我心中的大熱是台大Warsaw和清華,但最後好像三隊的表現都不太滿意。最後冠亞軍竟然是爆大冷的浙大和Michigan,輸了給以前嬴過的對手感覺更差 (雖然自己和對手的隊友都已經完全不同)。
事後自我檢討我們這場比賽爭牌失敗(除了實力和運氣外)的原因和這場比賽做得不好的地方:
- 比賽中第一個技術性失誤應該是kn的題E寫完後才和CTLi討論結果要重寫。中途由於我和CTLi的各自卡題導致kn要孤獨作戰而陷入一個很複雜的想法,事實上假如一早找CTLi談幾句的話這題應該會順利很多。
- CTLi卡題G的時候我和kn從頭到尾都沒有幫手。比賽中途我理解題目後曾給CTLi建議試一試O(n^3)的簡單DP,但後來到我過題H前後也望過CTLi的code但感覺是我不可能理解的算法。我們完全也沒有意識去幫CTLi,某程度上都是因為CTLi沒有找我們幫手。不過回想起來,在訓練中好像沒有CTLi做不到的題目,而CTLi從來沒有主動找我們幫忙。事實這題目遠比我想像中簡單,而我相信我亦有在這題找出一些observation和幫忙CTLi debug的能力。
- 最後一小時開題B的決定其實很值得商確。kn當時還是很沒有把握,題目有很多地方他也理解得不清楚,因此到後來需要作出很多修改。當時完全失去信心的我沒有意識到我題D的flow model已經是非常接近,事實上只要再加一層exhaustion就能完美解決我早前看錯的constraint而解決題目。假如我繼續去攻題D會否有更大機會過題?這永遠是一個謎。
- 到比賽前的最後一星期,我似乎都未能把ManiAC的狀態調較到最好位置。出發前一星期做南韓regional時某程度上已嚴重反映狀態不足的問題,而當時我亦非常明白這個情況。之後來到Orlando做練習時大家還是有很多很多的卡題和無聊失誤,但無輪是出發前一星期或是出發後我也是沒有辦法解決這個問題。
到後來我總覺得這次比賽中team work和策略上做得很差,有很多決定都好像做得不夠好。比賽從最初選錯題和卡題開始,我們已失去了平時的節奏。大家在比賽中從頭到尾好像都沒有靜下來慢慢想題目的時間,這也是我們在最後一小時出不到題的其中一個原因。我們三人以往比賽經驗都未能令我們在最後關頭作出正確的決定。不過也許如果沒有以往比賽的經驗,我們隊早在同時卡五題的時候就崩沮了。
我們隊三人都是老隊員了,也都是第二次參加World Final。對於World Final上的一切事也不太覺得新奇,在比賽前幾天所有活動中都能很集中於比賽中。記得兩年前在瑞典看到Petr的時候還大驚小怪然後要和他合照,今年幾乎每天也看到Petr但已經沒有甚麼感覺了。從比賽角度上看,假如和上一次Stockholm的World Final比較,雖然同樣是悲劇,可能因為上一次的期望和信心不太大,而這次目標只有拿牌,而且真的因為自己的錯而拖累了隊友,所以失望的感覺非常大。比賽後亦沒有當年沒有懷念KTH library的氣氛和感覺,只記得自己在比賽時過題H之後崩沮地躺在地氈的感覺。
我們大概在World Final一年前組成ManiAC,也好像是香港中大ACM team有史以來第一隊三個人也是第二次入World Final的。隊友kn是主力coding的隊員,專長於幾何,搜索和模擬題。CTLi的coding較慢,但對數學和算法非常有信心,總能把複雜的DP和數學題解決,有時候對題目又可以有些很創新的解法(如Kuala Lumpur 2010最後一題的E),對於幾何題有很多時候都能給出很有用的意見,是我們的皇牌武器。而我的特性就在兩人之間,比較特殊的能力可能就是做過類似的題目會很有印象吧。
由於我們的特性,比較容易的題目會多由kn去做,較難的題目會給CTLi去想,而我就卡在中間,主要去做些要花時間想但又不需要用到CTLi想的題目,和協助kn去做麻煩的題目。因此在較多的訓練後已經逐漸演變成我較少coding的情況。在訓練當中通常都是擔當支援的角色。除非有很多graph題,否則正常情況都是我用機時間+做題數量都是我最少的。
我們隊其中一個特點是絕對的信任隊友,就是在開始階段假如隊員說很有信心的時候通常都不會過問,直至提交後過不到。這個策略也許是我們這次比賽做得很差的原因,但我自己也沒有後悔的,因為想拿牌就要進取一點,這次運氣差賭輸了也沒有辦法。
我們這隊ManiAC是完全為了World Final而組成的。由於World Final要求的coding能力非常高,而歷年的試題中亦有很多幾何題。因此我們早在一年前訓練的時候已針對麻煩或是幾何的題目投放很多的時間去熟習,直至對這些題目有信心,而對算法的思考可能卻不是特別出眾(但也不弱)。可惜這次World Final的題目的題型卻是意料之外,連judge的其中一員Per也在他的題解說這份題目是“unusually geometry-free problem set”,因此其實我們特別為WF組成的隊型在這次比賽中發揮的空間不是太多。做這份題目,的確我們隊比起其他強隊沒有太大優勢。
寫完這篇總結,比賽已經過了差不多兩個星期,遺憾的感覺已經淡化了很多。不過每回想起來總覺得這次的表現實在是差得不能再差,做出6題其實完全沒有難度,即使只是中大以往幾年的一隊的能力都應該可以做到。最後我們的能力就只是用於挽救一連串不幸事件的危機,感覺有點可惜。
World Final已完,這樣就退役了,還有甚麼想說的就遲些在寫吧,退役文後補。
2010年12月29日 星期三
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, 所以下次要繼續努力
題目分數是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, 所以下次要繼續努力
2010年12月22日 星期三
[轉載] 復旦某前輩對今年ACM Team的訓話
說得太好了
希望以後的隊員明白, 出去比賽是要肩負起為cuhk拿獎爭光的責任, 並不是去旅行去給cuhk丟臉
你代表的並不只是自己的隊, 而是背後所有支持信任你的老師和同學
===========================================================
诚然,每年关于ICPC WF出线的问题没有哪一次不在复旦ACM队里闹得鸡飞狗跳。关于今年
的什么什么PK之类的问题,我不得不说几句丑话。
其一,争夺出线资格本来没有错。但是,我很希望小队员们不要曲解了“出线”的含义。
代表复旦“出线”绝对不是荣誉的象征,它是代表你将挑起为学校在总决赛上斩获荣誉的
责任。在我眼里,与其去当着世界三百位选手丢尽复旦的颜面,还不如加把劲今后在国内
赛区得点金奖。
其二,ICPC的规矩奇葩不是什么新鲜事了,不必醉心于怨天尤人。历史上复旦在某地丢掉
冠军只有一次,那就是当年的南京赛区冠军,当年的总决赛队。今年国内赛区的成绩还望
各位现役队员能够深刻反省,“期中考试”,“状态不好”之类的人民日报新闻联播式的
理由就不必拿出来了,全国所有的大学都要期中考试,总决赛也不会专门安排在你“状态
好”的时候。
其三,今年出线的队希望居安思危,认清形势也认清自己,明白身上的责任;没有出线的
队也不必再提什么PK什么被黑了。还是那句话,如果PK的话我跟FGD不会缺席的,你们自己
掂量。
难听的话说了这么多,还是衷心希望小队员们能端正态度,明确使命,做当之无愧的复旦
“一队”。没有出线的队伍也不必嚷爹骂娘,好好想一想,自己真正输的是什么……
http://blog.renren.com/blog/246784220/702543083
希望以後的隊員明白, 出去比賽是要肩負起為cuhk拿獎爭光的責任, 並不是去旅行去給cuhk丟臉
你代表的並不只是自己的隊, 而是背後所有支持信任你的老師和同學
===========================================================
诚然,每年关于ICPC WF出线的问题没有哪一次不在复旦ACM队里闹得鸡飞狗跳。关于今年
的什么什么PK之类的问题,我不得不说几句丑话。
其一,争夺出线资格本来没有错。但是,我很希望小队员们不要曲解了“出线”的含义。
代表复旦“出线”绝对不是荣誉的象征,它是代表你将挑起为学校在总决赛上斩获荣誉的
责任。在我眼里,与其去当着世界三百位选手丢尽复旦的颜面,还不如加把劲今后在国内
赛区得点金奖。
其二,ICPC的规矩奇葩不是什么新鲜事了,不必醉心于怨天尤人。历史上复旦在某地丢掉
冠军只有一次,那就是当年的南京赛区冠军,当年的总决赛队。今年国内赛区的成绩还望
各位现役队员能够深刻反省,“期中考试”,“状态不好”之类的人民日报新闻联播式的
理由就不必拿出来了,全国所有的大学都要期中考试,总决赛也不会专门安排在你“状态
好”的时候。
其三,今年出线的队希望居安思危,认清形势也认清自己,明白身上的责任;没有出线的
队也不必再提什么PK什么被黑了。还是那句话,如果PK的话我跟FGD不会缺席的,你们自己
掂量。
难听的话说了这么多,还是衷心希望小队员们能端正态度,明确使命,做当之无愧的复旦
“一队”。没有出线的队伍也不必嚷爹骂娘,好好想一想,自己真正输的是什么……
http://blog.renren.com/blog/246784220/702543083
2010年12月20日 星期一
PKU 3725 - I know the k-th integer
有趣的題目, 因為我實力不足的關係花了我幾天去想和寫和改良
這題我第一個想去就是想去binary search答案, 再看發現的確可以binary search
於是便寫了個binary search, 再找given一個n, 第k個數是多少
這個問題也不簡單, 但也不難, 花了一段時間寫完+debug, 再交得到TLE
看看discuss, 好像需要沒有binary search的做法才會不TLE, 於是再想想發現的確可以不binary search
詳細的details我想得很麻煩, 無謂寫在這裏
主要的想法就是一個一個digit去試, 直至找到most significant digit
大家花少許時間就會想到, 最後通過了之後再交PKU 2171, 竟然過不到
發現是<=和<搞亂了, 沒有詳細想清楚, 證明有些細節不想清楚的話, 雖然自己測試測不到, 但交上去還是會錯的
這題最後寫了很多個版本, 就等於做了幾道題目
不過對這類題目處理還是寫得不夠好, 想得也很慢, 希望WF之前可以改進
這題我第一個想去就是想去binary search答案, 再看發現的確可以binary search
於是便寫了個binary search, 再找given一個n, 第k個數是多少
這個問題也不簡單, 但也不難, 花了一段時間寫完+debug, 再交得到TLE
看看discuss, 好像需要沒有binary search的做法才會不TLE, 於是再想想發現的確可以不binary search
詳細的details我想得很麻煩, 無謂寫在這裏
主要的想法就是一個一個digit去試, 直至找到most significant digit
大家花少許時間就會想到, 最後通過了之後再交PKU 2171, 竟然過不到
發現是<=和<搞亂了, 沒有詳細想清楚, 證明有些細節不想清楚的話, 雖然自己測試測不到, 但交上去還是會錯的
這題最後寫了很多個版本, 就等於做了幾道題目
不過對這類題目處理還是寫得不夠好, 想得也很慢, 希望WF之前可以改進
ACM Kuala Lumpur Regional 2010 感想
我的最後一個regional比賽
終於,終於,拿到了期待已久的champion
某種感動週期性地在腦海中徘徊
其實在比賽前,我完全沒有想過可以拿champion
不知道為甚麼,我在jakarta的比賽前真的覺得有機會拿冠軍,但今次旅程卻沒有甚麼感覺。
在比賽中途,因為中段大家的失誤,令我亦完全沒有幻想有機會拿冠軍。現在的感覺真的很難以置信。
有人問我們隊玩ACM有甚麼秘訣,忍不住答了teamwork。
隊友的合作和支持真的非常重要。
亦非常感謝大家在香港的支持。
香港中大在ACM的名聲一年比一年響。
自從我們E++和++Zz;在大陸賽區頭段表現出色,到去年Intuition在寧波拿了第三
而今年Jakarta的射雕+放雕亦令大家緊張了一段時間,之後在twitter也有人討論我們
導致TJU看到我們大學的名後便問我們是不是香港中大,是不是jakarta第三 (雖然之後他們發現CDQ後便無視我們了)
相信在今年,CUHK的名字終於在大家心中留下深刻印象吧。
終於,終於,拿到了期待已久的champion
某種感動週期性地在腦海中徘徊
其實在比賽前,我完全沒有想過可以拿champion
不知道為甚麼,我在jakarta的比賽前真的覺得有機會拿冠軍,但今次旅程卻沒有甚麼感覺。
在比賽中途,因為中段大家的失誤,令我亦完全沒有幻想有機會拿冠軍。現在的感覺真的很難以置信。
有人問我們隊玩ACM有甚麼秘訣,忍不住答了teamwork。
隊友的合作和支持真的非常重要。
亦非常感謝大家在香港的支持。
香港中大在ACM的名聲一年比一年響。
自從我們E++和++Zz;在大陸賽區頭段表現出色,到去年Intuition在寧波拿了第三
而今年Jakarta的射雕+放雕亦令大家緊張了一段時間,之後在twitter也有人討論我們
導致TJU看到我們大學的名後便問我們是不是香港中大,是不是jakarta第三 (雖然之後他們發現CDQ後便無視我們了)
相信在今年,CUHK的名字終於在大家心中留下深刻印象吧。
ACM Kuala Lumpur Regional 2010 比賽過程
中大終於拿到了十一年來的Champion!
賽前真的沒有想過這麼順利
我們training經常縱使中途很多無聊失誤亦全清早走,今次真正比賽終於可以發揮出來!
之前聽到題目是由美國的人出,曾經擔心會很頹,但最後題目質素還是非常好
原來是由uva那堆有名的出題者出的
------------------------------------------------------------
比賽因為技術問題延誤了很多,又加多了一個試機session。之後從volunteer中得知我們比賽的機和試機的機不同,又躁底了。試完機大家再入場準備比賽,卻在比賽場地等了一個多小時才開始。他完全沒有嚴止大家使用電腦,於是大家便一起打自已的template。打完template發現還有很多時間,kn又把geometry的library打完。打完後還是有很多時間,大家便伏在枱上休息。
過了很長時間,終於比賽開始了。一開始開題目,題目感覺不長,先把一堆短的題目抽出來看。不久發現頹題B,上機提交得第一個Yes(5)。CTLi隨即上題I,中途卡了一卡,有少許慢,過sample後提交,又得到Yes(23)。我和kn在CTLi做的途中發現已有隊過H,研究一下卻不懂做,找kn討論一下。中途嘗試問CTLi但被無視,結果和kn討論一大堆後想到了公式,待I打完立即上H,很快便Yes(25)。kn隨即緊接做他已看的頹題,亦不久成功解決得到第4個Yes(34)。CTLi看完題D解給我聽,感覺很簡單,我便分給kn做D,悲劇就此開始。kn搞了一會兒很辛苦終於過到sample,這是已經6x分鐘,提交首先交錯題目,再交得到WA。我的題G也想得差不多,便搶機開始coding。Code到中途有bug,過不到sample,便和kn交替地上。CTLi又可以上,於是便讓他先上。中途kn找我幫忙,但好像沒有理會他,看了看便繼續埋頭做自已的題G。搞了好一段時間和不斷的換位上機,CTLi終於過了題C(98+1RE)。看到F已經有人過,是經典的steiner tree DP,想了想便想到DP的狀態和做法。經過一輪掙扎,我還是我的算法告訴做DP有更高準確度的CTLi,讓他準備上題F。我又發現我的code有些很無聊的bug,改完後過了sample,又再交幸運地沒有bug,得到第6個Yes(108)。之後看看kn的題D的題目,發現有地方CTLi看漏了,便叫kn過來看,很快想到解決辦法,kn改後再交終於Yes了(114+3WA)。一輪失誤後終於過了題D到了7題,但是現在罰時已經大幅落後南洋理工(NTU)。值得一提的是雖然旁邊大會有很多準備好的氣球,但在頭一個多小時都沒有派。
出了第7題後心情可以放鬆少許,看看scoreboard的情況,但知道形勢不妙,因為我們不懂得做題E,而罰時落後,而最不利的是CDQ有機會會做到。不管怎樣,我和kn開始研究題J的幾何。聽kn說明題意後,好像便是經典的O(n^2 log n) sort by angle的題目。過了一段時間CTLi需要debug,便換上kn開始code,我亦幫kn寫中間計算面積的部份。CTLi的題F搞了很久終於過到sample,提交卻得到TLE。我再想想,過了一會兒想到加速的方法,可以降低一個dimension,和CTLi討論一下便繼續讓CTLi上。這是kn又說他的題J差不多寫好,等我寫幾何計算面積的部份。我便立即在紙上寫我的code,讓kn打上機,但那段code發現有錯。CTLi這時又得到一個WA,我便沒有理kn,專心幫CTLi fix那個bug。中途又幫kn作test case去測試我寫錯的部份。終於CTLi上機改好,再交得到第8個Yes(168+1TLE+1WA)。我們的第二維持了不久便被HKUST過頭了。之後我讓CTLi全力想E,我和kn一起做J。又過了一大段時間,終於過了sample,提交得到WA。中間發現kn寫rotation的東西寫得很差很亂,把那段code簡化,和修改了有些for loop撞counter variable名的情況再交,仍是得到WA。這時候和CTLi討論了很長時間(途中因為CTLi不斷ban我的想法又不說原因令我有些躁),發現我們的assumption不正確,有一個case完全沒有考慮。這時我還高興,因為這個case不太易想,很可能NTU會發現不到,這樣我們有機會9題便勝出。kn上機加上再考慮那個case,又handle兩點分在兩邊的case,又過了自已新加的test case再交。交完不久kn發現那個case handle錯了,未等response再交,最後得出兩個也是Yes(229+2WA)。再看scoreboard失望地發現NTU亦過了題J,同樣達到9題,罰時領先我們。而CTLi又一直說不懂做題E,於是就等同於這次比賽已經輸了。
最後當然三個人一齊在想題E。我提出了可以拆成兩個式然後再用Chinese Remainder Theorem,而mod 2^12的式可以暴試找答案。但對於另一公式亦想不到解決方法。再想了一陣子CTLi說他可以試試頹做,我提出他把算法告訴我們然後他繼續想,我們上機頹做,但他說很簡單很快便寫好。無奈地讓他上機去做,不久CTLi便寫好了,打入sample發現極速出結果。再randomly打一寫大的數亦是立即可以出答案。CTLi提出立即交,但我和kn建議先打表。但打表途中我們發現如果沒有答案便會loop死,而我們又不知道怎樣check有沒有答案。我又提出去數iteration的數目,太多時便break。寫完發現打表打得極慢,於是不知道為甚麼又放棄了。最後我們一致通過交CTLi那個“頹”program,便很緊張地等結果。這時我們再試試random的test case,發現仍然是很快。由於CTLi不斷說他的方法很頹,我擔心假如NTU知道我們過了便又會試試頹做,所以還是不讓NTU知道的好。我便叫隊友看到Yes不要大叫,保持秘密不讓NTU知道。
因為judging time很長時間,我在很緊張和沒有警惕的情況突然下看到巨型綠色YES(247),也不小心大聲叫了YES,很失敗。到最後我們還是繼續假裝很忙,一開始在分題目,把整份題目從我們打印的code中抽出來。中途又有volunteer見我們渣攤來和我們說話,但由於他們壓低聲量,我完全不知道他們說甚麼。只記得有位大叔走過來看到我們8個氣球,笑說題目是不是很難,沒有可能做完呢。之後無聊了一會兒便叫CTLi打code,讓我留意CTLi打code的問題,好讓在World Final可以進步。CTLi的問題發現有:1.不用alt-tab,2.不用右手尾指,3.雙手放在keyboard沒有default固定的位置,4.不懂用numpad。現在已策劃一連串特訓給CTLi。感覺最後50分鐘時間過得很慢。
比賽結束後很緊張,先走到南洋理工一隊問題數,他們很灰地搖頭(大概自己在jakarta也是差不多的表情吧)。然後再跑去問HKUST的題數,是8題。這時腦袋有些空白,回到座位向隊友報告後,仍好像未必接受自己是champion的事實,有點不知所措的感覺。先把漏掉的氣球拿回拍一下照,之後又有很多人找我們問題目和拿code,又有找我們拍照。走時統一統計,當我還想認叻的時候,發現原來自己只是做了兩題。結論就是我今天的比賽是渣灘的。有傳言說新加坡某大學出了10題,我不太相信,因為已問過NTU。我猜是他們把我們認錯是新加坡的隊伍吧。
到頒獎禮,心急等了一大段時間終於證實自已確實是champion。上台的一刻想到等了十一年終於拿到了,有些感動。驚訝地發現HKUST一個人都不在,NTU也只有一個人上台拿獎。之後有很多人找我們拍照,亦有不少人借我們的獎盃拍照。我們亦找judges討論題E的做法,發現兩個judges和我們的做法也不相同。最後不斷拍照,連回hostel的巴士也沒有上。最後Derek Kisman在我們拍照時走過來又不敢打擾我們拍照,我們便立即輪流和他單獨拍照,他顯得有些無奈XD。拍完後原來他是想來找CTLi討論E的題解,說CTLi的做法好像可以解釋他一個之前不明白的地方。走的時候本來打算步行回到hostel(大約15-20分鐘路程),但途中看到volunteer姐姐的車,她們很好心地車了我們回去了。對於IIUM主辦的volunteer姐姐印象還是很不錯的。
趣事:
1. CJ還是很喜歡叫全部人拍手掌的演講
2. CTLi影相時不肯笑,連volunteer姐姐都忍不住說他"You look so sad!" 我和kn一齊“sosad!”
3. 最後找CJ拍照時,他有點不耐煩。問我們甚麼學校,答了發現我們第一,然後送了我們特別禮物,是一個空的袋 (o:
賽前真的沒有想過這麼順利
我們training經常縱使中途很多無聊失誤亦全清早走,今次真正比賽終於可以發揮出來!
之前聽到題目是由美國的人出,曾經擔心會很頹,但最後題目質素還是非常好
原來是由uva那堆有名的出題者出的
------------------------------------------------------------
比賽因為技術問題延誤了很多,又加多了一個試機session。之後從volunteer中得知我們比賽的機和試機的機不同,又躁底了。試完機大家再入場準備比賽,卻在比賽場地等了一個多小時才開始。他完全沒有嚴止大家使用電腦,於是大家便一起打自已的template。打完template發現還有很多時間,kn又把geometry的library打完。打完後還是有很多時間,大家便伏在枱上休息。
過了很長時間,終於比賽開始了。一開始開題目,題目感覺不長,先把一堆短的題目抽出來看。不久發現頹題B,上機提交得第一個Yes(5)。CTLi隨即上題I,中途卡了一卡,有少許慢,過sample後提交,又得到Yes(23)。我和kn在CTLi做的途中發現已有隊過H,研究一下卻不懂做,找kn討論一下。中途嘗試問CTLi但被無視,結果和kn討論一大堆後想到了公式,待I打完立即上H,很快便Yes(25)。kn隨即緊接做他已看的頹題,亦不久成功解決得到第4個Yes(34)。CTLi看完題D解給我聽,感覺很簡單,我便分給kn做D,悲劇就此開始。kn搞了一會兒很辛苦終於過到sample,這是已經6x分鐘,提交首先交錯題目,再交得到WA。我的題G也想得差不多,便搶機開始coding。Code到中途有bug,過不到sample,便和kn交替地上。CTLi又可以上,於是便讓他先上。中途kn找我幫忙,但好像沒有理會他,看了看便繼續埋頭做自已的題G。搞了好一段時間和不斷的換位上機,CTLi終於過了題C(98+1RE)。看到F已經有人過,是經典的steiner tree DP,想了想便想到DP的狀態和做法。經過一輪掙扎,我還是我的算法告訴做DP有更高準確度的CTLi,讓他準備上題F。我又發現我的code有些很無聊的bug,改完後過了sample,又再交幸運地沒有bug,得到第6個Yes(108)。之後看看kn的題D的題目,發現有地方CTLi看漏了,便叫kn過來看,很快想到解決辦法,kn改後再交終於Yes了(114+3WA)。一輪失誤後終於過了題D到了7題,但是現在罰時已經大幅落後南洋理工(NTU)。值得一提的是雖然旁邊大會有很多準備好的氣球,但在頭一個多小時都沒有派。
出了第7題後心情可以放鬆少許,看看scoreboard的情況,但知道形勢不妙,因為我們不懂得做題E,而罰時落後,而最不利的是CDQ有機會會做到。不管怎樣,我和kn開始研究題J的幾何。聽kn說明題意後,好像便是經典的O(n^2 log n) sort by angle的題目。過了一段時間CTLi需要debug,便換上kn開始code,我亦幫kn寫中間計算面積的部份。CTLi的題F搞了很久終於過到sample,提交卻得到TLE。我再想想,過了一會兒想到加速的方法,可以降低一個dimension,和CTLi討論一下便繼續讓CTLi上。這是kn又說他的題J差不多寫好,等我寫幾何計算面積的部份。我便立即在紙上寫我的code,讓kn打上機,但那段code發現有錯。CTLi這時又得到一個WA,我便沒有理kn,專心幫CTLi fix那個bug。中途又幫kn作test case去測試我寫錯的部份。終於CTLi上機改好,再交得到第8個Yes(168+1TLE+1WA)。我們的第二維持了不久便被HKUST過頭了。之後我讓CTLi全力想E,我和kn一起做J。又過了一大段時間,終於過了sample,提交得到WA。中間發現kn寫rotation的東西寫得很差很亂,把那段code簡化,和修改了有些for loop撞counter variable名的情況再交,仍是得到WA。這時候和CTLi討論了很長時間(途中因為CTLi不斷ban我的想法又不說原因令我有些躁),發現我們的assumption不正確,有一個case完全沒有考慮。這時我還高興,因為這個case不太易想,很可能NTU會發現不到,這樣我們有機會9題便勝出。kn上機加上再考慮那個case,又handle兩點分在兩邊的case,又過了自已新加的test case再交。交完不久kn發現那個case handle錯了,未等response再交,最後得出兩個也是Yes(229+2WA)。再看scoreboard失望地發現NTU亦過了題J,同樣達到9題,罰時領先我們。而CTLi又一直說不懂做題E,於是就等同於這次比賽已經輸了。
最後當然三個人一齊在想題E。我提出了可以拆成兩個式然後再用Chinese Remainder Theorem,而mod 2^12的式可以暴試找答案。但對於另一公式亦想不到解決方法。再想了一陣子CTLi說他可以試試頹做,我提出他把算法告訴我們然後他繼續想,我們上機頹做,但他說很簡單很快便寫好。無奈地讓他上機去做,不久CTLi便寫好了,打入sample發現極速出結果。再randomly打一寫大的數亦是立即可以出答案。CTLi提出立即交,但我和kn建議先打表。但打表途中我們發現如果沒有答案便會loop死,而我們又不知道怎樣check有沒有答案。我又提出去數iteration的數目,太多時便break。寫完發現打表打得極慢,於是不知道為甚麼又放棄了。最後我們一致通過交CTLi那個“頹”program,便很緊張地等結果。這時我們再試試random的test case,發現仍然是很快。由於CTLi不斷說他的方法很頹,我擔心假如NTU知道我們過了便又會試試頹做,所以還是不讓NTU知道的好。我便叫隊友看到Yes不要大叫,保持秘密不讓NTU知道。
因為judging time很長時間,我在很緊張和沒有警惕的情況突然下看到巨型綠色YES(247),也不小心大聲叫了YES,很失敗。到最後我們還是繼續假裝很忙,一開始在分題目,把整份題目從我們打印的code中抽出來。中途又有volunteer見我們渣攤來和我們說話,但由於他們壓低聲量,我完全不知道他們說甚麼。只記得有位大叔走過來看到我們8個氣球,笑說題目是不是很難,沒有可能做完呢。之後無聊了一會兒便叫CTLi打code,讓我留意CTLi打code的問題,好讓在World Final可以進步。CTLi的問題發現有:1.不用alt-tab,2.不用右手尾指,3.雙手放在keyboard沒有default固定的位置,4.不懂用numpad。現在已策劃一連串特訓給CTLi。感覺最後50分鐘時間過得很慢。
比賽結束後很緊張,先走到南洋理工一隊問題數,他們很灰地搖頭(大概自己在jakarta也是差不多的表情吧)。然後再跑去問HKUST的題數,是8題。這時腦袋有些空白,回到座位向隊友報告後,仍好像未必接受自己是champion的事實,有點不知所措的感覺。先把漏掉的氣球拿回拍一下照,之後又有很多人找我們問題目和拿code,又有找我們拍照。走時統一統計,當我還想認叻的時候,發現原來自己只是做了兩題。結論就是我今天的比賽是渣灘的。有傳言說新加坡某大學出了10題,我不太相信,因為已問過NTU。我猜是他們把我們認錯是新加坡的隊伍吧。
到頒獎禮,心急等了一大段時間終於證實自已確實是champion。上台的一刻想到等了十一年終於拿到了,有些感動。驚訝地發現HKUST一個人都不在,NTU也只有一個人上台拿獎。之後有很多人找我們拍照,亦有不少人借我們的獎盃拍照。我們亦找judges討論題E的做法,發現兩個judges和我們的做法也不相同。最後不斷拍照,連回hostel的巴士也沒有上。最後Derek Kisman在我們拍照時走過來又不敢打擾我們拍照,我們便立即輪流和他單獨拍照,他顯得有些無奈XD。拍完後原來他是想來找CTLi討論E的題解,說CTLi的做法好像可以解釋他一個之前不明白的地方。走的時候本來打算步行回到hostel(大約15-20分鐘路程),但途中看到volunteer姐姐的車,她們很好心地車了我們回去了。對於IIUM主辦的volunteer姐姐印象還是很不錯的。
趣事:
1. CJ還是很喜歡叫全部人拍手掌的演講
2. CTLi影相時不肯笑,連volunteer姐姐都忍不住說他"You look so sad!" 我和kn一齊“sosad!”
3. 最後找CJ拍照時,他有點不耐煩。問我們甚麼學校,答了發現我們第一,然後送了我們特別禮物,是一個空的袋 (o:
ACM Jakarta Regional 2010 比賽過程
這個可能是近十年中大最有機會拿冠軍的regional,最後還是輸了,很失望。相信我們過H的時候應該中大的朋友都十分興奮,甚至可能有我們興奮程度的一半。除了中大的朋友,可能還有一眾花生友(http://twitter.com/thanhvy)和judges也應該這樣想吧。雖然已提供了精彩的比賽,可惜不能把餘下的做完,否則過了台大的話將是經典的一場反擊。
final scoreboard: http://competition.binus.ac.id/icpc/result/final.html
================================================================
比賽大會要求早上六時正乘車去大學,然後等到九點才比賽。這樣的時間大會解釋是因為改遲時間的話會大塞車,10分鐘的路程可能會需要1小時。就這樣,我們便一早起來去比賽的大學吃早餐,然後躺在三張椅子上睡覺,意外地這樣睡還睡得不錯。
比賽開始雖然有少許緊張,但還不算是太緊張。雖然沒有World Final的輕鬆心情,但至少比以往的regional比賽較為放鬆。一開題目先把全部題目掃一遍,看到題C是game,立即叫CTLi看。這時聽到kn 打template的keyboard聲音非常怪異,心知不妙。我再看A,題意很簡單,constant數目的input,想了想又想不到,但又覺得有可能是極簡單被秒殺的題目,再想還是想不到。CTLi這時開始上機做題C。我又發現kn好像看了很多題目,於是讓他解給我聽,是有關BST的input sequence的counting題目,暫時不懂,但相信不難。之後kn又解了I的題意給我聽,一聽便知道是NWERC 04 Problem E和HKOI2004 Junior Compeition一樣,就是greedy。算法也懶得和kn說,便說我可以做這題了。上機寫便立即感受到keyboard真的很爛。寫完過不到 sample,打印題目看,再看看題目發現沒有考慮A這種咭。等CTLi的C做完後便上去改,改完立即過sample。CTLi的C回來一個 Yes(24)。我也交了我的I,不久又回來另一個Yes(25)。之後kn可以上題D,他說是頹題,果然很快便寫好提交,得到第三個Yes(34)
中途解了A的題意給CTLi,他搞了一會兒好像有些頭緒。kn解題F給我聽,想一想覺得可以SCC縮點,然後再做DP應該可行(大錯特錯)。我發現台大己經秒殺了題E,我看看題目,好像有些難又或者要類似segment tree,硬着頭皮再想想又立即發現簡單的算法。在題D過了後便上機做E,做到中途有bug,找了一段時間都不明白,只好退下來給CTLi做題A。再研究了一會兒知道錯了甚麼,準備好改的時候CTLi又如火如茶,心急地等他寫完提交得到WA。我再上機把E完成,還是有點錯,原來有些麻煩地方沒有 handle好,唯有硬着頭皮再開一個數組特別處理,辛苦地搞完發現過了sample,提交興奮地得到第4個Yes(72)。我可以繼續做F,但kn這時候又可以做題J,他說是簡單題。本來我想先做題F,但看見他已經在紙上寫好code,便讓他先做。做到中途有嚴重的卡住,不知道錯甚麼。CTLi又可以修改他的A,這時他們交錯的做,kn發現打錯了variable名,過了sample後交,得到TLE。CTLi又可以交了,可惜改完卻又只得TLE。搞了一大段時間,CTLi終於把A暫時射雕Yes了!(123+2)。kn改過他的無聊錯鋘後很快又把題J過了(129+2)。這時我開始做F,我以為是 SCC縮點後DP的題目,中途聽kn說H的題意,亦把我在題B想到的observation說給CTLi聽。題F很快便寫好,提交卻得到WA。打印出來卻又找不到bug。
中途看到台大已經八題遙遙領先。在這時候我才開始有些擔心:我一直沒有擔心是因為好像還未做的題目都懂得做(我假設了CTLi會做到那題數字題目G),但他們還有兩小時去做剩下的題目,很有機會可以把題目做完,這樣我們即使全清也不可能奪冠。在這時候 CTLi上B,雖然打得有少許慢,但還是穩住地把題目過了(152)。而我亦可以上題H,便便請kn幫我debug題F,最後還是要寫generator 去測試。當我交替寫H和kn trace我的program debug的時候,終於找到算法的錯誤。大家再想卻想不到修補的方法,絕望了一會兒後便決定由kn去頹做。頹做當然很快code完,提交竟然輕鬆得到 Yes(204)。看到Yes的一剎我不由自主地大叫了一聲,竟然在隔了一間房的chin也聽到這一下叫聲.....
而有關題H,我一聽便知道和NWERC 04 Problem A接近一模一樣, 就是經典的AC自動機+DP。kn又不能代我做題H,唯有我自己上, 打AC自動機的武器(又打武器了)。因為曾經做過的關係,有些第一次做會錯的地方都避免了,所以做的過程還算順利。但題目要撇除由0為開頭的 string,唯有另外再開一個類似的DP處理。之後過多了幾個sample,不過最後的還是過不到。搞了一段時間又發現TRIE有未 initialize的地方,改了後立即過sample,提交,得到的是WA。kn提出long long的問題,我發現雖然我DP數組有用long long,但中段有些variable沒有留意,只用了int,改了後再交,感覺好累好暈,去一去洗手間。回來後還沒有回到座位kn便告訴我過了,我興奮得跳了起來,整個房間都望着我 = =。這樣便射雕,達到9題,只淨那題數字的DP,還有超過一小時的時間,形勢還算不錯。
CTLi 這時可以上G,他說都是搜索+DP。雖然做到中途我開始覺得似乎不是這樣做,但又覺得應該相信一下CTLi。而我在做完H的時候精力差不多已經用盡,看看 scoreboard,發現除非IsolatE全清,否則我們罰時領先,心情安心了一點。中途看看旁邊的交大女隊,她們同樣是9題但還未做H,看到她們做了一段又三個停手,應該做不到H,又安心了一點。再望兩望還是集中僅有的精神想想G有沒有其他方法做,方向正確但還是想不到,看還有半小時,唯有放棄轉而支持CTLi。CTLi在最後二十分鐘過了sample,提交得到TLE。於是便轉而用其他data structure或優化,希望可以加速,但一直到最後還是各種No的結果不斷出來,比賽就這樣結束。台大和交大很明顯最後也做不到H。
比賽完後很灰,錯失了champion的好機會,而出線world final的機會亦不太肯定。灰了一段長時間後心情恢復了少許,心想還好拿到第二。交大的coach zhuojie(去年world final冠軍)和其他coach還有眾隊員走來問我題H的做法,原來交大他們全部都想不到做法,於是我便很有型地把算法告訴他們。在頒獎禮前chin看到香港大家send來的email才知道我們只得第三,又灰了很長時間。後來聽Leo補充,原來這隊冠軍的台大是由三個IOI金獎組成。
這次比賽落敗的原因並不在於前面的失誤,完全是因為做不到G。我們雖然做前面的題目做得很慢,但到最後亦有超過一小時的時間去做G。即使前面失誤減少,亦再需要很多運氣才可以比得上台大開局的完美表現。題G是我們應該有能力可以做到的,所以題G是本次落敗的關鍵。假如中途做好一點,就可以拿第二,出線機會又增加10-20%。假如運氣好一點想到G的做法,出線的機會便會升至100%了。現在感覺出線的機會只有50%,因此在Kuala Lumpur的比賽又更加努力。
[回憶比賽過程做題的先後次序可能和實際有少許偏差]
PS1: 題F有很多老手中伏,都往SCC的方向想,但其實頹做N次DFS也很快。
PS2: I hate Jakarta.
final scoreboard: http://competition.binus.ac.id/icpc/result/final.html
================================================================
比賽大會要求早上六時正乘車去大學,然後等到九點才比賽。這樣的時間大會解釋是因為改遲時間的話會大塞車,10分鐘的路程可能會需要1小時。就這樣,我們便一早起來去比賽的大學吃早餐,然後躺在三張椅子上睡覺,意外地這樣睡還睡得不錯。
比賽開始雖然有少許緊張,但還不算是太緊張。雖然沒有World Final的輕鬆心情,但至少比以往的regional比賽較為放鬆。一開題目先把全部題目掃一遍,看到題C是game,立即叫CTLi看。這時聽到kn 打template的keyboard聲音非常怪異,心知不妙。我再看A,題意很簡單,constant數目的input,想了想又想不到,但又覺得有可能是極簡單被秒殺的題目,再想還是想不到。CTLi這時開始上機做題C。我又發現kn好像看了很多題目,於是讓他解給我聽,是有關BST的input sequence的counting題目,暫時不懂,但相信不難。之後kn又解了I的題意給我聽,一聽便知道是NWERC 04 Problem E和HKOI2004 Junior Compeition一樣,就是greedy。算法也懶得和kn說,便說我可以做這題了。上機寫便立即感受到keyboard真的很爛。寫完過不到 sample,打印題目看,再看看題目發現沒有考慮A這種咭。等CTLi的C做完後便上去改,改完立即過sample。CTLi的C回來一個 Yes(24)。我也交了我的I,不久又回來另一個Yes(25)。之後kn可以上題D,他說是頹題,果然很快便寫好提交,得到第三個Yes(34)
中途解了A的題意給CTLi,他搞了一會兒好像有些頭緒。kn解題F給我聽,想一想覺得可以SCC縮點,然後再做DP應該可行(大錯特錯)。我發現台大己經秒殺了題E,我看看題目,好像有些難又或者要類似segment tree,硬着頭皮再想想又立即發現簡單的算法。在題D過了後便上機做E,做到中途有bug,找了一段時間都不明白,只好退下來給CTLi做題A。再研究了一會兒知道錯了甚麼,準備好改的時候CTLi又如火如茶,心急地等他寫完提交得到WA。我再上機把E完成,還是有點錯,原來有些麻煩地方沒有 handle好,唯有硬着頭皮再開一個數組特別處理,辛苦地搞完發現過了sample,提交興奮地得到第4個Yes(72)。我可以繼續做F,但kn這時候又可以做題J,他說是簡單題。本來我想先做題F,但看見他已經在紙上寫好code,便讓他先做。做到中途有嚴重的卡住,不知道錯甚麼。CTLi又可以修改他的A,這時他們交錯的做,kn發現打錯了variable名,過了sample後交,得到TLE。CTLi又可以交了,可惜改完卻又只得TLE。搞了一大段時間,CTLi終於把A暫時射雕Yes了!(123+2)。kn改過他的無聊錯鋘後很快又把題J過了(129+2)。這時我開始做F,我以為是 SCC縮點後DP的題目,中途聽kn說H的題意,亦把我在題B想到的observation說給CTLi聽。題F很快便寫好,提交卻得到WA。打印出來卻又找不到bug。
中途看到台大已經八題遙遙領先。在這時候我才開始有些擔心:我一直沒有擔心是因為好像還未做的題目都懂得做(我假設了CTLi會做到那題數字題目G),但他們還有兩小時去做剩下的題目,很有機會可以把題目做完,這樣我們即使全清也不可能奪冠。在這時候 CTLi上B,雖然打得有少許慢,但還是穩住地把題目過了(152)。而我亦可以上題H,便便請kn幫我debug題F,最後還是要寫generator 去測試。當我交替寫H和kn trace我的program debug的時候,終於找到算法的錯誤。大家再想卻想不到修補的方法,絕望了一會兒後便決定由kn去頹做。頹做當然很快code完,提交竟然輕鬆得到 Yes(204)。看到Yes的一剎我不由自主地大叫了一聲,竟然在隔了一間房的chin也聽到這一下叫聲.....
而有關題H,我一聽便知道和NWERC 04 Problem A接近一模一樣, 就是經典的AC自動機+DP。kn又不能代我做題H,唯有我自己上, 打AC自動機的武器(又打武器了)。因為曾經做過的關係,有些第一次做會錯的地方都避免了,所以做的過程還算順利。但題目要撇除由0為開頭的 string,唯有另外再開一個類似的DP處理。之後過多了幾個sample,不過最後的還是過不到。搞了一段時間又發現TRIE有未 initialize的地方,改了後立即過sample,提交,得到的是WA。kn提出long long的問題,我發現雖然我DP數組有用long long,但中段有些variable沒有留意,只用了int,改了後再交,感覺好累好暈,去一去洗手間。回來後還沒有回到座位kn便告訴我過了,我興奮得跳了起來,整個房間都望着我 = =。這樣便射雕,達到9題,只淨那題數字的DP,還有超過一小時的時間,形勢還算不錯。
CTLi 這時可以上G,他說都是搜索+DP。雖然做到中途我開始覺得似乎不是這樣做,但又覺得應該相信一下CTLi。而我在做完H的時候精力差不多已經用盡,看看 scoreboard,發現除非IsolatE全清,否則我們罰時領先,心情安心了一點。中途看看旁邊的交大女隊,她們同樣是9題但還未做H,看到她們做了一段又三個停手,應該做不到H,又安心了一點。再望兩望還是集中僅有的精神想想G有沒有其他方法做,方向正確但還是想不到,看還有半小時,唯有放棄轉而支持CTLi。CTLi在最後二十分鐘過了sample,提交得到TLE。於是便轉而用其他data structure或優化,希望可以加速,但一直到最後還是各種No的結果不斷出來,比賽就這樣結束。台大和交大很明顯最後也做不到H。
比賽完後很灰,錯失了champion的好機會,而出線world final的機會亦不太肯定。灰了一段長時間後心情恢復了少許,心想還好拿到第二。交大的coach zhuojie(去年world final冠軍)和其他coach還有眾隊員走來問我題H的做法,原來交大他們全部都想不到做法,於是我便很有型地把算法告訴他們。在頒獎禮前chin看到香港大家send來的email才知道我們只得第三,又灰了很長時間。後來聽Leo補充,原來這隊冠軍的台大是由三個IOI金獎組成。
這次比賽落敗的原因並不在於前面的失誤,完全是因為做不到G。我們雖然做前面的題目做得很慢,但到最後亦有超過一小時的時間去做G。即使前面失誤減少,亦再需要很多運氣才可以比得上台大開局的完美表現。題G是我們應該有能力可以做到的,所以題G是本次落敗的關鍵。假如中途做好一點,就可以拿第二,出線機會又增加10-20%。假如運氣好一點想到G的做法,出線的機會便會升至100%了。現在感覺出線的機會只有50%,因此在Kuala Lumpur的比賽又更加努力。
[回憶比賽過程做題的先後次序可能和實際有少許偏差]
PS1: 題F有很多老手中伏,都往SCC的方向想,但其實頹做N次DFS也很快。
PS2: I hate Jakarta.
2010年9月11日 星期六
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的時候差很遠
最近想算法好像有些慢, 頭腦不太靈活
不過不要緊, 只要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年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.
2009年11月18日 星期三
PKU3471 - Integral Roots
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3471
The problem is given an integral coefficient polynomial, find all integral roots of it.
If there is repeated root, output them repeatedly.
For the integral roots of the polynomial, it must be a factor of the constant term of the polynomial. We then can factorized the constant term and verify the factors to the polynomial one by one.
However, overflow will occur during the verification (the degree of the polynomial may be as large as 100), how should we verify the solution safely?
One method is that you can calculate the polynomial by repeatedly dividing and subtracting each terms. For example, ax^2 + bx + c = 0, it can be rewritten as ax + b = -c/x. As the LHS of the equation is integer, the c/x must be integer. Using this method, we can avoid overflow in our calculation.
This has not solved the problem. We have not identified the repeated roots. One way to find the multiplicity of roots is to check f(x), f'(x), f''(x), and so on, and they should all be zero. But calculating the derivatives of f may again lead to overflow.
The method I finally used is to do polynomial division.
I repeatedly divide the polynomial by (x - c). If that is divisible, then c is a root of it, and use the quotient to continue the process. This can avoid all overflow problems, and find the repeated roots successfully.
Be careful on the cases that zero is the root of the polynomial.
start writing ACM blog
a little bit late, but hopes this can make me write more, and of course, do more problems =)
訂閱:
文章 (Atom)
