Editorial for COCI '22 Contest 1 #5 Neboderi


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.

The first subtask is solvable with brute force, by trying out each possible interval. There are \mathcal O(n^2) such intervals, and by naively calculating the sum in \mathcal O(n) and the greatest common divisor in \mathcal O(n \ln MAX), where MAX is the largest height of a skyscraper, it is possible to achieve a complexity of \mathcal O(n^3 \ln MAX) which is enough to solve this subtask.

Let the function S(l, r) := h_l+h_{l+1}+\dots+h_r be the sum of heights of all skyscrapers inside an interval, and let \gcd(l, r) := G(h_l, h_{l+1}, \dots, h_r) be their greatest common divisor. Notice that the beauty of an interval [l, r] is exactly S(l, r) \cdot G(l, r). For the solution of the second subtask, notice the following relations: S(l, r) = S(l, r-1)+h_r and G(l, r) = \gcd(G(l, r-1), h_r). By that relation, it is possible to calculate all values of the functions S and G in complexities \mathcal O(n^2) and \mathcal O(n^2 \ln MAX) respectively. That is enough to solve the second subtask.

For the full solution, you should notice the following. For the function S, the following also holds for l > 1, S(l, r) = S(r, 1)-S(l-1, 1). It is enough to calculate all values of S(1, r) in \mathcal O(n) and that is enough to be able to calculate the value of all S(l, r) in \mathcal O(1). Let us now fix the right border r of the interval we will look at. Notice the following holds for each l < r: G(l, r) = G(l+1, r), or G(l, r) \mid G(l+1, r) which implies 2G(l, r) \le G(l+1, r). Now notice that the function G(l, r) can achieve at most \log MAX different values for a fixed r.

Now, notice that for a fixed l, G(l, r) = G(l+1, r) implies G(l, r+1) = G(l+1, r+1). It follows that it is enough to maintain the leftmost l which achieves each possible value of G for the current border r. Because there are at most \mathcal O(\log MAX) of them, it is possible to iterate through all of them and calculate their beauties. When switching the right border from r to r+1, it is enough to try and add the border r+1 for the interval [r+1, r+1], and check for each of the current left borders whether the inequality G(l, r) > G(l-1, r) still holds for G(l, r+1) > G(l-1, r+1). This can be done using Euclid's algorithm. This gives us an algorithm of the complexity \mathcal O(n \log MAX \ln MAX) 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

There are no comments at the moment.