ACM_kirakira: T-414-ÁFLV Lecture 1 Homework 續: Kattis一題 + Operator Overload (Updated 2015-05-09)

(經GG提醒後有所Update, 全以紅字表示)
經上一篇由於要做功課的關係得知了Kattis這個OJ

經GG口中所說原來這個OJ水準也不錯, 題目很新很有趣

是由 KTH 的人研製出來的

有見及此, 我隨便找了一題difficulty 不錯的題目來試刀
上一篇所說的最難Bonus題目difficulty是4.4
這次選了一題difficulty 4.8的, 叫 Almost Union-Find

Kattis: Almost Union Find

Almost Union Find (Data Structure Usage, STL, Disjoint Set)

題目: https://open.kattis.com/problems/almostunionfind

題目標題已經出現了很久沒接觸的字眼: Disjoint Set / Union-Find data structure!

題目給了 n 個不同的數字和 m 個query (n, m <= 10^5)

代表的是每個query 要在 O(lg n) 內完成了, 總時間最大 O(m lg n)

題目給了 3種不同的query, 有點像是Union-Find的:

Union p 跟 q, 要是已經在同一Set 則無視
把 p 由現在的 Set 移動到包含了 q 的 Set, 要是已經在同一Set 則無視
報告包含 p 的 Set 現在的 Size 跟 Sum

入手立即從Union-Find能做到的事開始想...

發現不太記得怎樣Code, 順手 wiki 了一下, 借此重溫這個強大的東西:

這個Disjoint Forest的任何operation速度都depends on depth
存在2種方法可以盡力把depth 變小

Union by Rank: 在Union()時, 永遠把depth少的tree 加到 depth 大的tree
Path Compression: 在Find()時, 把所有經過的node的root 直接設定到最高的root
第一種方法已經令所有operation 變成O(lg N); 第二種方法更加使複雜度變成O(alpha(N)), alpha(N) 就是 inverse of Ackermann function, 直接就其實就是變成O(1)了, 2種加速手法複雜度證明我就沒深究了

分析這題題目的話, Disjoint Set本身已經能處理第1種和第3種query, 但是第2種query : Move()

則有點難度了...原因在於要是用Disjoint Set的的結構處理這種operation

明顯要知道所有點的children, 而且在移動時要把它的children移動到它的parent / root...

這樣做法最差已經是O(N)了, 不可取

由於限制了要O(lg N)內完成這種operation, 我最能直接想到的就是STL中的Set

只要一個erase(), 一個insert() 就完了, 但是STL:Set 又不能好好的處理另外2種operations...

運氣又到了, 我忽發奇想, 要是我把Disjoint Set 跟 STL:Set一起用呢?

Simulate了一下小的Test Case好像可行的樣子:

圖像化來說, 我把資料分成三層:

真正的data: 1,2,3,...n; 設一個array叫 curSet[] 記錄數字 i 現在所在的Set index
STL: Set: 真正的Set, 真正的儲存了數字, 可能某些Set在某些時間是空的
Disjoint Set: 一個array sp[], 第 i 格代表第 i 個Set 的 root

簡單地說, 我把Disjoint Set apply在 STL:Set 之上

記錄的是那一個Set跟那一個Set已經Union了, 還有這些Set的 Size 跟Sum

而實際上的移動 (operation 2) 則在 STL:Set那一層進行, 同時用O(1) 可以Update到

curSet[]

沒有太多的證明, 過了sample case就交了, 一棍AC

現在可以試試說服自己為何這樣做OK

首先複雜度是肯定沒問題的: operation 1跟3 只是普通的Disjoint Set, 而operation 2 則是 STL:Set

所以最多每個operation也只是O(lg n)

正確性來說呢

先來看Operation 2 (跟Disjoint Set最不同的operation...)

由於過程是直接從Set中移動, 每次移動時同時Update curSet[], 也update 2個相關的Set 所屬的Disjoint Set 的Sum[] 跟Size[]....這樣就維護了所有以後operation所需的狀態正確性

