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