Discussion @ 1066. Garland @ Timus Online Judge

Ярославцев Григорий What is the easiest way to solve this problem?(I have already got AC) [8] // Problem 1066. Garland 13 Apr 2004 18:23

My solution uses binary search to find such height for second lamp that garland is never under the floor and this height is the lowest possible. For checking that garland is never under the floor I use simple O(N).

Vesper Re: What is the easiest way to solve this problem?(I have already got AC) // Problem 1066. Garland 21 Apr 2004 19:02

I have used a simulation method, first I have built that garland thinking that second lamp is at the same height as first, then Ive calculated then minimum of i*H[i] and lowered the garland by the result, and the resulted height of Nth lamp was the answer. Overall O(n) I think.

Sandro Re: What is the easiest way to solve this problem?(I have already got AC) // Problem 1066. Garland 27 Jul 2004 14:40

I like the idea of binary search, but I check that garland is never under the floor in O(1).
It easily can be proved, that the garland has an equation x*x+p*x+A. p is a parameter of binary search. Also it's known, that such a parabola(defined in integer points only) has minimum in floor(0.5-p/2). So the checking is very easy.

Edited by author 27.07.2004 14:40

Anton Chupin Very short solution [5] // Problem 1066. Garland 6 Mar 2005 22:32

Knowing that the form of the garland is parabola and knowing exact solution for h[i], it is very easy to check minimal B:
n--;
for(i=1;i<n;i++)
if((tmp=(n-i)*(n*i-a)/i) >b) b = tmp;
That's all! b is answer!

Kit Re: Very short solution [4] // Problem 1066. Garland 1 Apr 2005 14:54

It is short. But while you will think about a garland's form, I will have written a solution, based on binary search. In real competition it is better.

Chen Yu Re: Very short solution [3] // Problem 1066. Garland 5 Nov 2006 20:34

Actually,we can get the formula by mathematical induction very easily.We can see:
h1=h1,
h2=h2,
Since hn+1=2hn-h(n-1)+2,
so we can find:
h3=2h2-h1+2,
h4=3h2-2h1+6,
h5=4h2-3h1+12,
and by mathematical induction,not difficult to prove:
hn=(n-1)h2-(n-2)h1+n(n+1).
Thus we can trace every hi>0 and get the minimum for h2 and then we can find hn.

PSV Re: Very short solution // Problem 1066. Garland 5 Nov 2006 21:19

Guys why this cleverness. Binary search - is solution that author recognized I think. But about parabolf thinking is good idea - you're clever boys ;)

kobra Re: Very short solution [1] // Problem 1066. Garland 27 Jun 2008 02:33

I have change h2 to h, h1 to A and n to x. Then i have get something like x^2+bx+c. hn>0 if that formula ax^2+bx+c>=0. Its possible only if D<=0. I have found and get the othe formula but now with h like h^2+bh+c.
After that i have found h1 and h2, and choose the smallest bigger than 0. And that result i have written in the first formula, and have found B. But the problem that my result is different from the real, but not very much.
its my code:

#include <stdio.h>
#include <math.h>

int main()
{
    int N,i;
    double h1,h2,A,B,min;
    scanf("%d%lf",&N,&A);
    h1=A+1.0+2*sqrt(A);
    h2=A+1.0-2*sqrt(A);;
    if(h2<h1&&h2>0) min=h2;
    else min=h1;
    B=(N-1)*min-(N-2)*A+(N-1)*(N-2);
    printf("%0.2lf",B);
    return 0;
}

PS sorry for my English

Edited by author 27.06.2008 02:38

Zero O(n) solution // Problem 1066. Garland 24 Jun 2013 14:19

a2=(1/2)a1 + (1/2)a3 -1
a3=(1/3)a1 + (2/3)a4 -2
a4=(1/4)a1 + (3/4)a5 -3
...
an=(1/n)a1 + ((n-1)/n) a(n+1) - (n-1)

Just by putting a2 into a3's initial formula a3=(1/2)(a2+a4) -1 and so on, you can get the relationship of an and a(n+1), then you can guess An, and calculate the whole sequence. As long as ai>=0, An can be lower, in this way you'll get the answer.

Discussion of Problem 1066. Garland