Statement↵
------------------↵
↵
here is the problem : https://oj.uz/problem/view/COCI21_hiperkocka↵
↵
Abridged Statement : you are given a tree T with n edges , you want to find a tiling using T on the hipercube Q_n.A hipercube with Q_i is defined as a tree such that node x and node y have an edge if and only if bitwise xor of them is a power of 2.↵
↵
(please see the problem if you couldnt understood the abridged statement)↵
↵
Editorial & Issue↵
------------------↵
↵
editorial : https://hsin.hr/coci/archive/2021_2022/contest2_solutions.zip↵
↵
As you can see in the editorial , it gives a construction which appearantly works but it doesnt provide a proof :/↵
I couldnt make sense on spesifically this paragraph : ↵
↵
↵
↵
_"The rest of the trees can be placed as follows: for each x ∈ {0, . . . , 2n − 1} that has an even number of↵
ones in binary, we take the hipercube nodes on which the first tree was placed and xor their labels with x.↵
Notice that in such a way we obtain 2n−1 trees."_↵
↵
↵
Any help and insight provided for the problem is welcomed!↵
↵
------------------↵
↵
here is the problem : https://oj.uz/problem/view/COCI21_hiperkocka↵
↵
Abridged Statement : you are given a tree T with n edges , you want to find a tiling using T on the hipercube Q_n.A hipercube with Q_i is defined as a tree such that node x and node y have an edge if and only if bitwise xor of them is a power of 2.↵
↵
(please see the problem if you couldnt understood the abridged statement)↵
↵
Editorial & Issue↵
------------------↵
↵
editorial : https://hsin.hr/coci/archive/2021_2022/contest2_solutions.zip↵
↵
As you can see in the editorial , it gives a construction which appearantly works but it doesnt provide a proof :/↵
I couldnt make sense on spesifically this paragraph : ↵
↵
↵
↵
_"The rest of the trees can be placed as follows: for each x ∈ {0, . . . , 2n − 1} that has an even number of↵
ones in binary, we take the hipercube nodes on which the first tree was placed and xor their labels with x.↵
Notice that in such a way we obtain 2n−1 trees."_↵
↵
↵
Any help and insight provided for the problem is welcomed!↵
↵
