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

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

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.