## IPSC 2008

## Solution to Problem D – Discover All Sets

The straightforward solution of this problem is to try all possible sets of M cards and check whether they
form a Set. This solution is very slow and thus we will not go into details.

A slightly better solution is to try all possible sets of M - 1 cards. For each such a set S, it is clear
whether cards in S can form a Set. If so, we can calculate the missing value of each property and
thus compute the missing card that will create a Set. Note that such card is uniquely determined.
It is enough to check whether it is among the K given cards, and for this, we can use a set or a
hashmap.

Note that this solution counts each set M times, once for each missing card.

Both solutions can be improved by cutting the branches of the program in early stages when it is clear that
the branch does not lead to a Set. This approach performs reasonably well on many inputs, but its
performance is not guaranteed – and its time complexity is always at least linear in the number of
Sets.

The sample solution of this problem uses this improvement, and the idea of the meet-in-the-middle approach
for M ≥ 4.

We can hash a set of cards to a NM-bit sequence of ones and zeroes that describes for each of the N
properties which of the M values are represented in the set.

How can this help us? Suppose that we have two sets of cards C and D, with |C|,|D|≥ 2 and |C| + |D| = M.
Do C and D form a Set together? The answer to this question is uniquely determined by their
hashes.

For each set C of X = ⌊M∕2⌋ cards that can form a Set we will determine its hash, and construct a hash
table where we count the number of times each hash occured.

After the hash table is constructed we take all possible sets of cards of size Y = ⌈M∕2⌉ that can form a Set.
For each such set D: From the hash of D we can determine the hash of its matching set C. (The properties that
are constant in D must be constant in C as well, with the same value. For the other properties we take
the complement of the set of values.) From our hash table we know how many such sets C there
are.

As in the previous solution, the resulting number of Sets need to be divided by the number of times we
counted each set, which is the number of ways how to choose ⌈M∕2⌉ cards out of M.

(The solution can be made even faster by counting each Set only once. Can you see how to do
it?)