再來看Operation 1, Union() 是把Set 的index 作一個關係,

相對的Find(), 也可以從某個Set index 找到它所屬的 Disjoint Set的root,

這樣Sum[] 跟Size[] 可以直接改動 root 那個Set的, curSet[]則不用改

例如數字 1 是在 Set 3內面, 而Set 3現在跟Set 5 Union, 我們會改的是:

Set 3 的root, Set 5 的Sum 跟Size, 數字1 仍然是在Set 3 內面不用改curSet[]

最後是Operation 3, 我們可以由curSet[] 知道某數字存在的Set index, 然後可以由Find()找出這個Set 所在的 Disjoint Set 的root (另一個Set的index)

而由上面所改動的Sum[], Size[]也是在root 這個Set上維護的, 所以直接output root的Sum跟Size就可以了...

大約就是這樣吧...沒太嚴謹但還算是logically correct吧?
~~AC Code: https://open.kattis.com/submissions/717636~~
好吧昨晚太累了也沒想清楚, 其它人是看不到我的Submission的...
所以直接把code貼出來

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
int n,m,t,p,q;
LL sp[100010], size[100010], sum[100010], curSet[100010];
set<int> data[100010];
 
void init(){
    for(int i=0; i<100010;i++){
        sp[i] = i; size[i] = 1; sum[i] = i; curSet[i] = i;
        data[i].insert(i);
    }
}
 
int find(int x){ // pass curset of x
    return sp[x] == x? x : sp[x] = find(sp[x]);
}
 
void Union(int x, int y){
    int sx = find(curSet[x]), sy = find(curSet[y]);
    if(sx == sy) return;
    sp[sx] = sy; sum[sy] += sum[sx]; size[sy] += size[sx];
}
 
void move(int x, int y){
    int sx = curSet[x], sy = curSet[y];
    if(sx == sy) return;
    data[sx].erase(x); sum[find(sx)]-=x; size[find(sx)]--;
    data[sy].insert(x); sum[find(sy)]+=x; size[find(sy)]++;
    curSet[x] = sy;
}
 
int main(){
    while(scanf("%d%d", &n, &m) != EOF){
        init();
        for(int i=0; i<m;i++){
            scanf("%d%d", &t, &p);
            if(t != 3) scanf("%d", &q);
            if(t == 1) Union(p,q);
            else if(t == 2) move(p,q);
            else printf("%lld %lld\n", size[find(curSet[p])], sum[find(curSet[p])]);
        }
    }
    return 0;
}

而經GG的提醒下, 這題確實可以以O(alpha(N)), 純Disjoint Set去解的...
Operation 2 等於要delete 一個node, 我原本的想法是physically真的要delete...
導出上面我說的結論: 要移動它所有children...etc

但其實根本可以不用真的delete它...留它在原本的地方就好了...
反正我們也可以照樣update size[] 跟sum[]....另外再allocate 一個新的node 去新的root之下就好了....下面補上紅字User GG的 O(alpha(N)) 的Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#define FOR(i,s,e) for (int i=(s); i<(e); i++)
#define FOE(i,s,e) for (int i=(s); i<=(e); i++)
#define FOD(i,s,e) for (int i=(s)-1; i>=(e); i--)
#define CLR(a,x) memset(a, x, sizeof(a))
#define EXP(i,l) for (int i=(l); i; i=qn[i])
#define LLD long long
#define N 200005
using namespace std;
 
int n, m, x, y, rx, ry, op;
int p[N], c[N], a[N];
LLD s[N];
 
int find(int x){
    if (x == p[x]) return x;
        return p[x] = find(p[x]);
}
 
