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 a \mid b and a < b, then a \le 2b.

Let \operatorname{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 \left\lfloor \frac{\operatorname{greatest\_bit}(a)}{4} \right\rfloor = \left\lfloor \frac{\operatorname{greatest\_bit}(b)}{4} \right\rfloor.

All other edges we give to frog 2 if \left\lfloor \frac{\operatorname{greatest\_bit}(a)}{16} \right\rfloor = \left\lfloor \frac{\operatorname{greatest\_bit}(b)}{16} \right\rfloor, and the remaining ones we give to frog 3.

Using \operatorname{greatest\_bit}(x) < 64, we can prove this construction works.


Comments

There are no comments at the moment.