Editorial for COCI '17 Contest 2 #3 Doktor
Submitting an official solution before solving the problem yourself is a bannable offence.
Let the value of the contiguous subsequence (from now on, just subsequence) be equal to the difference between the number of fixed points created by rotating that subsequence and the number of fixed points that disappear by rotating that subsequence. It is clear that we want to choose the subsequence of the maximal possible value.
We can see that a card with the number
Using the observations above, we can try to design a solution: for each possible center of the subsequence, iterate over all subsequences with that center from the smallest to the largest member. We will always spread by exactly
In order to improve the previous solution, we will take advantage of the fact that we are searching for a subsequence with the maximal value, and not the values of all subsequences. In fact, the value of the subsequence when we iterate over all subsequences with the same center in the previous solution only increases at positions where a new fixed point is created. Therefore, it is sufficient to observe, for each center, only the subsequences with card
The previous passage motivates the following solution: for each card, determine the center that can make it a fixed point, and store it in a list of cards for that center. Then, for each center, we sort the associated list by the distance between the card and the center, and iterate over the list and increase the number of newly created fixed points by
In order to calculate the value of each of the given subsequences, we also need to find out the number of fixed points that disappear by reversing a subsequence. We can do this in constant complexity if we previously calculate the number of fixed points in all prefixes of the sequence of cards. The asymptotic complexity of the solution by parts is
Additionally, it is not too difficult to solve the task in
Comments