Vase collection

http://acm.pku.edu.cn/JudgeOnline/problem?id=1632

Description

Mr Cheng is a collector of old Chinese porcelain, more specifically late 15th century Feng dynasty vases. The art of vase-making at this time followed very strict artistic rules. There was a limited number of accepted styles, each defined by its shape and decoration. More specifically, there were 36 vase shapes and 36 different patterns of decoration ? in all 1296 different styles.
For a collector, the obvious goal is to own a sample of each of the 1296 styles. Mr Cheng however,like so many other collectors, could never afford a complete collection, and instead concentrates on some shapes and some decorations. As symmetry between shape and decoration was one of the main aestheathical paradigms of the Feng dynasty, Mr Cheng wants to have a full collection of all combinations of k shapes and k decorations, for as large a k as possible. However, he has discovered that determining this k for a given collection is not always trivial. This means that his collection might actually be better than he thinks. Can you help him?

Input

On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer m <= 100, the number of vases in the collection. Then follow m lines, one per vase, each with a pair of numbers, si and di, separated by a single space, where si ( 0 < si <= 36 ) indicates the shape of Mr Cheng's i:th vase, and di ( 0 < di <= 36 ) indicates its decoration.

Output

For each test scenario, output one line containing the maximum k, such that there are k shapes and k decorations for which Mr Cheng's collection contains all k*k combined styles.

Source

Northwestern Europe 2003


Solving

챙이 모으는 도자기에는 36개의 모양과 36개의 무늬패턴이 있고 따라서 조합하면 1296개의 스타일이 있다. 챙은 1296개의 도자기를 다 모으고 싶지만 다 모으기가 쉽지않다. 도자기들의 모양과 패턴이 주어졌을 k개의 모양과 패턴의 조합을 모두 모을 수 있는 최대의 k를 구하라

모양과 무늬를 왔다갔다하면서 연결성을 찾으려고 하면 문제가 무한대로 어려워진다.
모양의 조합을 선택하였을 때 무늬가 어떻게되는지를 따져보자.

우선, i번째 도자기를 Pi, i번째 모양의 도자기와 연결된 무늬(Decoration)의 집합을 Di라고 이라고 정의하자.
Ai와 Aj를 선택한 경우 양쪽에 모두 연결된 무늬는 Di ∩ Dj 이다.
이제 슬슬 감이 오기 시작한다.

선택한 도자기의 집합 S를 S={s1, s2, ..., sn}, n:선택한 도자기의 수 이라고 정의하면, 선택한 도자기의 집합과 모두 연결된 무늬는 D = D(s1) ∩ D(s2) ∩ ... ∩ D(sn) 이다. D에 남아있는 무늬의 수가 n보다 큰 경우 n개의 모양과 패턴의 모든 조합을 완성할 수 있다.

n을 2부터 늘려가면서(1은 무조건 된다) 최대치를 찾거나 바이너리 서치를 한다.
문제는 모든 도자기의 집합을 구하여야 한다는 것인데, 모든 경우의 수가 2^36으로 너무 크다. 하지만 입력으로 주어지는 도자기의 수가 최대 100개이기 때문에 백트레킹으로 가지치기를 잘 하면서 구하면 충분히 빠른시간내에 답을 구할 수 있다(비트 연산을 이용한 Brute Force는 2^36의 경우의 수를 모두 체크해야 하므로  TLE난다)

m이 100개로 제한되어 있지 않고 백트레킹이 안될 정도로 크다면 어찌풀어야 할까..??

#include <cstdlib> #include <cstdio> #include <memory> long long d[36]; int M; int bitcount(long long bit) { int res = 0; for (int i = 0; i < 36; i++) if (bit & (1LL<<i)) res++; return res; } int K; bool OK; void go(int depth, int count, long long rem) { if (OK) return; if (bitcount(rem) < K) return; if (count == K) { if (bitcount(rem) >= K) OK = true; return; } if (depth + count > 36 + K) return; go(depth + 1, count, rem); if (d[depth]) go(depth + 1, count+1, rem & d[depth]); } int main() { int T; scanf("%d", &T); while (T--) { memset(d, 0x00, sizeof(d)); scanf("%d", &M); for (int i = 0; i < M; i++) { int a, b; scanf("%d%d", &a, &b); a--;b--; d[a] |= (1LL<<b); } int ans = 1; for (int k = 2; k * k <= M; k++) { K = k; OK = false; go(0, 0, (1LL<<36)-1); if (!OK) break; ans = k; } printf("%d\n", ans); } return 0; }