ICPC 2014 E Maze Reduction

README.md

Maze Reduction

기본 아이디어는 쉽게 얻었으나, 실제 구현하는 과정에서 삽질한 사례 소개. 강한 스포일러가 포함되어 있으니 위 문제를 풀 생각이 있는 사람이라면 스킵하는 것을 권장합니다.

문제 소개

링크 참조

기본 풀이 아이디어

room A와 B가 각각 서로 다른 갯수의 문을 갖고 있다면, 두 개의 방은 서로 구분가능하다. 이어서 A로 연결되는 임의의 복도 a와, B로 연결되는 임의의 복도 b 또한 서로 구분가능해 진다. 이 복도 a가 (X, A)를 연결하는 녀석이고, b는 (Y, B)를 연결하는 녀석이라고 하자. 이때 X, Y 만으로는 서로 구분하는 것이 불가능하지만, 다음과 같이 다른 경로들을 서로 구분가능한 것으로 결정할 수 있다.

Image hosted for free at CtrlV.in

X, Y가 각각 3개의 문을 갖고있는 경우라고 한다면, a1과 b1은 서로 구분가능한 복도가 된다.(해당 경로를 다 걸어간 다음, 도달한 방에서 바로 오른쪽에 있는 문을 열고 이동하면 서로 다른 A 혹은 B 방이 나와 자기가 a1에 있는지, b1에 있는지 구분가능해진다. a2, b2도 마찬가지. 결국 어떤 구분가능한 복도쌍을 가지고 있는 경우 다른 구분가능한 복도쌍을 만들어나갈 수 있고, 이것들을 통해 모든 구분가능한 복도쌍을 계산해낼 수 있게 된다.

구분가능한 복도쌍을 만들어낸 이후, 방과 방을 서로 구분하는 것은 비교적 trivial한 문제다. 일단 서로 문 갯수가 다르면 당연히 서로 구분가능한 방들인 것이고, 같은 경우, 한바퀴 돌면서 순서대로 문을 매칭했을 때 모두 구분 불가능한 경우가 있다면 두 방을 구분할 수 없는 것이고, 그런 경우가 없다면 두 방을 구분할 방법이 있다는 것이렷다.

실제 풀이 코드

위 아이디어를 가급적 그대로 구현한 코드는 아래와 같다.

https://gist.github.com/blmarket/d027d3a998dca0262d9f#file-e-fail-cc

이 코드는 두 가지가 틀렸다. 먼저, 문 갯수가 0개인 경우, '한바퀴 돌면서 문을 매칭'하는 과정이 아예 안돌아가는 바람에 두 방을 구분할 수 있다는 것으로 나와버렸고, 그 다음에는 call stack이 깊게 들어가지면서 segmentation fault가 발생하는 경우가 있었다.

https://gist.github.com/blmarket/d027d3a998dca0262d9f#file-e2-success-cc

위에서 발생한 버그들을 아이디어를 유지하면서 수정한 코드. 근데 어디서 틀렸는지 알 수가 없는 대회 환경에선 이런 버그 잡기 정말 어려워진다. 아이디어 단계에서부터 좀 더 쉽게 구현가능한 레벨의 아이디어를 고민했다면, 좀 더 버그 잡기 쉬운 풀이가 가능했을 것이다.

https://gist.github.com/blmarket/d027d3a998dca0262d9f#file-ee-cc

bmerry의 블로그 글을 읽고 다시 풀어본 코드. iteration을 돌면서 라벨링을 수행하기 때문에, 버그가 있더라도 중간중간 라벨링을 찍어보는 것이 가능하다.

Written with StackEdit.

E-fail.cc

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <numeric>
#include <iterator>
#include <queue>
#include <set>
#include <map>
#include <vector>

#define mp make_pair
#define pb push_back
#define sqr(x) ((x)*(x))
#define foreach(it,c) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

template<typename T> int size(const T &a) { return a.size(); } 

int n;
vector<int> rr[105];
char diff[105][105][105][105];

void add_diff(int s1, int e1, int s2, int e2) {
    if(diff[s1][e1][s2][e2]) return;
    diff[s1][e1][s2][e2] = 1;
    if(rr[s1].size() != rr[s2].size()) return;

    int p1 = find(rr[s1].begin(), rr[s1].end(), e1) - rr[s1].begin();
    int p2 = find(rr[s2].begin(), rr[s2].end(), e2) - rr[s2].begin();

    int sz = size(rr[s1]);
    for(int i=1;i<sz;i++) {
        int pp1 = rr[s1][(p1 + i) % sz];
        int pp2 = rr[s2][(p2 + i) % sz];
        add_diff(pp1, s1, pp2, s2);
    }
}

bool check_diff(int a, int b) {
    int sz = size(rr[a]);
    for(int i=0;i<sz;i++) {
        bool same = true;
        for(int j=0;j<sz;j++) {
            int n1 = rr[a][j];
            int n2 = rr[b][(i+j)%sz];
            if(diff[a][n1][b][n2]) { same = false; break; }
        }
        if(same) return true;
    }
    return false;
}

int main(void) {
    scanf(" %d", &n);
    for(int i=0;i<n;i++) {
        int m;
        scanf(" %d", &m);
        rr[i].resize(m);
        for(int j=0;j<m;j++) {
            scanf(" %d", &rr[i][j]);
            rr[i][j]--;
        }
    }

    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            if(rr[i].size() == rr[j].size()) continue;
            for(auto a: rr[i]) {
                for(auto b: rr[j]) {
                    add_diff(a, i, b, j);
                    add_diff(b, j, a, i);
                }
            }
        }
    }

    bool chk[105];
    memset(chk, 0, sizeof(chk));

    bool none = true;
    for(int i=0;i<n;i++) if(!chk[i]) {
        chk[i] = true;
        vector<int> V;
        V.pb(i);
        for(int j=i+1;j<n;j++) if(!chk[j]) {
            if(rr[i].size() != rr[j].size()) continue;
            if(check_diff(i, j)) {
                V.pb(j);
                chk[j] = true;
                continue;
            }
        }
        if(V.size() > 1) {
            none = false;
            for(int j=0;j<size(V);j++) cout << V[j]+1 << " ";
            cout << endl;
        }
    }
    if(none) {
        cout << "none" << endl;
    }

    return 0;
}

