這次是早上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, 所以下次要繼續努力
2010年12月29日 星期三
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.
訂閱：
文章 (Atom)