Transforming an array into one with descending order

Question

Problem Description

Given an array $A$ of $n$ integers, find the minimum number of operations to turn it into a new array $\widehat{A}$ with a (weakly) descending order: we require that $\hat{a}_i \geq \hat{a}_j$ for all $1\leq i<j\leq n$. Here an operation means either increasing or decreasing an element by $1$.

For example, it requires at least $4$ operations to turn the array $[1,2,3,4]$ into descending order. One solution is increasing the first element by $2$, increasing the second element by $1$, and decreasing the last element by $1$ (then the new array is $[3,3,3,3]$, which is in decending order).

My questions:

• Is the problem NP-hard?

• If not, what algorithm solves this problem with the best time complexity?

My efforts

We can write this problem as an integer linear programming. Say the elements in the array are $a_1,a_2,\ldots,a_n$, and those in the new array are $\hat{a}_1,\ldots,\hat{a}_n$ then the problem is essentially an interger programming:

$$ \begin{align*} \text{minimize}\quad &\left|\hat{a}_1-a_1\right|+\cdots+\left|\hat{a}_n-a_n\right| \\ \text{subject to}\quad &\hat{a}_1\ge\cdots\ge\hat{a}_n \end{align*} $$

or equivalentlly

$$ \begin{align*} \text{minimize}\quad &t_1+\cdots+t_n \\ \text{subject to}\quad &\hat{a}_i-a_i\le t_i, &i=1,\ldots,n\\ &-\left(\hat{a}_i-a_i\right)\le t_i, &i=1,\ldots,n\\ &\hat{a}_1\ge\cdots\ge\hat{a}_n \end{align*} $$

But it seems not to help because the coefficient matrix is not totally unimodular, thus we cannot relax it to linear programming.

I also find a property of optimum solutions:

If some consecutive elements are originally in non-descending order, then they must be the same in an optimum solution.

I don't know whether this property helps.

Answer 1

The LP you gave always admits a integral optimal solution.

Suppose there is a fractional optimal solution $\hat{a}_1,\ldots,\hat{a}_n$. For every $i$, fix the other elements $\hat{a}_j$ with $j\neq i$ and consider the optimization on $\hat{a}_i$, that is, minimizing $|\hat{a}_i-a_i|$ subject to $\hat{a}_{i-1}\geq\hat{a}_i\geq\hat{a}_{i+1}$. It's easy to see that the optimal $\hat{a}_i$ is either $a_i$ itself, or equal to one of its neighbors $\hat{a}_{i-1}$ or $\hat{a}_{i+1}$.

This observation could be generalized. Suppose in an optimal solution we have $$\hat{a}_i=\hat{a}_{i+1}=\cdots=\hat{a}_j=\lambda.$$ Now we fix $\hat{a}_1,\ldots,\hat{a}_{i-1},\hat{a}_{j+1},\ldots,\hat{a}_n$, and consider the optimization on $\lambda$. This is the simplest facility location problem, with the (convex and unimodal) objective $\sum_{k=i}^j|\lambda-a_k|$ subject to $\hat{a}_{i-1}\geq\lambda\geq\hat{a}_{j+1}$. It is optimized when $\lambda$ equals $\hat{a}_{i-1}$ or $\hat{a}_{j+1}$, or $\lambda$ coincides with some of the $a_k$'s (actually the median of $a_i,a_{i+1},\ldots,a_j$).

Upon the above observations, we could conclude that in a general problem where we want to minimize the $L_1$ distance from a real number sequence $\langle a_i\rangle$ to descending sequences:

There is always a optimal solution such that each $\hat{a}_i$ coincide with some $a_k$.

To be formal, this conclusion could be deduced from examining the potential function $\Phi(\langle\hat{a}_i\rangle)=|\{\hat{a}_i\}\setminus\{a_i\}|$.

Therefore, you can solve the linear program which gives directly the minimum number of operations. An alternative polynomial-time algorithm by the dynamic programming you suggested, but first sort $A=\{a_i\}$ and compute $$C_i(v)=\min\{C_i(v'),|a_i-v|+C_{i+1}(v)\}$$ where $v\in A$ and $v'$ is the largest number smaller than $v$ in $A$.

Answer 2

There is an efficient dynamic programming solution if the input domain is small.

Let $C_i(v)$ be the cost of increasing/reducing elements such that $\hat a_i = v \wedge (\forall j >i)[\hat a_{j} \leq v]$.

It should be obvious that $C_n(v)$ is simply $|a_n - v|$, and thus computing $C_n$ completely is easy.

Then $C_{i}(v)$ is $|a_i - v| + \min(C_{i+1}(0), C_{i+1}(1),\dots,C_{i+1}(v))$. Using this we can compute $C$ as a table, using $C_{i+1}$ to fill $C_i$, working backwards all the way to $C_1$. Then choosing the minimal element of $C_1$ and working forwards again you have found the solution.