2
$\begingroup$

We have given an array of size $N$, consisting of positive integers, and an integer $H$. We also know that an array is stable iff $|A_i - A_{i-1}| \leq H$ for each $1<i<N-1$. We can modify the element by adding +1 to some element or by adding -1 to some element, we don't have a limit on how much we can use those operations, but we want to make the array stable in minimum moves.

I started solving the task by writing a dynamic programming relation, described by the state $f(i, j)$ meaning the minimum moves to stabilize the first $i$ elements of the array, such that the last element is equal to $j$.

However it seems that this method is slow for big values of $N$. How would you approach solving this problem?

$\endgroup$
1
$\begingroup$

Let $M=\max_i|A_i|$.

Besides the linear programming method proposed in this post (which is suitable for small $N$ and large $M,H$), you can optimize your dynamic programming method by building a larger table to reduce the time for querying the minimum value among $f(i-1,j-H),\ldots,f(i-1,j+H)$.

Let $f(i,j,k)$ be the minimum moves to stabilize the first $i$ elements of the array, such that the last element is in the range $\left[j,j+2^k\right)$. Then we have $f(0,j,0)=0$, $$f(i,j,0)=|A_i-j|+ \min\left\{f\left(i-1,j-H,\hat{k}\right),f\left(i-1,j+H+1-2^{\hat{k}},\hat{k}\right)\right\}$$ where $2^{\hat{k}}>H$, and $$f(i,j,k)= \min\left\{f(i,j,k-1),f\left(i,j+2^{k-1},k-1\right)\right\}$$ for $k>0$. Note each entry can be calculated in $O(1)$ time if we calculate them in some proper order.

Note in an optimal solution, the final $A_N$ must be in the range $[-(M+NH),M+NH]$ (otherwise the final elements are all either greater than $M$ or less than $-M$, which is not optimal), so we need to calculate $f(i,j,k)$ for all $i,j,k$ such that $0\le i\le N$, $j\ge -(M+(2N-i)H)$, $k\ge0$ and $j+2^k\le M+(2N-i)H+1$. The time complexity is $O\left(N(M+NH)\log (M+NH)\right)$, while the naive $f(i,j)$ solution takes $O(N(M+NH)H)$ time.

You can further use the range minimum query technique to reduce the time complexity to $O(N(M+NH))$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.