E2-success.cc

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <numeric>
#include <iterator>
#include <queue>
#include <set>
#include <map>
#include <vector>

#define mp make_pair
#define pb push_back
#define sqr(x) ((x)*(x))
#define foreach(it,c) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

template<typename T> int size(const T &a) { return a.size(); } 

int n;
vector<int> rr[105];
char diff[105][105][105][105];

void add_diff(int s1, int e1, int s2, int e2) {
    if(rr[s1].size() != rr[s2].size()) return;

    int p1 = find(rr[s1].begin(), rr[s1].end(), e1) - rr[s1].begin();
    int p2 = find(rr[s2].begin(), rr[s2].end(), e2) - rr[s2].begin();

    int sz = size(rr[s1]);
    vector<tuple<int, int, int, int> > VT;
    for(int i=1;i<sz;i++) {
        int pp1 = rr[s1][(p1 + i) % sz];
        int pp2 = rr[s2][(p2 + i) % sz];
        if(diff[pp1][s1][pp2][s2] == 0) {
            VT.pb(make_tuple(pp1, s1, pp2, s2));
            diff[pp1][s1][pp2][s2] = 1;
        }
    }
    for(int i=0;i<size(VT);i++) {
        int a,b,c,d;
        tie(a,b,c,d) = VT[i];
        add_diff(a,b,c,d);
    }
}

bool check_diff(int a, int b) {
    int sz = size(rr[a]);
    if(sz == 0) return true;
    for(int i=0;i<sz;i++) {
        bool same = true;
        for(int j=0;j<sz;j++) {
            int n1 = rr[a][j];
            int n2 = rr[b][(i+j)%sz];
            if(diff[a][n1][b][n2]) { same = false; break; }
        }
        if(same) return true;
    }
    return false;
}

int main(void) {
    scanf(" %d", &n);
    for(int i=0;i<n;i++) {
        int m;
        scanf(" %d", &m);
        rr[i].resize(m);
        for(int j=0;j<m;j++) {
            scanf(" %d", &rr[i][j]);
            rr[i][j]--;
        }
    }

    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            if(rr[i].size() == rr[j].size()) continue;
            for(auto a: rr[i]) {
                for(auto b: rr[j]) {
                    if(diff[a][i][b][j] == 0) {
                        diff[a][i][b][j] = 1;
                        add_diff(a, i, b, j);
                    }
                }
            }
        }
    }

    bool chk[105];
    memset(chk, 0, sizeof(chk));

    bool none = true;
    for(int i=0;i<n;i++) if(!chk[i]) {
        chk[i] = true;
        vector<int> V;
        V.pb(i);
        for(int j=i+1;j<n;j++) if(!chk[j]) {
            if(rr[i].size() != rr[j].size()) continue;
            if(check_diff(i, j)) {
                V.pb(j);
                chk[j] = true;
                continue;
            }
        }
        if(V.size() > 1) {
            none = false;
            for(int j=0;j<size(V);j++) cout << V[j]+1 << " ";
            cout << endl;
        }
    }
    if(none) {
        cout << "none" << endl;
    }

    return 0;
}

EE.cc

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <numeric>
#include <iterator>
#include <queue>
#include <set>
#include <map>
#include <vector>

#define mp make_pair
#define pb push_back
#define sqr(x) ((x)*(x))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

template<typename T> int size(const T &a) { return a.size(); } 

int n;
VI links[105];
VI label[105];
vector<PII> ls[150005];

VI get_doorsig(int s, int e) {
    int sz = size(links[e]);
    int ii = find(all(links[e]), s) - links[e].begin();

    VI ret;
    for(int i=0;i<sz;i++) {
        ret.pb(label[e][(ii+i)%sz]);
    }
    return ret;
}

