How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?

Question

You are given n integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a non-decreasing sequence. Define the deviation of such a sequence to be $\max(|a_1-b_1|, \ldots, |a_n-b_n|)$. Design an algorithm that finds the $b_i$'s with the minimum deviation in runtime $O(n\sqrt[4]{l})$.

I honestly have no clue whatsoever how to even begin to solve this question. It looks like a dynamic programming question to me, but the professor said that this should be solved using a greedy algorithm. It would be much appreciated if someone can point me in the right direction by giving a small hint.

Answer 1

Let's start with the following observation:

Let $max$ denote the maximum of the sequence $a_1,...,a_n$, and let $min$ denote its minimum. If $a_1=max$, then choosing $b_1=b_2=...=b_n=\lfloor(max+min)/2\rfloor$ is optimal.

Why is this the case? Well, since the sequence starts with the maximum, either we choose $b_1$ large, and suffer a large deviation from the minimum of the sequence (since any subsequent $b_i$ must be greater or equal to $b_1$), or we choose $b_1$ small and suffer from the deviation to $max$. The average minimizes the maximal deviation.

We can now try to generalize this observation to use on general sequences $a_1,...,a_n$. For instance, we can partition any sequence into subsequences, such that each begins with the maximum of the respective subsequence.

Example: $(2,6,4,1,5,2,8,7,5,1)$ is partitioned into $(2)$, $(6,4,1,5,2)$, and $(8,7,5,1)$.

Given this partitioning, we can now solve each these subsequences separately, and obtain an assignment of the $b_i$'s, which however might violate the non-decreasing condition. This can be fixed without losing optimality.

Observe that the last subsequence always contains the maximum $max$ of the whole sequence (otherwise, there would be another subsequence after it). Let $w_1,w_2,...,w_k$ be the values we assigned to the $k$ subsequences. Now, to achieve non-decreasingness in $w_1,...,w_k$, we start from the back at $w_k$ and work our way to the front. If $w_{k-1}$ is larger than $w_k$, we simply set $w_{k-1}:=w_k$. If it is smaller, we keep it. Then, we proceed with comparing $w_{k-2}$ with $w_{k-1}$ and so on. Note that lowering any $w_i$ to the value of $w_{i+1}$ never increases the deviation, since the maximium value in the subsequence assigned with $w_i$ is always lower than the maximum in the subsequence assigned with $w_{i+1}$.

This algorithm should be correct, I think. Concerning the running time, the key step is computing the increasing maxima for the subsequences, which is possible in $O(n)$? Not sure where $l$ contributes.

Answer 2

I'm going to think out loud here just working through the hints you've given. Let's go to the original hint of saying that $O(nl)$ is what you should try first. I can think of a greedy algorithm that has that time.

The $l$ part of the time complexity means you can keep a list of the count of each occurence of each value $0..l$. That, is just create a set $\text{Count} = { C_0, \ldots, C_l} $ which tracks the count of each $l$ in the set. You can create the initalize list by scanning the input sequence once.

You can scan this list in $O(l)$ to get the maximum and minimum value. If you were to fill the entire list of $b$ with this mid-point your variance would simply be the difference from this value and the max/min. This is basically your worst-case scenario, let's call it $b_w$.

So work your way to $b_i$ from the left. You can both drop this elemeent from $\text{Count}$ and get the min/max of $b[i+1] \ldots b[n]$ in $O(l)$. Now we can be greedy. We don't choose $b_i > b_w$ since that forces the remaining entire list up (to meet the non-decreasing requirement) and thus increases the variance. The minimum value we can choose is $b[i-1]$. If $a_i$ is in the acceptable range we select it, if below the range than use the minimum. This minimizes the variance at $b_i$ given known constraints.

This is just an idea, perhaps I'm lucky and it points you in the right direction. This algorithm may not work (it does for my few simple tests), but it does match the hints given, so perhaps it is helpful. If correct it is easy to see that the $O(l)$ part can for sure be dropped to $O(\log l)$, about even further, I'm not sure.

Answer 3

Here is the professor's solution, which he calls "reduction": For each $i$ from $0$ to $l$, try to construct a solution if we know that the deviation is less than or equal to $i$. The first $i$ for which a solution can be found is the minimum deviation. We can find a solution given the deviation in $O(n)$ time. So the running time is $O(nl)$. Then, instead of using linear search, we can use binary search to determine the smallest deviation for which a solution is possible. This reduces the running time to $O(n\log l)$, which satisfies the requirement of $O(n\sqrt[4]{l})$.

Answer 4

I think this should be doable in O (n).

Take the similar problem: Given $a_i$, 1 ≤ i ≤ n, and d ≥ 0, find $b_i$ in non-descending order such that $|a_i - b_i| ≤ d$ for all i, or show that it isn't possible. This can be done in O (n), and using binary search the original problem is solved in O (n log l).

Now if there are i ≤ j such that a_i - a_j > 2d, then there is no solution (because $b_i ≥ a_i - d, b_j ≤ a_j + d < a_i - 2d + d = a_i - d ≤ b_i$).

But if a_i - a_j ≤ 2d for all i ≤ j then I think a solution will always be found. So all we have to do is find m = max (a_i - a_j) for all i ≤ j, and choose d = floor ((m+1) / 2). That maximum can be found in O (n).