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:

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.

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的時候差很遠

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, 而且看漏了題目, 又優化很久才過

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的放寬約制
等等, 有些比較喜歡, 有些比較不好看

個人認為要選出比較好看的論文, 主要還是看作者的名氣, 很多強勁出名的選手通常都寫得不錯
又或者是女選手的作品, 也會比較淺白易明

遺憾的是有很多看題目覺得有趣的論文, 作者都有一定程度的語癌

ZJU3280 - Choose The Best

Link: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3280

December ZOJ Monthly problem, the problem is about finding maximum manhattan distance among all pairs of points in m-dimensional space (m<=8).

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.

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了.....