Ural 1424 - Minibus

題目連結: 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中比較有趣的題目

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

不知道還有沒有更好的方法解決這條問題呢?

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，輸了給以前嬴過的對手感覺更差 (雖然自己和對手的隊友都已經完全不同)。

事後自我檢討我們這場比賽爭牌失敗(除了實力和運氣外)的原因和這場比賽做得不好的地方：

1. 比賽中第一個技術性失誤應該是kn的題E寫完後才和CTLi討論結果要重寫。中途由於我和CTLi的各自卡題導致kn要孤獨作戰而陷入一個很複雜的想法，事實上假如一早找CTLi談幾句的話這題應該會順利很多。
2. CTLi卡題G的時候我和kn從頭到尾都沒有幫手。比賽中途我理解題目後曾給CTLi建議試一試O(n^3)的簡單DP，但後來到我過題H前後也望過CTLi的code但感覺是我不可能理解的算法。我們完全也沒有意識去幫CTLi，某程度上都是因為CTLi沒有找我們幫手。不過回想起來，在訓練中好像沒有CTLi做不到的題目，而CTLi從來沒有主動找我們幫忙。事實這題目遠比我想像中簡單，而我相信我亦有在這題找出一些observation和幫忙CTLi debug的能力。
3. 最後一小時開題B的決定其實很值得商確。kn當時還是很沒有把握，題目有很多地方他也理解得不清楚，因此到後來需要作出很多修改。當時完全失去信心的我沒有意識到我題D的flow model已經是非常接近，事實上只要再加一層exhaustion就能完美解決我早前看錯的constraint而解決題目。假如我繼續去攻題D會否有更大機會過題？這永遠是一個謎。
4. 到比賽前的最後一星期，我似乎都未能把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已完，這樣就退役了，還有甚麼想說的就遲些在寫吧，退役文後補。

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, 所以下次要繼續努力

[轉載] 復旦某前輩對今年ACM Team的訓話

說得太好了
希望以後的隊員明白, 出去比賽是要肩負起為cuhk拿獎爭光的責任, 並不是去旅行去給cuhk丟臉
你代表的並不只是自己的隊, 而是背後所有支持信任你的老師和同學

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

诚然，每年关于ICPC WF出线的问题没有哪一次不在复旦ACM队里闹得鸡飞狗跳。关于今年
的什么什么PK之类的问题，我不得不说几句丑话。

其一，争夺出线资格本来没有错。但是，我很希望小队员们不要曲解了“出线”的含义。
代表复旦“出线”绝对不是荣誉的象征，它是代表你将挑起为学校在总决赛上斩获荣誉的
责任。在我眼里，与其去当着世界三百位选手丢尽复旦的颜面，还不如加把劲今后在国内
赛区得点金奖。

其二，ICPC的规矩奇葩不是什么新鲜事了，不必醉心于怨天尤人。历史上复旦在某地丢掉
冠军只有一次，那就是当年的南京赛区冠军，当年的总决赛队。今年国内赛区的成绩还望
各位现役队员能够深刻反省，“期中考试”，“状态不好”之类的人民日报新闻联播式的
理由就不必拿出来了，全国所有的大学都要期中考试，总决赛也不会专门安排在你“状态
好”的时候。

其三，今年出线的队希望居安思危，认清形势也认清自己，明白身上的责任；没有出线的
队也不必再提什么PK什么被黑了。还是那句话，如果PK的话我跟FGD不会缺席的，你们自己
掂量。

难听的话说了这么多，还是衷心希望小队员们能端正态度，明确使命，做当之无愧的复旦
“一队”。没有出线的队伍也不必嚷爹骂娘，好好想一想，自己真正输的是什么……

http://blog.renren.com/blog/246784220/702543083

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之前可以改進

ACM Kuala Lumpur Regional 2010 感想

我的最後一個regional比賽
終於，終於，拿到了期待已久的champion
某種感動週期性地在腦海中徘徊

其實在比賽前，我完全沒有想過可以拿champion
不知道為甚麼，我在jakarta的比賽前真的覺得有機會拿冠軍，但今次旅程卻沒有甚麼感覺。
在比賽中途，因為中段大家的失誤，令我亦完全沒有幻想有機會拿冠軍。現在的感覺真的很難以置信。

有人問我們隊玩ACM有甚麼秘訣，忍不住答了teamwork。
隊友的合作和支持真的非常重要。
亦非常感謝大家在香港的支持。

香港中大在ACM的名聲一年比一年響。
自從我們E++和++Zz;在大陸賽區頭段表現出色，到去年Intuition在寧波拿了第三
而今年Jakarta的射雕+放雕亦令大家緊張了一段時間，之後在twitter也有人討論我們
導致TJU看到我們大學的名後便問我們是不是香港中大，是不是jakarta第三 (雖然之後他們發現CDQ後便無視我們了)
相信在今年，CUHK的名字終於在大家心中留下深刻印象吧。