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