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

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

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