2008年12月26日 星期五

UVa 110 Meta-Loopless Sorts

相當有趣的一題....寫程式產生器
用自創的Modified-Permutation Algo ( ̄▽ ̄#)﹏﹏
第一次寫有點痛苦,過了幾天醞釀過想法後,寫起來很順很快就AC了
距離連號解題剩下最後一題107了..

2008年12月21日 星期日

I have a dream

I have a dream.....


就是....一次AC.....


最好不是渣渣題....


到底什麼時候才能達成呢?

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)。

閒聊

@2011.10.07
有點囉嗦的題目。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 ___.
    常識也告訴我們:假如你先穿襪子再穿鞋,那麼脫的時候,首先該脫掉___。
    --談為何AB的反矩陣是B-1A-1

  4. Ax combines the columns of A while xTAT combines the rows of AT
    Ax線性組合了A的諸行,而xTAT線性組合了AT的諸列。
    --談為何(AB)T = BTAT

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

比起補習班名師的講義,研讀起來樂趣大多了。有機會再補上更多句子。

2008年12月5日 星期五

UVa 476 Points in Figures: Rectangles

渣渣題三號

判斷點是否在矩形內。在頭腦不清的凌晨三點,犯了一些低級錯誤,還好很快就AC了。
我最近的休閒娛樂就是寫渣渣題....

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 
gits大大說得很清楚,我就不囉唆作法了。

閒聊

苦思良久的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!