Simple Observations

The definition of the reduce operation in the problem statement could be rephrased in the following way. We have ~n~ points on a line (corresponding to the elements of the sequence), so there are ~n-1~ line segments connecting pairs of adjacent points. In the beginning, all ~n-1~ line segments are erased, so each point forms a single set. A single reduction is equivalent to drawing back one of these line segments, what results in joining the sets that contain the points corresponding to the ends of this line segment; the cost of this operation is equal to the maximal element of the resulting set. This interpretation of the reduce operation will simplify some of the following solutions' descriptions (as in this version the sequence never becomes shorter).

~\mathcal O(n^3)~ Dynamic Programming Solution

A segment of a sequence is its contiguous subsequence, i.e. ~a_l, a_{l+1}, \dots, a_r~. In the simplest solution for each segment of the sequence we count the minimal cost of reducing it into a single element (let us denote this value by ~tab[l, r]~ for the segment ~a_l, \dots, a_r~). Obviously, for every ~i \in \{1, \dots, n\}~ we have ~tab[i, i] = 0~. If ~l < r~ then the last operation in the process of reducing this segment to a single element always costs ~M = \max(a_l, \dots, a_r)~; in our solution, we can only choose the position of this reduction, which is in other words the position of the line segment drawn during this reduction. That is why for ~l < r~ formula ~tab[l, r] = \min(tab[l, i] + tab[i+1, r] + M : l \le i < r)~ holds. Using this formula we can compute all values of array ~tab~ from the shortest to the longest segments. The total time complexity of this solution is ~\mathcal O(n^3)~, because there are ~n^2~ fields of array ~tab~ and computing each of them requires ~\mathcal O(n)~ time. This solution scores ~30~ points out of ~100~.

A Greedy Observation

To achieve a better time complexity of our solution we need to introduce some greediness. Let us assume for simplicity that ~a_0 = a_{n+1} = \infty~. We claim that performing ~n-1~ repetitions of the following step:

find ~i~ such that ~a_{i-1} \ge a_i \le a_{i+1}~

if (~a_{i-1} < a_{i+1}~) then reduce(~i-1~) else reduce(~i~)

gives us an optimal reduction scheme for our sequence.

Proof

Firstly we need to prove that in each of the ~n-1~ steps finding a required value of ~i~ is possible. In each step let us start with ~j = 1~ and while the condition ~a_{j-1} > a_j~ holds let us increase the value of ~j~ by one. This process will certainly terminate because ~a_n < a_{n+1} = \infty~ (since ~n \ge 1~). The value of ~i = j-1~ in the moment of termination is an example of an index that we were looking for.

Now let us find out why this reduction scheme is optimal. We will prove this by induction on the value of ~n~. If ~n = 1~ then this solution is obviously optimal with cost ~0~. If ~n > 1~ then we need to prove that there exists an optimal reduction scheme of our sequence in which the reduction determined by our greedy step is done in the beginning. Let us assume that ~a_{i-1} < a_{i+1}~ (the other case is analogical). Let ~S~ be any optimal reduction scheme of our sequence in which the reduction between ~a_{i-1}~ and ~a_i~ is not the first reduction (if no such scheme exists, then we are done). Let us consider two reductions: the one defined by the line segment between ~a_{i-1}~ and ~a_i~ (we will call it ~r_1~) and the one between ~a_i~ and ~a_{i+1}~ (called ~r_2~). If none of the reductions ~r_1~ and ~r_2~ is first in ~S~ then we can move the first of them that appears in ~S~ (let ~r_i~ be this reduction) to the beginning of ~S~. After performing this operation, the cost of ~S~ does not increase. Why? Firstly, the cost of ~r_i~ can only decrease or stay the same (the sooner a reduction is performed, the lower is its cost). Secondly, performing this reduction earlier will not change the cost of any reductions performed in ~S~ before the second of reductions ~r_1~ and ~r_2~, because inserting ~a_i~ to a set containing either ~a_{i-1}~ or ~a_{i+1}~ does not change the maximal element of this set and only reductions involving this set could change their costs. On the other hand, after both ~r_1~ and ~r_2~ were performed, the costs of all following reductions will not change (all three elements ~a_{i-1}~, ~a_i~ and ~a_{i+1}~ will be in a single set since then).

If ~r_i~ = ~r_1~ then we are done now. In the opposite case, we will prove that swapping ~r_2~ (which is now in the beginning of ~S~) and ~r_1~ decreases the cost of ~S~ (what will give a contradiction with optimality of ~S~). Let us notice that after this swap the cost of all reductions apart from ~r_1~ and ~r_2~ in ~S~ is exactly the same as in the beginning (the argument is similar to the one from the previous fragment of the proof). The second of those reductions in both cases (before and after the swap) costs exactly the same, as its resulting set is the same. So the change of cost of ~S~ is ~cost(r_1)-cost(r_2) = a_{i-1}-a_{i+1} < 0~, what gives us the desired contradiction.

Implementations of the Greedy Method

A straightforward implementation of the greedy approach (performing simply one step after another on a sequence represented as an array of integers) leads to an ~\mathcal O(n^2)~ solution. This solution scores ~50~ points out of ~100~.

An implementation of this algorithm with complexity ~\mathcal O(n)~ can be obtained. In this solution, the sequence will be analyzed from ~a_0~ to ~a_{n+1}~. Throughout the algorithm, a stack containing a decreasing subsequence of ~a~ is maintained. In the beginning, the stack contains only values ~a_0~ and ~a_1~. In each of the following steps (for ~i = 2, 3, \dots, n+1~), if ~a_i~ is smaller than the element on the top of the stack, then ~a_i~ is simply pushed on the stack, and in the opposite case, all possible reductions are made. In other words, if the element from the top of the stack is not greater than ~a_i~, then this element is reduced with smaller of the elements: ~a_i~ and the element second from the top of the stack. This operation pops the element from the top of the stack and the process continues. This loop stops at one of the conditions:

• if ~i = n+1~ and the stack contains only two elements, one of which must be ~a_0 = \infty~ — this terminates the algorithm, the sequence was reduced to a single element,

• if ~a_i~ is smaller than the element on the top of the stack (in this case ~a_i~ is pushed on the stack) — this terminates the loop in the case ~i < n+1~; there will surely be such a moment in the loop for every ~i < n+1~, because ~a_0 > a_i~.

Even though a single step of the algorithm (for a given ~i~) may take ~\mathcal O(n)~ operations, the whole algorithm has complexity ~\mathcal O(n)~. This is true because the number of iterations of the inner loop of the algorithm is bounded by the total number of elements that are pushed on the stack, and the latter is ~\mathcal O(n)~ because in every step only one element is pushed on the stack.