# Internet Problem Solving Contest

## Solution to Problem H – Magic

We state the problem more formally: Let C be the set of all cards, i.e. C = {1,2,...,N}. Let A be the family of all subsets of C of size (N+1)/2. Similarly, let B be the family of all subsets of C of size (N-1)/2. We want to find a perfect matching between A and B such that if SA is matched to SB then SB is a subset of SA.

In other words, we can define a bipartite graph with partitions A and B. A pair (SA,SB) is an edge of the graph if and only if SB is a subset of SA. Now we want to find a perfect matching in this graph. (A perfect matching is a set of vertex-disjoint edges of size (number of vertices)/2, a maximum matching is a set of vertex-disjoint edges of maximum size.)

Finding a maximum matching in a bipartite graph can be done in time O(nm), where n is the number of vertices and m is the number of edges (see e.g. Cormen-Leiserson-Rivest: Introduction to Algorithms, page 600). In our case, n = 2 * (N choose (N+1)/2), and m = n/2 * (N+1)/2. If the size of a maximum matching is n/2, we have a perfect matching which we print as an output of our program. (Otherwise, if the size is not n/2, we should output "MAGIC". By Hall's Theorem, this never happens in our case.)