Editorial for COCI '10 Contest 5 #5 Dvoniz

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.

Let us freeze the middle of an interesting sequence in all possible ways. It can easily be noticed that if there exists a sequence of length 2N, there also exists a sequence of length 2M < 2N with the same middle value for each integer M less than N. This suggests a binary search approach to be used to find the longest interesting sequence for every position of the middle element, which yields an algorithm with \mathcal O(N \log N) time complexity.

For each element, we first search for the longest sequence which starts with that element. To solve that problem, we process elements from right to left. Among all interesting sequences [a_i, b_i] which start before the position of the current element we are processing we search for the one for which the value (b_i-a_i+1)-2(X-a_i) = b_i+a_i+1-2X is maximal. The value of a_i can be found as follows: as we process the elements, we keep track of the maximum and we try to improve that maximum by considering interesting sequences which start at the current position.

When we move to the right, we decrease that maximum by 2 (since a move X := X+1 decreases this value by 2).

The above algorithm can easily be implemented with \mathcal O(N \log N) time complexity, which solves the problem.


There are no comments at the moment.