2008年11月25日 星期二

UVa 112 Tree Summing

終於AC了..這次最大的心得就是,腦袋不清楚的時候不要寫程式。如果沒辦法理清思路,找出邏輯上的漏洞,那麼debug也只是亂試一通而已,一點幫助都沒有(只有浪費時間)。寫到後來連錯誤的測資也在試,現在想起來真是笨阿

我用recursive的方法去追蹤整顆樹。測資是pre-order sequence
所以遞回順序是root ,left-child , right-child

很不清楚核心Algo:
int traversal(int sum, int target){
    抓左括號
    抓root
    lc = traversal(int sum+root, int target) //向left-child遞回
    rc = traversal(int sum+root, int target) //向right-child遞回  
    抓右括號

    如果是Leaf? 判斷總和相不相等?
    如果是Internal Node,將子樹的結果繼續往上回傳。
}

另外一提,這次我參考了某份AC Code,用non-recursive(Stack)作法,但是因為用了STL stack;,最後執行時間0.510s,慢了我五倍之多。我用Recursive反而執行時間只有0.100s(Ranking 90,再進百大XDDDD)有點意外。證明一件事:Recursive不一定慢,但是STL=慢。

2008年11月24日 星期一

UVa 108 Maximum Sum

解題策略

這題AC的關鍵是時間,用暴力法O(n6) 六層迴圈去解鐵定超時。已知最佳的解法是 O(n3) ,不過一般用O(n4) 就可以通過了。

我也是用 O(n4) 的解法,首先用四層迴圈窮舉子矩陣的左上角(x1,y1) 跟右下角 (x2,y2) 的位置,一旦給定了子矩陣後,就要 O(1) 時間得到子矩陣的和。

要達成這個目標可以透過 sum table 來達成,我說明一下我的方法, sum table ( i, j ) 每個位置儲存的值的是原矩陣 (1,1) ~ (i, j) 之間的元素總和。像下圖的 sum table ( 2, 3 ) 的值就是 原矩陣 (1, 1) ~ (2, 3) 之間的元素和。


一旦建好 sum table,那接下來就可以簡單透過這 D - B -C + A 這四個sum table的元素直接得到子矩陣的和了。

閒聊

最後執行時間0.052 過關....改天再將作法補完,我好睏....晚安。原本用暴力法去跑 100x100 的矩陣,竟然要253秒(大汗)。

2008年11月22日 星期六

UVa 10751 Chess Board v.2

解題策略


注意

修正了兩個問題,終於AC了
1. 雖然題目頁說只要印小數點後三位,但其實要印四位。
2. 各個output case"之間",要隔一個blank line。
但只有case間要空行,最後一個case印完後不能有多餘的空行。 (很嚴格的的格式要求...)

新版的AC Code

2008年11月16日 星期日

UVa 111 History Grading

這題說穿就是LIS,對於已經精通LIS的我自然是小菜一碟(咦?)
不過這題有個陷阱,如果沒仔細讀懂題目的話,會以為只要做一次轉換,其實上要做兩次轉換。
第一次把rank轉成真正的event sequence,(rank[] => seq[])
第二次才轉成可以做LIS的形式。(seq[] => seq2[])
剛開始送了兩個WA,後來看事有悉蹺,(sample output怪怪的),改了一下就AC了。

2008年11月10日 星期一

UVa 103 Stacking Boxes

題目講解

這題給你一堆多維的箱子,要找出最長的裝箱序列,這個最常裝箱序列就是像俄羅斯娃娃那樣,大箱子裡面放入小箱子,一層包一層,必須要可以裝最多層這樣。

這題的麻煩就是各個箱子之間不一定有的大小關係 (數學上打這叫偏序集 Partial Order Set ,不過這兒我們先不管 ),比方說有兩個三維箱子 BoxA(1,4,5) 、BoxB(2,4,6) ,B箱比較大,所以 BoxA 可以裝進 BoxB 裡,那麼我們說 BoxA < BoxB 。

但來看 BoxC(1,5,6) 跟 BoxD (2,4,5) 呢? 我們既不能說BoxC < BoxD ,也不能說 BoxC > BoxD,BoxC 與 BoxD 兩者之間就沒有大小關係。

一個簡單的表示法就是有向圖(Directed Graph)
比如說 A(1,2,3) B(2,4,6) C(2,3,7) D(50,50,50) E(10,10,100) 的有向圖表示法:



到此為止,本題的最長裝箱序列,已經有兩種解法,第一個方法就是找圖的最長路徑,稍微修改 Warsahll algorithm 來解,第二個方法是跑 LIS 。

我這裡用 LIS(最長上昇子串列) 解法。

//先定義一個box struct
struct Box {
    int no;
    int edge[10];
};

Box box[30]; 

LIS 法的關鍵是要先對箱子排序,確保小箱子一定在大箱子前,至於沒有大小關係箱子的就隨便放沒關係。這個排序以圖的角度是拓樸排序,以字串的角度是字典排序,兩者都行。

sort(box[i].edge) for all i  //先對箱子內部的邊長排序

int lexico_less(const Box& a, const Box& b) {
    for(int i=0;i<dimension;++i)
        if( !(a.edge[i]<=b.edge[i]) )
            return false;
    return true;
}
sort(box) by lexico_less(); //再用字典序排箱子
一切都準備好後,就可以直接套用LIS解了。
// LIS
int length[MAX_BOX];
int   prev[MAX_BOX];

length[i] = 1  for all i;
  prev[i] = -1 for all i;

for(int i=0;i<num_box;++i)
    for(int j=i+1;j<num_box;++j) {
        if( box[i]<box[j] ) {
            if(length[i]+1 > length[j] ){
                length[j] = length[i]+1;
                prev[j] = i;
            }
        }
    }
輸出結果
    int max = max_element(length, length+num_box) - length;
    //print the result
    printf("%d\n", length[max]);

    int output_seq[MAX_BOX];
    int size = 0;

    int cur = max;
    do {
        output_seq[size++] = box[cur].no;
        cur = prev[cur];
    } while( cur!= -1 );

    for(int i=size-1;i>0;--i)
        printf("%d ", output_seq[i]);
    printf("%d\n", output_seq[0]);
}

碎碎念

值得慶賀的事,Ranking 進世界百大!!!! 我相信這是誤打誤撞XDDD,不過真的蠻爽的。 @2008.11.10

[Algo] String Matching - KMP Algorithm

看了兩次,可是每次都忘記,所以做個筆記
s: input string
p: pattern

Failure Function的值k,就是下次要從p(k)開始matching

舉例

Pattern A B C A B C D
failure -1-1-1 0 1 2-1

Case I:
Input string
ABCDADFGACEDAABBBB
ABCABCD

紅色=not matching
step1: 看最後一個matching字元 (綠色的字) 的failure function value= f
step2: 將p(f)對齊綠色的位置 ( p(i)代表p的第i個字元 )

ex. f(C) = -1 ,所以p(-1)對齊上面那排的C
ABCDADFGACEDAABB
>>>ABCABCD

Case II:
ABCABCEACAADDBBBABCABC
ABCABCD

f(C)=2 ,所以p(2)對齊上面那排的綠色C

ABCABCEACAADDBBBABCABC
>>>ABCABCD


講的不是很有條理,不過我先給自己看懂就好= =
改天再來整理的清楚一些