Convex Array#11812

Convex Array (Editorial)

Problem Author:	Anton Trygub
Problem Prepared by:	Vasyl Merenych
Editorial Written by:	Kostiantyn Denysiov

Claim 1. A convex array has non-decreasing differences between adjacent elements. That is, if we denote $d_{i} = b_{i + 1} - b_{i}$ d_i = b_{i+1} - b_i, then for each $i$ the inequality $d_{i} \leq d_{i + 1}$ d_i \le d_{i+1} holds.

This follows directly from the definition of convexity.

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

It is then necessary to split the array into two increasing convex sequences that intersect at the smallest element of the array.

Logically, these sequences should be constructed by adding elements in ascending order. But how to determine to which of them to add a new element?

For this, it is enough to keep two last elements of each sequence. This will allow checking the conditions of convexity and correctly distributing the new elements.

Then we can write a dynamic programming solution $d p [i] [a] [b] [c]$ dp[i][a][b][c] ( $i > a$ i > a, $i > b > c$ i > b > c), which will take values true or false and denote whether we can split the first $i$ numbers into two sequences. The first sequence ends at elements with indices $i, a$ , and the second — at $b, c$ . Then we have a solution with complexity $O (n^{4})$ \mathcal{O}(n^4).

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

Additionally, instead of binary values true and false for the tuple $i, a, b$ i, a, b, we can store the largest possible value $c$ , since it is beneficial to minimize the difference between $b$ and $c$ . Thus, we have a solution with complexity $O (n^{2})$ \mathcal{O}(n^2).

To optimize the solution further, it's necessary to delve deeper into the characteristics of the states. In particular, we have already considered that index $i - 1$ i-1 is important in the states. Now, let's also consider index $i - 2$ i-2.

There are three cases for states $i, a, b, c$ i, a, b, c:

$i, i - 1, b, c$ i, i - 1, b, c;
$i, i - 2, i - 1, c$ i, i - 2, i - 1, c;
$i, c, i - 1, i - 2$ i, c, i - 1, i - 2;

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

Let's consider the transitions for a fixed $i$ . We have at most one state of the second and third types. States of the first type can be numerous, so let's consider them separately to optimize the transitions from these states.

Consider the state $i, i - 1, b, c$ i, i-1, b, c. Let's consider two cases depending on which sequence we place the element $i + 1$ i+1:

We add it to the first subsequence. Then the condition must hold: $a_{i + 1} + a_{i - 1} \geq 2 \cdot a_{i}$ a_{i+1} + a_{i-1} \geq 2 \cdot a_i. And we transition to the state: $i + 1, i, c, d$ i + 1, i, c, d. Notice that in this state the transition occurs regardless of the values of $c, d$ , and the transition occurs from the first type to the first type.
That is, if for a fixed $i$ we keep all possible states as a set of pairs $(c, d)$ , then when transitioning to the next state $i + 1$ i+1 all these states will remain unchanged, if the condition $a_{i + 1} + a_{i - 1} \geq 2 \cdot a_{i}$ a_{i+1} + a_{i-1} \geq 2 \cdot a_i holds.
We add it to the second subsequence. Then the condition must hold: $d + a_{i + 1} \geq 2 \cdot c$ d + a_{i+1} \geq 2 \cdot c, which is equivalent to $a_{i + 1} \geq 2 \cdot c - d$ a_{i+1} \geq 2 \cdot c - d. And we transition to the state: $i + 1, c, i, i - 1$ i+1, c, i, i-1, that is, to the third type state.
For states of the third type, it is necessary to maximize $c$ , so it is necessary to find the maximum $c$ among all the states that satisfy the condition $a_{i + 1} \geq 2 \cdot c - d$ a_{i+1} \geq 2 \cdot c - d.

There is no need to optimize transitions from the states of the second and third types, because there is at most one of them.

Now it remains to optimize transitions from the first type to the third. To do this, you can sort the states $(c, d)$ by the value $2 \cdot c - d$ 2 \cdot c - d. After that, for each new element $a_{i + 1}$ a_{i+1} it is necessary to find the maximum value of $c$ among those states where $2 \cdot c - d \leq a_{i + 1}$ 2 \cdot c - d \le a_{i+1}.

To effectively find this maximum, there is no need to use complex data structures like a segment tree or Fenwick tree. It is enough to use std::set, if you notice that states for which there exists another state with a smaller $2 \cdot c - d$ 2 \cdot c - d and simultaneously a larger $c$ do not need to be saved.

Thus, if unbeneficial states are filtered out, the resulting states will be sorted both by $2 \cdot c - d$ 2 \cdot c - d and by $c$ . Then to find the maximum on the prefix it is enough to use one call to lower_bound.

Final solution complexity: $O (n lo g n)$ \mathcal{O}(n \log{n}).