Please subscribe to the official Codeforces channel in Telegram via the link ×

Dewi's blog

By Dewi, history, 2 months ago, In English


here is the problem :

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 :

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!

  • Vote: I like it
  • +11
  • Vote: I do not like it

2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Dewi (previous revision, new revision, compare).