Editorial for COCI '21 Contest 5 #4 Radio
Submitting an official solution before solving the problem yourself is a bannable offence.
For each broadcasting radio frequency , we can keep track of two other radio frequencies
and
, the next smallest and the next largest broadcasting frequency which makes noise with
(if
doesn't exist, we take it to be
, and if
doesn't exist, we take it to be
). The interval
creates noise if
or
. The minimum and maximum in the interval can be determined in
using a segment tree. What remains is to figure out a way to keep track of
and
.
Notice that two frequencies create noise if and only if they are both divisible by some prime number. If in the sieve of Eratosthenes, we store for each number one of its prime factors, then we can factor a number in by going over each of its prime factors. For each prime, we can maintain a set of broadcasting frequencies divisible by this prime. Then for each frequency, there are at most
candidates for
and
.
These observations are sufficient to obtain a solution. When a frequency becomes active, for each prime factor of
, we look at the set of broadcasting frequencies for that prime and we find the next smallest and next largest frequency in this set. The minimum of the larger frequencies will be
, and the maximum of the smaller frequencies will be
. Additionally, for each of the
and
candidates, their
and
values might change, so we must update them. The number of candidates is
, and updating
or
takes
. Therefore, we can keep track of the updates in
. When deactivating a frequency, we do the opposite. We erase the number
from all the sets it is in, and adjust
and
of its neighbours. Again, the number of neighbours is
.
It should be noted that the time complexity is in practice even better because numbers less than can have at most
distinct prime factors since
.
Comments