Skip to content

Instantly share code, notes, and snippets.

@blmarket

blmarket/E-fail.cc

Last active August 29, 2015 14:03
Show Gist options
  • Save blmarket/d027d3a998dca0262d9f to your computer and use it in GitHub Desktop.
Save blmarket/d027d3a998dca0262d9f to your computer and use it in GitHub Desktop.
Download ZIP
ICPC 2014 E Maze Reduction
Raw
README.md

Maze Reduction

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

문제 소개

링크 참조

기본 풀이 아이디어

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

CtrlV Free Image Hosting
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.

Raw
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;
}
Raw
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;
}
Raw
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;
}
Raw
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);
+ }
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment