6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Try first solving the problem for very short $L$, say of sizes $2,3,4$. Then come up with a formula. Then come up with an efficient algorithm for computing it. $\endgroup$ – Yuval Filmus Apr 17 '15 at 4:19
  • 1
    $\begingroup$ Maybe try dynamic programming. Do you have more examples for checking? $\endgroup$ – hengxin Apr 17 '15 at 10:00
  • $\begingroup$ @YuvalFilmus, @hengnix. Thanks. I know it must be solved by DP and some kind of backtracking but I'm unable to find a good way to solve it even for a short list. Let's say, I pick the min of the list (here 2) and then iterate over the list and try to find the minimum value m that either item + m or item - m is still greater than min . Now, next item and updated min and so on. But that doesn't take me any where. $\endgroup$ – norbertpy Apr 17 '15 at 16:39
  • $\begingroup$ @hengxin, I'll try to find some more examples. That's gonna help. There are few solutions that I'm not sure if correct or not. But I don't understand their logic. Here, here and here $\endgroup$ – norbertpy Apr 17 '15 at 16:49
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Inspired by Bergi's answer, I've written this:

import math

a = [5, 4, 3, 2, 8]
b = [5, 4, 3, 0, 8]
c = [5, 4, 110, 0, 8]
d = [5, 4, 3, -16, 8]


def hill(a):
    max_m = 0
    head = a[0]
    for item in a[1:]:
        current_m = math.fabs(head + 1 - item)

        if current_m > max_m:
            max_m = current_m

        # update the head for next iteration
        head = item + current_m

    print math.ceil(max_m / 2)

hill(a) # 3.0
hill(b) # 4.0
hill(c) # 107.0
hill(d) # 12.0

The logic is, we set the max_m to zero and the head to first element of the list. We then start iterating through the list - first element and find the minimum value current_m such that adding current_m to the item will be equal to head + 1. At each iteration of we find a greater m, we just store it in max_m.

At the end we divide the m by 2 since we just used the addition to find the m and not the subtraction.

I hope this helps but I'm still not sure if it's correct for all inputs.

$\endgroup$
1
$\begingroup$

I took three test cases L1 = [5, 4, 3, 2, 8], L2 = [5, 4, 3, 0, 8] and L3 = [4, 6, 1, 2, 5, 7] and performed the following steps:

  1. Take the mean, x of all numbers except the last.

    x1 = mean(L1') = 3.5
    x2 = mean(L2') = 3
    x3 = mean(L3') = 3.6
    L' is the list excluding last number.
    
  2. Perform ceil(x) and duplicate the list L into M

    x1 = 4, x2 = 3, x3 = 4
    
  3. Start from the center, M'[middle] do:

    M[i] = --x if i < middle, else
    M[i] = ++x if i > middle.
    

Find the maximum difference, m(which is the required answer) between each element of M[i] and L[i].

http://ideone.com/SwwXjm

$\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.