## IPSC 2007

## Solution to Problem C – Calling Me Calling You

As you have probably noticed, the problem can be described in the language
of graphs. Vertices of the graph are friends, the edges correspond to the
"can choose as the Happy number" relation. Our goal is to pick some of the
edges so that the resulting graph is connected, while trying to minimize a
quantity **H** related to the distribution of the edges with respect to
the vertices (**H** is the number of Happy Packs). Obviously, as long as
the marked edges form a cycle, we can remove at least one of them and
**H** will remain the same or even decrease. Thus, without loss of
generality, we can search for an optimal solution in which the chosen edges
form a spanning tree.

Every spanning tree has the same number of edges, **(N-1)**, so there
is an obvious lower bound on the value of **H**: **H** ≥
**ceil((N-1)/K)**, where **ceil(X)** denotes the least integer greater
or equal to **X**.

The case **K=1** is the simplest one, as the lower bound can be attained
trivially by choosing any spanning tree in the graph. This can be done by
performing a depth-first search on the tree, for example.

The case **K=2** is only slightly more complicated. Again, the lower
bound can be attained by choosing any spanning tree and partitioning it into
a set of edge-pairs (and, in the case of **N** even, one unpaired edge).
This partitioning can be performed recursively and fits well into the
depth-first search for the spanning tree.

The algorithm partitions the edges of a tree **T** with root **v** and
a "dangling edge" **e** which connects it to the rest of the whole
spanning tree. If the number of the edges in tree **T** was odd,
the dangling edge will be used in the pairing as well, otherwise it'll
be left untouched.

At the beginning, the algorithm processes all the subtrees of tree **T**.
The subtrees with odd number of edges get partitioned completely, using up
their respective dangling edges. The dangling edges of the other subtrees
are free so far, so we can pair them up arbitrarily. If there was an odd
number of them, we pair the dangling edge **e** of tree **T** to one
of them. Once we process the whole graph, we'll have partitioning of all
the edges of the spanning tree.

The only remaining case present in the hard input was **K=3**. This case
is the most difficult one and we are not aware of any solution better than
an exhaustive search (in fact, a generalization of this problem is provably
NP-complete). Due to the size of such test cases, solving them by hand was
most likely a simpler option.