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.


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.


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.


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})$.

  • 4
    $\begingroup$ So the $O(n\sqrt[4]{l})$ was a trick... But I am more intrigued by the "We can find a solution given the deviation in O(n) time" .. how is that not the interesting part? $\endgroup$ – jmad Jun 8 '12 at 19:29
  • $\begingroup$ @jmad Given $i$, for each $j$, take $b_j$ as the lowest value which is at least as big as all previous $b_k$, and which is no more than $i$ away from $a_j$. If we can't find such a value, what does it mean? It means that a previous $b_t$ is more than $i$ bigger than $a_j$. So a previous $a_t$ is more than $2i$ bigger than $a_j$. So that value of $i$ wasn't possible. If you get through the $n$ values without getting stuck like this, you have found a solution for $i$ without backtracking, in time $O(n)$. $\endgroup$ – jwg Sep 6 '17 at 10:09
  • $\begingroup$ O (n log l) would have been a strong hint that you need to do some binary search over the range 0 to l. $\endgroup$ – gnasher729 Apr 12 '18 at 11:19

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).

  • $\begingroup$ Intriguing idea! I can believe something like this might work, but it seems like there's a big gap at the end of your answer and I'm having a hard time filling in the details. Do you have a proof that if $a_i - a_j \le 2d$ for all $i\le j$ then a solution always exists? More importantly, how do we find it? The original question says we must find the $b_i$'s. Even if we assume a solution exists, I'm having difficulty seeing how to find the corresponding $b_i$'s. Can you elaborate on that? $\endgroup$ – D.W. Apr 12 '18 at 17:23

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.