20120116

ACM 481 What Goes Up

Longest Increasing Subsequence問題。
用正常的O(n ^ 2)的演算法去解竟然會TL,傻眼……
結果只好開始看別人是怎麼AC的。
結果AC一定要用O(nlogn)的演算法……
就開始看……我發現我看不懂 ToT。

反正就是找了一堆資料,然後寫法都很數學式,又是英文,
而且又沒範例 = =,只能說GG啊。

最後還是在這裡
找到範例碼,真是揪甘心~

重點就是要了解Patience sorting的運作原理即可。
Patience sorting大概是這樣:
1.如果沒有pile,就做一個pile。
2.每次把x值與pile最上的值相比,若x值 < pile的top值,
就把x放到該pile上。
若無,就再做一個pile。
3.反覆,到沒有x值為此。

這樣講可能很複雜,直接舉實例說明:
-7 10 9 2 3 8 8 1。
一開始是-7,沒pile,所以給-7一個pile:
-7,
接著是10,10 > -7,所以make a new pile:
-7
10,
再來是9, 9 > -7,所以不能放在pile1,
但9 < 10,所以放在pile2上,
-7
10 9,
反覆此動作我們最後可以得到:
-7
10 9 2 1
3
8
(因為Patience sorting是針對撲克牌做sort,
所以有重複的數字,我們就不再處理第二次)
如此,我們得到4個pile。
也就是lis為4。
第1到第4個位置分別可以放-7、10 9 2 1、3、8。
注意,上面這個例子並不表示,所有lis為4的組合……
也就是每個數字其實是獨立的,不能放在一起看,
除非我們找到一組順序,使得此子序列的對應關係合於本來的序列。
好吧,其實我不是很懂Patience sorting……
總之pile數 = lis數就對了!
那這樣要怎麼找到一組lis呢?
現在我們已經知道,每個位置能放的值了,
所以按照題目要求,我們只要從最末的值開始往前找即可。
這部份就跟O(n ^ 2)的方法是一樣的。

接著談實作,實作非常之令我苦惱……
所謂懂還不一定寫得出程式碼,就是這回事,囧。
首先要做出一個pile,所以讓seq[0]為第一個pile,
然後我們可以發現,Patience sorting其實是一個遞增數列(這應該是重點)。
也就是說,每個pile最上面的值,排在一起,一定為遞增數列。
既然是遞增,那我們可以用binary search去做search的動作。
(因為已經sort,所以可以用bin search)
兩種情況:
(1)seq[x]的值,比最後一個pile 的top值還大,就增加一個pile。
因為我們已知所有pile的top為一遞增數列,
那如果seq[x] > 最後一個pile的top值,
勢必seq[x],大於所有pile的tope值,
所以這時候就要增加一個pile。
(2)非(1)的情況,表示seq[x] <= 最後一個pile的top值。
這時候,seq[x]這個值,可能跟前面某個pile的top值一樣,
或是介於某兩個pile值之間的情況。
如果是前者,那我們找到seq[x] == pile top時,任務就結束了。
如果是後者,那我們會得到pile[i] top < seq[x] < pile[i + 1] top。
這時,需把pile[i + 1]的top換成seq[x]才行。
如此才符合Patience sorting的第二個定義。

所以我們可以得到一種資料結構:stack包含stack,
但是實作上不用這麼麻煩,只要用stack + 取代就好了。
其實更好的作法是再用一個空間,去紀錄每個seq[x]的在lis位置,
就是紀錄他在哪個pile啦!用空間換取時間!

這樣,我們已經知道了pile數(lis長度),
也紀錄了每個seq[x]所在lis長度的位置,
那麼這題就有解了!
從最後一個seq[x]往前到seq[0],去尋找符合lis長度的值,
找到該值後記錄下來,再把lis長度 - 1,同樣做找值的動作,
一直找到第一個lis為止。
如此,就是答案了。

另外為什麼是O(n * log(n))呢,
因為binary search是O(log(n)),
而有n個值,最慘的情況就是每個值都去做binary search,
那就會得到O(n * log(n))。

再一次感謝DJWS~
有興趣可以再看一些參考資料
wiki跟algorithmist都有。

/* ACM 481 What Goes Up
 * mythnc
 * 2012/01/16 09:58:36   
 * run time: 0.044
 */
#include <stdio.h>

#define MAXN 100000

void lis(int);
void binsearch(int, int, int);

int n;
int seq[MAXN], pos[MAXN], v[MAXN];

int main(void)
{

    n = 0;
    while (scanf("%d", &seq[n]) == 1)
        n++;

    lis(n);

    return 0;
}

/* lis: return the last max len position */
void lis(int n)
{
    int len, i, j;
    int out[MAXN];

    len = 0;
    v[len++] = seq[0];
    pos[0] = 0;

    for (i = 1; i < n; i++) {
        if (seq[i] > v[len - 1]) {
            v[len] = seq[i];
            pos[i] = len++;
        }
        else
            binsearch(0, len, i);
    }
    /* output */
    printf("%d\n-\n", len);
    for (i = n - 1, j = len - 1; i > -1 && j > -1; i--)
        if (pos[i] == j) {
            out[j] = seq[i];
            j--;
        }
    for (i = 0; i < len; i++)
        printf("%d\n", out[i]);
}

void binsearch(int begin, int end, int index)
{
    int mid;

    while (begin <= end) {
        mid = (begin + end) / 2;
        if (v[mid] == seq[index]) {
            pos[index] = mid;
            return;
        }
        else if (v[mid] > seq[index])
            end = mid - 1;
        else
            begin = mid + 1;
    }
    
    mid = (begin + end) / 2;
    if (mid == 0 && index == 1) {
        v[0] = seq[index];
        pos[index] = 0;
    }
    else {
        v[mid + 1] = seq[index];
        pos[index] = mid + 1;
    }
}

沒有留言: