Internet Problem Solving Contest

IPSC 2018

Solution to Problem F – Farmer's code

In the easy subtask the population is very small, so you should have been able to find it using a sufficiently exhaustive search (and possibly even with some random clicking).

One possible solution: Crossing the first and the second tree gives us a tree with the correct shape, but with the fruits in incorrect branches. The same goes for third and fourth three. Combining those two symmetrical trees yields the requested tree.

In the hard subtask, things are much more involved. Given the query limit, it seems unlikely that we will be able to win by accident, so we need to deduce the representation of the genetic code, the way how the crossover works and how is the genotype mapped to phenotype. In the following text, will denote the crossover operation.

We soon realise that the crossover is deterministic, i.e. A ⊕ B always yields the same tree. Furthemore, the operation is commutative, i.e., the order of the trees doesn’t matter. Additionally, the operation is associative – we can easily verify that A ⊕ (B ⊕ C)=(A ⊕ B)⊕C.

What happens if we do A ⊕ A? (We have to select two distinct trees to cross, but we can always create two copies of the same tree and then combine those if we want to experiment.) For each A we will get the same result: let’s call it tree X. It is then easy to verify that X has another interesting property: we have A ⊕ X = A for all A.

Observe that we have just verified all axioms of a commutative group and hence we have established that the crossover is a group operation. The order of the group is 2. What groups of order do we know? Perhaps we are dealing with 2k with being xor?

How many different trees are there in the first place? If we count correctly, each tree has six different fruits, one trunk and one node without any fruit. The tree is rooted, but always at the trunk. By Cayley’s formula we know that there are exactly nn − 2 distinct labelled trees on n vertices. In this problem, this would suggest that there are 218 of them. Could it be just a coincidence that we have exactly 18 trees to play with? They would make a great basis of our group!

How does one prove Cayley’s formula? One famous approach is using so called Prufer codes, where each code is a (n − 2)-tuple of vertex labels. The proof gives a bijection to labelled trees. If we label our vertices from 0 to 7, those Prufer codes become closed on element-wise xor operation!

How to find the labels? Easily: simply try all different permutations of labels and check whether they are consistent with the crossover operations we observe. Given this information, how do we construct the tree we want? This is also simple – we can either use Gaussian elimination or simply try all possible subsets of the input to see which one yields the target tree. There is only one such subset, as the starting trees are indeed linearly independent. The 1-based indices of the trees for the solution are (1, 2, 5, 6, 8, 9, 13, 14, 16).