Convex Array#393

Convex Array (Editorial)

Problem Author:

Anton Trygub

Prepared by:

Vasyl Merenych

Analysis written by:

Kostiantyn Denysov

Statement 1. In a convex array, the differences between adjacent elements do not decrease. That is, if we denote d_i = b_{i+1} - b_i, then for each the inequality d_i \le d_{i+1} holds.

This directly follows from the definition of convexity.

Since the sequence of differences d_i = b_{i+1} - b_i is non-decreasing, there exists an index such that d_i \le 0 for i < k and d_i \geq 0 for i \geq k. This means that the array can be divided into two monotonic convex sequences: a decreasing one b_1, \dots, b_k and an increasing one b_k, \dots, b_n.

Then we need to split the array into two increasing convex sequences that intersect at the smallest element of the array.

It is logical to build these sequences by adding elements in increasing order. But how to determine which of them to join the new element?

For this, it is sufficient to keep the last two elements of each sequence. This will allow us to check the convexity conditions and correctly distribute new elements.

Then we can write a dynamic programming state dp[i][a][b][c] (i > a, i > b > c), which will take values true or false and indicate whether we can divide the first numbers into two sequences. The first sequence ends at the elements with indices , and the second one at . Thus, we have a solution in \mathcal{O}(n^4).

Note that in reachable states, exactly one of a, b, c will be equal to i-1. Therefore, we can actually optimize the previous dynamic programming to \mathcal{O}(n^3).

Moreover, instead of binary values true and false for the triplet i, a, b, we can store the maximum possible value of , since it is advantageous to minimize the difference between and . Thus, we will have a solution in \mathcal{O}(n^2).

To further optimize the solution, we need to delve deeper into the specifics of the states. In particular, we have already considered that the index i-1 is important in the states. Now we will also consider the index i-2.

There are three cases of states i, a, b, c:

  1. i, i - 1, b, c;

  2. i, i - 2, i - 1, c;

  3. i, c, i - 1, i - 2;

For the second and third cases, it is sufficient to keep only the maximum possible reachable values of for a fixed . Similarly, we have for the first case for a fixed and , but here there are more parameters, so this case is more complex.

Let's consider transitions for a fixed . There can be at most one state of the second and third types. There can be many states of the first type, so we will consider them separately to optimize transitions from these states.

We consider the state i, i-1, b, c. We will consider two cases depending on which sequence we place the element i+1:

  1. Adding to the first subsequence. Then the condition must hold: a_{i+1} + a_{i-1} \geq 2 \cdot a_i. We transition to the state: i + 1, i, c, d. Note that in this state the transition occurs independently of the values of , and the transition goes from a first-type state to a first-type state.

    That is, if for a fixed we keep all possible states as a set of pairs , then when transitioning to the next state i+1, all these states will remain in the same form if the condition a_{i+1} + a_{i-1} \geq 2 \cdot a_i holds.

  2. Adding to the second subsequence. Then the condition must hold: d + a_{i+1} \geq 2 \cdot c, which is equivalent to a_{i+1} \geq 2 \cdot c - d. We transition to the state: i+1, c, i, i-1, that is, to a third-type state.

    For third-type states, we need to maximize , so it is necessary to find the maximum among all states that satisfy the condition a_{i+1} \geq 2 \cdot c - d.

Transitions from second and third-type states do not need optimization, as there is at most one.

Now we need to optimize transitions from first-type states to third-type states. For this, we can sort the states by the value of 2 \cdot c - d. After that, for each new element a_{i+1}, we need to find the maximum value of among those states where 2 \cdot c - d \le a_{i+1}.

To efficiently find this maximum, there is no need to use complex data structures such as segment trees or Fenwick trees. A simple std::set will suffice if we notice that states for which there is another state with a smaller 2 \cdot c - d and at the same time a larger do not need to be stored.

Thus, if we filter out unprofitable states, the resulting states will be sorted both by 2 \cdot c - d and by . Then to find the maximum on the prefix, a single call to lower_bound will be sufficient.

Final complexity of the solution: \mathcal{O}(n \log{n}).