VI roomsig(int s) {
    int sz = size(links[s]);
    VI ret;
    for(int i=0;i<sz;i++) {
        VI tmp; tmp.clear();
        for(int j=0;j<sz;j++) {
            tmp.pb(label[s][(i+j)%sz]);
        }
        if(ret.size() == 0 || ret > tmp) ret = tmp;
    }
    return ret;
}

int main(void) {
    scanf(" %d", &n);
    for(int i=0;i<n;i++) {
        int m;
        scanf(" %d", &m);
        links[i].resize(m);
        for(int j=0;j<m;j++) {
            scanf(" %d", &links[i][j]);
            links[i][j]--;
            ls[m].pb(mp(i, links[i][j]));
        }
        label[i] = vector<int>(m, m);
    }

    int mm = 105;
    while(true) {
        bool change = false;
        // for(int i=0;i<mm;i++) {
        //     if(ls[i].size() == 0) continue;
        //     cout << i << " : ";
        //     for(int j=0;j<size(ls[i]);j++) {
        //         cout << ls[i][j].first << "-" << ls[i][j].second << " ";
        //     }
        //     cout << endl;
        // }

        for(int i=0;i<mm;i++) {
            if(ls[i].size() < 2) continue;
            map<VI, vector<PII> > M;
            M.clear();
            for(int j=0;j<size(ls[i]);j++) {
                VI tmp = get_doorsig(ls[i][j].first, ls[i][j].second);
                M[tmp].pb(ls[i][j]);
            }
            if(size(M) == 1) continue;
            change = true;
            for(auto &it : M) {
                ls[mm] = it.second;
                for(PII jt : it.second) {
                    int a,b;
                    tie(a,b) = jt;
                    for(int j=0;j<size(links[a]);j++) if(links[a][j] == b) {
                        label[a][j] = mm;
                    }
                }
                mm++;
            }
            ls[i].clear();
        }
        if(!change) break;
    }

    VVI sigs(n);
    for(int i=0;i<n;i++) {
        sigs[i] = roomsig(i);
    }

    vector<bool> used(n, 0);
    bool none = true;
    for(int i=0;i<n;i++) if(used[i] == false) {
        used[i] = true;
        vector<int> V; V.clear(); V.pb(i);
        for(int j=i+1;j<n;j++) if(!used[j] && sigs[i] == sigs[j]) {
            used[j] = true;
            V.pb(j);
        }
        if(V.size() == 1) continue;
        none = false;
        for(int j=0;j<size(V);j++) {
            cout << V[j]+1 << " ";
        }
        cout << endl;
    }

    if(none) {
        cout << "none" << endl;
    }

    return 0;
}

test.diff

--- E-fail.cc	2014-06-27 13:15:50.000000000 +0900
+++ E2-success.cc	2014-06-27 22:38:45.000000000 +0900
@@ -30,23 +30,31 @@
 char diff[105][105][105][105];
 
 void add_diff(int s1, int e1, int s2, int e2) {
-    if(diff[s1][e1][s2][e2]) return;
-    diff[s1][e1][s2][e2] = 1;
     if(rr[s1].size() != rr[s2].size()) return;
 
     int p1 = find(rr[s1].begin(), rr[s1].end(), e1) - rr[s1].begin();
     int p2 = find(rr[s2].begin(), rr[s2].end(), e2) - rr[s2].begin();
 
     int sz = size(rr[s1]);
+    vector<tuple<int, int, int, int> > VT;
     for(int i=1;i<sz;i++) {
         int pp1 = rr[s1][(p1 + i) % sz];
         int pp2 = rr[s2][(p2 + i) % sz];
-        add_diff(pp1, s1, pp2, s2);
+        if(diff[pp1][s1][pp2][s2] == 0) {
+            VT.pb(make_tuple(pp1, s1, pp2, s2));
+            diff[pp1][s1][pp2][s2] = 1;
+        }
+    }
+    for(int i=0;i<size(VT);i++) {
+        int a,b,c,d;
+        tie(a,b,c,d) = VT[i];
+        add_diff(a,b,c,d);
     }
 }
 
 bool check_diff(int a, int b) {
     int sz = size(rr[a]);
+    if(sz == 0) return true;
     for(int i=0;i<sz;i++) {
         bool same = true;
         for(int j=0;j<sz;j++) {
@@ -72,12 +80,14 @@
     }
 
     for(int i=0;i<n;i++) {
-        for(int j=i+1;j<n;j++) {
+        for(int j=0;j<n;j++) {
             if(rr[i].size() == rr[j].size()) continue;
             for(auto a: rr[i]) {
                 for(auto b: rr[j]) {
-                    add_diff(a, i, b, j);
-                    add_diff(b, j, a, i);
+                    if(diff[a][i][b][j] == 0) {
+                        diff[a][i][b][j] = 1;
+                        add_diff(a, i, b, j);
+                    }
                 }
             }
         }