Given two arrays $A$ and $B$ of integers, both of size $N$, such that for all $0 \le i \le N-1$, $A[i] \ge B[i]$, we have to convert array $A$ to array $B$. For this we can do only one type of operation: choose some $l$ and $r$ ($0 \le l \le r \le N-1$) and set the values of $A[l],A[l+1],\ldots,A[r]$ to $k$, where $k \le A[i]$ for all $l \le i \le r$. Find out minimum operations to convert $A$ to $B$.

I was thinking about dynamic programming solution but could not figure it out.


Let distinct elements of $B$ be $b_1,b_2,\ldots$ where $b_1>b_2>\cdots$. There must be an optimal solution where it first sets a range to $k_1$ then set a range to $k_2$ and so on, such that $k_1\ge k_2\ge\cdots$ (otherwise one can swap related operations to meet the constraint without changing the result), and $k_1,k_2,\ldots\in\{b_1,b_2,\ldots\}$ (otherwise, say $k_i\notin\{b_1,b_2,\ldots\}$, one can delete the $i$th operation without changing the result).

Using the property above, we have the following greedy algorithm.

Let $B[i_1],B[i_2],\ldots$ ($i_1<i_2<\cdots$) be the greatest elements, i.e. $b_1$. The algorithm firstly sets $A[i_1],A[i_2],\ldots$ to $b_1$ using as little operations as possible. More specifically, it checks whether $A[i_1]>b_1$ to see whether an operation is required to set $A[i_1]$ to $b_1$. If so, it then checks whether $A[i_1+1],\ldots,A[i_2-1]\ge b_1$* by range minimum query to see whether this operation can be merged with the operation corresponding to $A[i_2]$. It then goes on with $A[i_2],A[i_3],\ldots$ For example, say

A: 3 3 3 3 2 1 3
B: 2 1 2 1 2 1 2

Now $b_1=2$ and $i_1=0, i_2=2, i_3 = 4, i_4=6$. It requires 2 operations to set $A[i_1],A[i_2],\ldots$ to $b_1$: first setting $A[0], \ldots, A[2]$, then setting $A[6]$.

The algorithm then repeats the above process for $b_2,b_3,\ldots$

This algorithm runs in $O(n\log n)$.

*Note, for example, when dealing with $b_2$ instead of $b_1$, no operation can be performed on a range containing $i_j$ for some $j$, otherwise $A[i_j]$ will be less than $B[i_j]$ and cannot be recovered. Therefore we must also check this constraint here. This can be done by maintaining a sorted index array of all elements greater than $b_m$ when dealing with $b_m$.


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.