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

Let $\operatorname{greatest\_bit}(x)$ ~\operatorname{greatest\_bit}(x)~ equal the position of the leading bit in the binary representation of $x$ ~x~.

We give the edge between $a$ ~a~ and $b$ ~b~ to frog $1$ ~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$ ~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$ ~3~.

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

Comments

There are no comments at the moment.