## IPSC 2001

## 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 **S**_{A}
is matched to **S**_{B} then **S**_{B} is a subset of **S**_{A}.

In other words, we can define a bipartite graph with partitions *A* and *B*. A pair
**(S**_{A},S_{B}) is an edge of the graph if and only if
**S**_{B} is a subset of **S**_{A}. 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.)