ACM-ICPC Problem for April 4th

Here is a link to this week’s problem.

The basic idea of the problem, ignoring the silly acronyms, is to determine the number of distinct grids that can be formed from two types of vertices. One type of vertex (a “hive”) must be linked to any 4 other elements, while the other type (“couches”) must be linked only to a single hive. (These sound suspiciously similar to carbon and hydrogen atoms, respectively.) One important restriction is that no cycles can exist between graph elements; for example, it is forbidden for A to link to B, B to link to C, and C to link back to A. The input given is a number N, and the goal is to determine the number of possible distinct configurations including N hives.

A first approach to this problem might be to focus on the hives rather than couches, since the couches have only one connection and so their placement is determined uniquely by the placement of the hives. A simple brute-force solution would involve recursively enumerating the possible orientations, reducing the Nth case to the (N-1)th case, although this will probably be too slow. Dynamic programming might be useful.