0
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ There are problems that you either get it or don't, this is the 'dont get it' for me. I cannot correlate the hint to the solution. I mean what are we supposed to search, yes I can understand the problem but it's like the hint is the ambiguity for me, even without it, I still don't know how to proceed. $\endgroup$ – Loc Truong Apr 28 at 5:55
  • 2
    $\begingroup$ I don't see any question here. We're a question-and-answer site (not a homework help site), so it's not enough to paste an image of your exercise; you need to articulate a specific question about it. I encourage you to edit your question to articulate a specific question. See here for tips on asking questions about exercise problems. $\endgroup$ – D.W. Apr 28 at 6:33
  • $\begingroup$ @D.W. Could you please delete all comments? Thanks. $\endgroup$ – Apass.Jack Apr 28 at 16:32
  • $\begingroup$ I've deleted the ones that to me seem no longer applicable. I still don't see any question stated in the body of the post, and I still think that it's hard to know how to answer without some explanation of what the poster does understand and doesn't understand (saying "I don't get it" give me much guidance). Feel free to flag any others that seem obsolete and they'll be handled as well. $\endgroup$ – D.W. Apr 29 at 0:18
  • $\begingroup$ Ah, @@ sorry I didn't mean to ignore this. $\endgroup$ – Loc Truong May 2 at 6:50
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Impressive, at first I also bang my head around to understand the hint, I asked myself "what are we supposed to look for?". I think your last observation is the most important one, I couldn't figure out that, to get minimal height of B, we need to make the first drop as large as possible. $\endgroup$ – Loc Truong Apr 28 at 16:30
  • $\begingroup$ One more question, the interval [0, A] is pretty much involve infinite numbers, because A is a floating point number, how can we do searching? $\endgroup$ – Loc Truong Apr 29 at 10:50
  • $\begingroup$ Sorry but I'm lost :( would you mind providing more details of picking value of d in interval [0, A], or even the whole steps from picking d to end of binary search as I still can't understand the whole picture? $\endgroup$ – Loc Truong Apr 29 at 13:25
  • $\begingroup$ $$h_{3}=2\times h_{2}-h_{1}+2$$ Given that formula, how can we calculate $h_{n}$ @@ ? I think at this point you can give me the entire pseudocode, I will look at it and try to understand more clearly how the binary search correlates to the min heigh of $B$. $\endgroup$ – Loc Truong Apr 30 at 4:04
  • $\begingroup$ We only know the difference between $h_{1}$ and $h_{2}$, we don't know the actual values of $h_{1}$ and $h_{2}$, given the formula for $h_{3}$ , $2 * h_{2} - h_{1} + 2$, we can't compute $h_{3}$ because $2 * h_{2}$ is executed first :| or it should be $2 * (h_{2} - h_{1}) + 2$? $\endgroup$ – Loc Truong Apr 30 at 4:17

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.