2008年12月26日 星期五

UVa 110 Meta-Loopless Sorts

用自創的Modified-Permutation Algo ( ̄▽ ̄#)﹏﹏

2008年12月21日 星期日

I have a dream

I have a dream.....




2008年12月14日 星期日

UVa 109 SCUD Busters


典型的凸包 (Convex Hull ) 問題。我是採用 Graham's Scan 來解。作法可以參考維基條目 Graham's Scan,我就是照著條目裡的算法原封不動實做的。


求國土面積,要先對王國內的所有的發電廠位置求凸包,然後由凸包去計算多邊形面積 (題目頁有給多邊形面積公式) 。 判斷飛彈落點是否落在國土內,也是以凸包為基礎,沿著凸包的每個邊判斷,如果飛彈落點都在邊的左側,那就表示打中了!


使用Graham's Scan 時要特別注意共線問題,尤其是起始點三點共線,例如 (0,0) (1,1) (2,2) (1,3) ,求出來的凸包應該是 (0,0) (2,2) (1,3)。


有點囉嗦的題目。2008年底我第一次解這題,因為過程有點曲折,所以花了好幾天才解出來,而且一直搞不定 std::sort( ) 的判斷函數,現在重寫一遍,感覺比較清爽一些了!

2008年12月9日 星期二

線性代數的世界作者 Dr. Strang 妙語如珠

  1.  "you can't add apples and oranges."「你不能把蘋果和橘子加在一起」

  2. The central porblem of linear algebra is to solve a system of equations.

  3. It is also common sense: If you put on socks and then shoes, the first to be taken off are the ___.

  4. Ax combines the columns of A while xTAT combines the rows of AT
    --談為何(AB)T = BTAT

最近看Gilbert Strang寫的『Introduction to Linear Algebra』,Strang教授講法生動,不論是趣味的例子,或者是一句話直搗觀念核心,都常讓我拍案叫絕。


2008年12月5日 星期五

UVa 476 Points in Figures: Rectangles



2008年12月4日 星期四

UVa 458 The Decoder

Buffered加速版 0.020s。看到很多0.000s,這我真的不知道怎麼做了....

2008年12月3日 星期三

2008年12月2日 星期二

UVa 104 Arbitrage


Some Hints about uVA 104 


苦思良久的UVa 104終於在 gits 幾乎手把手的帶領下寫出來了,了結了多天以來的心中懸念。XDDD稍微變化題,馬上就把我土法煉鋼學會的Floyd-Warshall 打回原型。連F-W要用二維還是三維陣列來建表都搞不清楚,唉,由這題可以知道我的DP/Graph有待磨練。

只有與問題面對面的對決,在測資跟Bug中打滾一番後,才能對Algorithm有更深刻的體會吧。這也是我寫ACM的目的與樂趣所在。不過...這題還是有點心虛阿.....orz 只能說敗給你了Modified Floyd-Warshall,還未夠班....總有一天我要能秒殺這題。

2008年12月1日 星期一

[ACM] Some hints about uva 104 (Modified Floyd-Warshall)

by gits
Original Thread http://online-judge.uva.es/board/viewtopic.php?t=7292

Well, I'll assume you understand what the problem asks. You have to find the shortest sequence that yelds a profit (not the one with the greatest profit!). If there is more then one sequence with the same length, any of those is valid.

Now, you can't just try with brute force (trying all combinations) because it'll be too slow and you'll get Time Limit Exceeded. However, there's a well known algorithm, Floyd-Warshall, which will find all the shortest paths between every node to the others in just O(n^3) time. You can find more info about F-W in the net. In my previous post I said how you have to change the general F-W algorithm to work for this particular problem...

As for floating point errors, most numbers representation isn't totally acurate; for instance, 0.1 is usually stored as 0.10000000000000001. After some operations, the error may influence the final result. Again, search the net for floating point errors. However, you won't have to deal with these errors to solve this problems (at least I didn't).

Hope this helps

Floyd-Warshall finds all the mininum paths between every vertex and all the other vertexes. However, in this problem you not only have to find the shortest path, it also has to make a profit of more than 1%.

Simple F-W goes like this:
// initialization
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      best[i][j] = path[i][j];
      path[i][j] = i;

for (k = 0; k < n; k++) {
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (best[i][k] + best[k][j] < best[i][j]) {
                best[i][j] = best[i][k] + best[k][j];
                path[i][j] = k;

For this problem, instead of having best[i][j] and path[i][j] I have best[i][j][s] and path[i][j][s], which means "best path from i to j in s steps". I also have an outer loop, representing the number of steps.
// initialization
best[i][j][s] = 0, for all i,j,s
best[i][j][1] = input for the program
best[i][i][1] = 1, for all i
path[i][j][1] = i, for all i, j

for (steps = 2; steps <= n; steps++)
    for k...
        for i..
            for j..
                tmp = best[i][k][steps-1] * best[k][j][1]
                if (tmp > best[i][j][steps]) {
                    best[i][j][steps] = tmp;
                    path[i][j][steps] = k;
What we are doing is to find the most profitable way to go from i to j in "steps" steps, trying for each to use k as the point just before j. As you can see, this is O(n^4) but since max n is 20 it's ok.

After this, you scan though best[i][i][s] (best way to go from i to i again, in s steps). Remember that you want the minimum number of steps that yields a profit; so it's this:
for (steps = 2; steps <= n; steps++)
    for (i = 0; i < n; i++)
        if (best[i][i][steps] > 1.01) {
            // score!
If the "if" never matches, then there is no arbitrage sequence. If it matches, you have to print the path. To print the path, use path[i][i][steps], which is the vertex just before the last (i).

For instance, if i is 1 and steps is 4. Check path[1][1][4]. Suppose it is 2. So the path ends with "... 2 1". Now check path[1][2][3]. Supposing it's 4, the path ends with "... 4 2 1". Now check path[1][4][2]. If it's 5, the path is "... 5 4 2 1". Finally check path[1][5][1], which will be obviously 1. So the complete path is "1 5 4 2 1" (exactly 4 steps).

Just remember that path[i][j][s] is the vertex which is before the last one in a path from i to j in s steps. If s is 1, the path is simply "i j". In this problem you have to start and finish in the same currency; that's why we only search in best[i][i][steps].

Hope this helps, I almost wrote the complete program!

You could also stop the algorithm as soon as you found a solution. In other posts, some people talked about a O(n^3) solution but I can't figure it out... if someone has such a solution please mail it to me, I would love to learn how to do this in a better way.

Good luck and happy coding!