Editorial for COCI '22 Contest 1 #5 Neboderi
Submitting an official solution before solving the problem yourself is a bannable offence.
The first subtask is solvable with brute force, by trying out each possible interval. There are such intervals, and by naively calculating the sum in
and the greatest common divisor in
, where
is the largest height of a skyscraper, it is possible to achieve a complexity of
which is enough to solve this subtask.
Let the function be the sum of heights of all skyscrapers inside an interval, and let
be their greatest common divisor. Notice that the beauty of an interval
is exactly
. For the solution of the second subtask, notice the following relations:
and
. By that relation, it is possible to calculate all values of the functions
and
in complexities
and
respectively. That is enough to solve the second subtask.
For the full solution, you should notice the following. For the function , the following also holds for
,
. It is enough to calculate all values of
in
and that is enough to be able to calculate the value of all
in
. Let us now fix the right border
of the interval we will look at. Notice the following holds for each
:
, or
which implies
. Now notice that the function
can achieve at most
different values for a fixed
.
Now, notice that for a fixed ,
implies
. It follows that it is enough to maintain the leftmost
which achieves each possible value of
for the current border
. Because there are at most
of them, it is possible to iterate through all of them and calculate their beauties. When switching the right border from
to
, it is enough to try and add the border
for the interval
, and check for each of the current left borders whether the inequality
still holds for
. This can be done using Euclid's algorithm. This gives us an algorithm of the complexity
which is enough for full score. Notice that there exist similar algorithms with the same complexity which have a far worse constant. Such implementations were supposed to get points on the third and fourth subtasks.
Comments