跳到主要內容

[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!

留言

這個網誌中的熱門文章

讀書心得: 撒哈拉的故事

初拿起「撒哈拉的故事」時,我心中想著大概是本以沙漠為背景的美麗幻想般的愛情小說吧,有誰會真的費盡千辛萬苦跑去撒哈拉沙漠,在物質極為缺乏的環境下過著刻苦的生活呢? 沒想到這人就是三毛,只因為一個理由「我要認識沙漠」。

「撒哈拉的故事」是三毛與她的丈夫荷西在撒哈拉沙漠旅遊生活的紀實,生活在沙漠很糟糕,至少我看完最後一篇『白手成家』後認為實在很糟,不過在樂觀又開朗的三毛的筆下,撒哈拉沙漠化為一個有趣又不可思議的國度,說著一個又一個異國的故事。

如果不是三毛,我無法想像原來世界上還有這樣子的一群人,還有這等事情,你能想像沙哈拉威人三四年才洗一次澡嗎? 『觀浴記』裡三毛跑去看沙漠女人洗澡,要先用蒸氣蒸,再用石片刮下身上的泥沙,而且沙漠女人不只洗外面,還洗裡面,讓我看的哈哈大笑。『娃娃新娘』 裡則是三毛的一個沙哈拉威鄰居叫「姑卡」要出嫁了,可是她才十歲呀,結婚習俗更是特別,新郎去迎接新娘時,新娘拼命的抵抗,原來才在沙哈拉威人的觀念裡,打得激烈才叫做「好女人」,不掙扎事後會被取笑的。

沙哈拉威人很少受教育,思想沒有邏輯,通常講道理是講不通的。有次三毛要參加晚宴,遍尋不著自己的漂亮高跟鞋,反倒是鞋櫃上多了一雙破鞋子,原來高跟鞋被鄰居小女孩偷去穿了。事後三毛很生氣地跟她理論,小女孩竟然回嘴「生氣,生氣,你的鞋子在我家,我的鞋子還不是在你家,我比你還要氣。」聽見這種話真的是秀才遇到兵,有理講不清,還好三毛是個灑脫的人,笑笑就過去了。

事實上,生活在沙漠真的需要灑脫,老是計較小事肯定活不下去。除了講不清道理的沙拉哈威鄰居,沙漠也有許多危險,書中至少有兩次三毛差點在沙漠裡丟掉小命。但是每一篇故事裡,我都看見一位勇氣可嘉的中國女孩兒,她不屈不撓,以樂觀的心和智慧面對生活中的困難,盡情的玩,盡情的享受生活,像個瘋狂的孩子般,最後甚至布置了一個號稱撒哈拉沙漠裡最美麗的家,連記者都聞風專程前來拜訪,他們的物質生活雖不富裕,但是精神卻很富足。

說到三毛不能不提她的另一半荷西。三毛書裡這樣子描寫『荷西有一個很大的優點,任何三毛所做的事情,在別人看來也許是瘋狂的行為,在他看來卻是理所當然的』,所以當三毛說要去沙漠時,荷西早她兩個月,就先對著撒哈拉沙漠找工作去了,沙漠裡的瘋狂事也總有荷西的一份。人生能遇見這樣的他,既是羨慕,也是感動。

8. 使用視圖與相機鏡頭轉換,及 gluLookAt() - OpenGL FAQ

返回 OpenGL FAQ 目錄

8.010 OpenGL裡的相機鏡頭到底是怎麼運作的呢?  就目前的OpenGL來說,沒有相機鏡頭這種東西。更精確地講,相機永遠都位處於眼空間座標的原點 (0,0,0)。你的OpenGL應用程式為了假裝出移動相機的樣子,必須移動場景,對整個世界場景做相機鏡頭的逆空間轉換。

8.020 我要如何移動場景裡的眼睛或者相機鏡頭? 以相機鏡頭模型來說,OpenGL 並沒有提供介面去做這件事情。然而,GLU庫提供了gluLookAt()函數,傳入眼睛本身位置,眼睛瞄準點位置,以及朝上向量,都是世界空間坐標。這個函數依據參數計算出正確的相機逆空間轉換矩陣,並且乘上目前的矩陣。

8.030 我的相機鏡頭應該放在 ModelView 矩陣還是 Projection矩陣? GL_PROJECTION 矩陣只應該包含投影變換,它必須將眼空間坐標(eye space coordinates)轉換到裁切坐標(clip coordinates)。

GL_MODELVIEW矩陣呢,如其名,應該包含模型(modeling)與視圖(viewing)轉換,將物體空間坐標轉換成眼空間座標。所以請記住,永遠把相機鏡頭轉換放在GL_MODELVIEW矩陣,而不是GL_PROJECTION矩陣。

你可以把投影矩陣(projection matrix)想像成相機鏡頭的各種特性,像是視角的寬窄、焦距、用了魚眼鏡頭等等。而把模型視圖矩陣(model-view matrix)想成,你目前拿著相機站立的位置,及鏡頭指向的方向。

這份 The game dev FAQ 對這兩個矩陣說明得很不錯。

去讀讀 Steve Baker 的文章「濫用投影」(備用連結) 吧。此篇文章寫得很好,值得推薦。它曾經幫助過許多OpenGL新手程式員。

8.040 我該如何實現鏡頭變焦 (Zoom) 的操作? 簡單的做法是對 ModelView矩陣做等比縮放(uniform scale)。但是當模型放得太大時,通常會導致模型被近平面及遠平面裁切掉。一個比較好的做法是限縮投影矩陣裡view volume的寬與高。舉例來說,你的程式對應使用者的輸入,儲存了一個縮放參數值。當縮放值是1.0 時不變焦。縮放值變大就縮小視角,結果模型看起來就放大了。縮放值變小時就反過來做。程式碼範例看起來可能像這樣子:
/* 如果…

UVa 10018 Reverse and Add

解題策略這題是這樣的,要把輸入的數字反轉,例如1357變成7531,然後與原數相加。直到這個數字變成迴文(palindrome)為止,像是1357+7531=8888,8888就是一個迴文。本題只需要按照著要求計算即可,唯一比較技巧是反轉一個整數 int:reverse()
注意需要注意變數範圍:至少要 unsigned long 才能容納題目的數字範圍。而printf()、scanf() 與 unsigned long 打交道的代號是%lu。

爭議點這題有個爭議點是第一個數字到底需不需要判斷回文,舉個例子:
輸入2,那麼該輸出0 2或者1 4?舊版的UVa測資要求必須要輸出1 4,這有些不合常理,新版則是把爭議性測資都拿掉了,所以兩種寫法都能AC。但是在zerojudge.tw上就必須輸出1 4才行。

PS.這題我不小心把某個unsigned long打成int,抓了好久的bug。