Editorial for COCI '20 Contest 4 #3 Hop


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.

There are several solutions; we describe the shortest one. The idea is: if ab and a<b, then a2b.

Let greatest_bit(x) equal the position of the leading bit in the binary representation of x.

We give the edge between a and b to frog 1 if greatest_bit(a)4=greatest_bit(b)4.

All other edges we give to frog 2 if greatest_bit(a)16=greatest_bit(b)16, and the remaining ones we give to frog 3.

Using greatest_bit(x)<64, we can prove this construction works.


Comments

There are no comments at the moment.