int main(){
        while (scanf("%d%d", &n, &m) != EOF){
                FOR(i,0,n){
                        a[i+1] = i;
                        s[i] = i + 1;
                        c[i] = 1;
                        p[i] = i;
                }
                while (m--){
                        scanf("%d", &op);
                        if (op == 1){
                                scanf("%d%d", &x, &y);
                                if (find(a[x]) == find(a[y])) continue;
                                x = find(a[x]), y = find(a[y]);
                                s[y] += s[x];
                                c[y] += c[x];
                                p[x] = y;
                        }
                        if (op == 2){
                                scanf("%d%d", &x, &y);
                                rx = find(a[x]), ry = find(a[y]);
                                if (rx == ry) continue;
                                c[rx]--, s[rx] -= x;
                                c[ry]++, s[ry] += x;
                                p[n] = ry;
                                a[x] = n++;
                        }
                        if (op == 3){
                                scanf("%d", &x);
                                x = find(a[x]);
                                printf("%d %lld\n", c[x], s[x]);
                        }
                }
        }
        return 0;
}

運行速度比我的做法快了一倍, 由0.28s --> 0.14s, 也簡單易code也簡單易明 (correctness self-explained)

另外由於這篇不想太短, 我也歸納了上一篇最後帶出的一個問題:
C++ Struct的 operator是怎樣寫overload的呢? 上一篇我說是不知道

巧合之下我發現了Stack Overflow的一個 Post, 解釋得還算很清楚:

http://stackoverflow.com/questions/14047191/overloading-operators-in-typedef-structs-c

Finally, in answering your question, what is the difference between a member function or operator declared as const and one that is not?

A const member declares that invoking that member will not modifying the underlying object (mutable declarations not withstanding). Only const member functions can be invoked again const objects references and pointers. For example, your operator +() does not modify your local object and thus should be declared as const. Your operator =() clearly modifies the local object, and therefore the operator should not be const.

所以說:重點是在於該operator的implementation內會否改動到你object內的東東

決定了要不要 bool operator() const {} 中的const

至於parameter的 const是速度的考慮:

All of your input parameters to all of your members are currently making copies of whatever is being passed at invoke. While it may be trivial for code like this, it can be very expensive for larger object types. An exampleis given here:

所以合起來就是:

// assignment operator modifies object, therefore non-const
    pos& operator=(const pos& a)
    {
        x=a.x;
        y=a.y;
        return *this;
    }

    // addop. doesn't modify object. therefore const.
    pos operator+(const pos& a) const
    {
        return pos(a.x+x, a.y+y);
    }

這樣理解還算很易記, 也解開了心中一個疑問...

PS: 今天還看了之前Codeforces #300 的Problem G Editorial...我認為要進步就要盡力看跟學..即使這題的AC人數還是只有雙位數....肯好還算明白, 等有時間Implement完就再Edit那一篇補充好了...至於之前的GCJ Round 1B, 我也做了B-Large, 看了Solution後, 明白了B跟C...C還沒做, 至於A是看了也不明白, 好像有點事情它沒有Proof的樣子...只能說B-Large其實絕對是可以做得出來的...也是一樣等做得夠完整才一篇長篇說吧...

PS2: Segment Tree再深究了一下, 做了一題SPOJ的題目, 那一題可以下篇長篇說一下, 同時學習了:

如何用BIT 做 Range Update (Add)
Segment Tree in general的結構, 還有關於push down (split / lazy propagation) 跟merge的一點理解

還是同一句真的忙死了...

再多一句: 希望GCJ 1C順順利利 (反正只能打一個小時多一點就要出門了=.=)

ACM_kirakira

2015年5月8日星期五

T-414-ÁFLV Lecture 1 Homework 續: Kattis一題 + Operator Overload (Updated 2015-05-09)

Kattis: Almost Union Find

Almost Union Find (Data Structure Usage, STL, Disjoint Set)

沒有留言:

張貼留言

2015年5月8日 星期五

T-414-ÁFLV Lecture 1 Homework 續: Kattis一題 + Operator Overload (Updated 2015-05-09)

Kattis: Almost Union Find

Almost Union Find (Data Structure Usage, STL, Disjoint Set)

沒有留言:

張貼留言

2015年5月8日星期五