Cheap and Secure Web Hosting Provider : See Now

[Solved]: Find the minimum range

, , No Comments
Problem Detail: 

Given a list of numbers as L, how do you find the minimum value m such that L can be made into a strictly ascending list by adding or subtracting values from [0,m] from each element of L except the last? (Strictly ascending means the new list can't have any duplicates.)

Example #1:

for L = [5, 4, 3, 2, 8] the minimum value for `m` is 3.  5 - 3 = 2 # subtract by 3 4 - 1 = 3 # subtract by 1 3 + 1 = 4 # add by 1 2 + 3 = 5 # add by 3 8 untouched # nothing  result = [2, 3, 4, 5, 8] 

Example #2:

for L = [5, 4, 3, 0, 8], minimum value for `m` is 4 

NOTE: I'm not looking for a complete solution just give me few thoughts and clue.

Asked By : norbertpy

Answered By : hengxin

Below I try to prove that the greedy algorithm ($\mathcal{A}$) given by @norbertpy (and @Bergi) is correct. Please check it.


Problem Definition:

The algorithm $\mathcal{A}$ of @norbertpy is for a variant of the original problem:

To find the minimum positive number $2m$ such that for each item in the array, adding a number from $[0, 2m]$ can lead to a strictly ascending array?

The solutions to these two problems can be reduced to each other (by $\pm m$). Note that I have ignored the "except the last" part.


A lemma for the property of the algorithm $\mathcal{A}$:

Let $L'[n]$ be the last element of the resulting strictly ascending list of any feasible solution to $L[1 \ldots n]$. We first claim that:

Lemma: $\mathcal{A}$ gives the smallest value of $L'[n]$ among all the feasible solutions to $L[1 \ldots n]$.

This lemma can be proved by mathematical induction on the length $n$ of $L$.


Now we prove that $\mathcal{A}$ always gives the optimal solution.

Base case: $n = 1$ and $n = 2$ are trivial.

Inductive Hypothesis: Suppose that for any $L[1 \cdots n-1]$ of length $n-1$, the algorithm $\mathcal{A}$ gives us the optimal solution $m$.

Inductive Step: Consider the $n$-th iteration of the greedy algorithm $\mathcal{A}$: it compare a = head + 1 - L[n] with $m$, and take $M = \max(m,a)$ as the feasible solution to $L[1 \cdots n]$.

We aim to prove that

$M$ is the optimal solution to $L[1 \cdots n]$.

Suppose, by contradiction, that there is another feasible solution to $L[1 \cdots n]$, denoted by $M' < M$.

First, $m < M'$: otherwise, $M'$ is a smaller feasible solution to $L[1 \cdots n-1]$, which contradicts the assumption.

Thus we have $m < M' < M$. Because $M = \max(m,a)$, we obtain $m < M' < M = a$.

By the lemma above, $L'[n-1]$ in the solution corresponding to $M'$ is not less than that in the solution corresponding to $m$. However, $L'[n]$ (for $M'$) is less than that for $M$ (because $M' < a$). According to the way how $a$ is chosen in $\mathcal{A}$, the resulting array (for $M'$) is not strictly ascending. Thus $M'$ cannot be a solution. Contradication.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41482

 Ask a Question

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback