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.
        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 ). Then we do a DFS on the tree, and when moving from a tree node that is placed on the hypercube node 
 to a new node using the 
 edge, we place it on the hypercube node 
.
The rest of the trees can be placed as follows: for each  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 
. Notice that in such a way, we obtain 
 trees.
A proof that the described trees make a tiling is left to the reader.
Comments