Editorial for COCI '20 Contest 5 #5 Sjeckanje

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 can be solved by dynamic programming. We find the largest possible value of each array prefix. When we are on some element, we try to cut the string in all possible places to the left, and maintain the current minimum and maximum. The complexity is $\mathcal O(n^2)$ $O (n^{2})$ per update.

For other subtasks, we need the following observation: It is optimal to chop the array into monotonous (ascending or descending) segments. If the segment is not monotonous, we can always cut it into two parts that will have higher total value.

The value of a monotonous segment $[a_l, a_{l+1}, \dots, a_r]$ $[a_{l}, a_{l + 1}, \dots, a_{r}]$ equals $|a_l-a_{l+1}| + |a_{l+1}-a_{l+2}| + \dots + |a_{r-1}-a_r|$ $| a_{l} - a_{l + 1} | + | a_{l + 1} - a_{l + 2} | + \dots + | a_{r - 1} - a_{r} |$ .

Let $d_i := |a_i-a_{i+1}|$ $d_{i} := | a_{i} - a_{i + 1} |$ . The value of the whole array is the sum $\sum |d_i|$ $\sum | d_{i} |$ , minus those $|d_i|$ $| d_{i} |$ in the places where we cut. That is, if we cut the string in place between $i$ $i$ and $i+1$ $i + 1$ , we won't include $|d_i|$ $| d_{i} |$ in the answer.

We have reduced the problem to the following: we are given an array of integers $(d_i)$ $(d_{i})$ , and we need to choose some of them so that the sum of their absolute values is maximal, without taking two adjacent numbers, one of which is strictly positive and the other strictly negative. (The last condition is because the segments of the initial sequence must be monotonic).

For the second subtask, we can recompute the maximum possible value after each update by simple dynamic programming in complexity $\mathcal O(n)$ $O (n)$ : for each prefix we calculate the maximum possible value in two cases depending on whether or not we took the last element. Hence the total complexity is $\mathcal O(qn)$ $O (q n)$ .

We can solve the full problem using a segment tree. Each node remembers the maximum value of its segment, for each of the four cases of (not) taking the first and the last element. While merging, we have to pay attention to the signs of the elements on the border to be joined. Note that when an update occurs, at most two $d_i$ $d_{i}$ 's (those at positions $l-1$ $l - 1$ and $r$ $r$ ) will change, so the segment tree easily handles this easily. The total complexity is $\mathcal O(n + q \log n)$ $O (n + q \log n)$ .

Comments

There are no comments at the moment.