Editorial for COCI '21 Contest 2 #3 Hiperkocka

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

A single tree can be placed in the following way: root the tree in an arbitrary node, and place that node on an arbitrary node of the hypercube (say 0). Then we do a DFS on the tree, and when moving from a tree node that is placed on the hypercube node x to a new node using the i^\text{th} edge, we place it on the hypercube node x \oplus 2^i.

The rest of the trees can be placed as follows: for each x \in \{0, \dots, 2^n-1\} that has an even number of ones in binary, we take the hypercube nodes on which the first tree was placed and xor their labels with x. Notice that in such a way, we obtain 2^{n-1} trees.

A proof that the described trees make a tiling is left to the reader.


There are no comments at the moment.