How can I understand a hint for finding the lowest height of the last bulb in a Garland?

Question

Disclaimer This is not from an ongoing contest, this is from my course on edx of ITMO. Also this is a paid courses so the direct link to the problem is not useful unless you also register this course.

Problem description A garland consists of light bulbs hanging from the same wire. One endpoint of this wire is fixed at a height of $A$ millimeters ($h_1 = A$. Thanks to gravity, the garland bends down: the height of every light bulb which is not at the endpoint is one millimeter smaller than the average height of its neighbors: ($\displaystyle h_i=\frac{h_{i-1}+h_{i+1}}2-1$ for $1 < i < n$).

Determine the smallest height of the second endpoint $B$ ($B= h_n$), given that at most one light bulb is allowed to touch the ground, and for all other light bulbs the inequality ($h_i$ > 0) should be true.

Hint: to solve this problem, you can use binary search.

Input
The first line of the input file contains two numbers $n$ and $A. 3 \le n \le 1000$, $n$ is an integer, $10 \le A \le 10000$, $A$ is a floating-point number which has at most three digits after the decimal point.

Output
Print a single number $B$ , which is the minimal height of the second endpoint. Your answer is considered to be correct if it differs from the right one by at most $10^{-6}$.

Examples

$\displaystyle\begin{array}{|l|l|} \hline \text{input.txt} & \text{ output.txt} \\\hline 8\ \,15 & 9.75 \\\hline 692\ \,532.81 & 446113.34434782615 \\\hline \end{array}$

---

There are problems that you either get it or don't, this is the "don't get it" for me. I cannot correlate the hint to the solution. I mean what we are supposed to search, although I can understand the problem but it's like the hint is the ambiguity for me. Without the hint, I don't know how to proceed, either.

Answer 1

Short answer

Let $d=h_1-h_2$. Do a binary search for the largest value of $d$ in interval $[0,A]$ so that none of $n$ bulbs in the garland will be lower than the ground. The wanted minimum value of the second endpoint $B$ corresponds to the case when $d$ is that largest value.

Explanation

The question is how to understand the hint "you can use binary search".

Before understanding the hint, we are supposed to have understood what is binary search. Binary search is a search algorithm that finds the position of a target value within a sorted array or an interval.

So, what could be that target value we are supposed to search? Within which sorted array or which interval?

• The most obvious target value to search is $m$, the minimal value of $B$. We could search $m$ within the interval $[0, \text{FM}]$, where $\text{FM}$ is the maximum value of a floating-point number.

• Another obvious target to search is about that lowest bulb. In case there are two lowest bulbs, the lowest bulb will mean the one to the left. The further to the right the lowest bulb is, the lower value $B$ is. We could search $\ell$, the rightmost possible position of the lowest bulb within the interval $[0,n]$.

• Whenever we started to compute, we find we have to understand clearly the given equality, $\displaystyle h_i=\frac{h_{i-1}+h_{i+1}}2-1.$ If $h_1=A$ and $h_2$ are known, the height of every bulb is fixed, since $$h_{3}=2\times h_{2}-h_{1}+2$$ $$h_{4}=2\times h_{3}-h_{2}+2$$ $$\cdots$$

  The only requirement is that no bulb can be lower than the ground. Note that

  $$\displaystyle h_{i+1}-h_i=h_{i}-h_{i-1}+2.$$

  As we visit the bulb from left to right, the bulb is dropping less and less between each pair of successive bulbs initially. Once the bulb have reached the lowest level, it will climb more and more between each pair of success bulbs. The larger the first drop $h_1-h_2$ is, the more likely one of the $n$ bulbs will hit the ground and the lower the last $B$ will be. Aha, we can also search the largest value of $h_1-h_2$ within interval $[0, A]$.

How to binary search a real number?

How can we search for the largest value of $d$, which is a real number in an interval?

Since there are infinitely many real number in an interval, checking equality is not likely to work as the stopping condition. That is why we are given the requirement for the "the minimal height of the second endpoint" that it differs from the right one by at most $10^{−6}$". The pseudocode looks like the following.

'''A=h_1, n are given.'''

'''10^(-7) instead of 10^(-6) to guard against rounding errors in computation of floating-point numbers'''
precision = 10^(-7)   

function get_largest_first_drop_by_binary_search():
    L = 0
    R = A
    B_L = last_height(L)
    B_R = last_height(R)
    while ( B_L - B_R > precision):
        m = (L + R) / 2.0
        if hit_ground(m):
           R = m
           B_R = last_height(R) 
        else:
           L = m
           B_L = last_height(L)
    return B_L


function last_height(d):
    ''' Given first drop h_2 - h_1 = d, return h_n, the height of last bulb'''
    return A + ((-d)+(-d+2(n-2)))(n-1) / 2

function hit_ground(d):
    ''' Given first drop h_2 - h_1 = d, return true iff the garland will hit the ground '''
    k = floor(d/2) + 2
    if k >= n return last_height(d) < 0
    if k < n return A + ((-d)+(-d+2(k-2)))(k-1) / 2 < 0
    return false

Implementation

Here is an implementation in Java. Click the run button to see the result.

Exercise

Show that the minimum value of the second endpoint $B$ is 0 if and only if $A \ge (n-1)(n-2)$.