Very Difficult Problem that requires Dynamic Prog.

[TiiG]

You are given numbers N and H. H=floors of the building N=number of telephones.
Your must find the MINIMUM amount of throws you need(A) to find out the highest floor from which the telephone will not break when thrown.
For example when you have one phone and 10 floors, you start from the lowest floor and start throwing your phone- if it breaks the highest floor is 1, if not we throw it from the second floor-if it breaks the highest floor is 2....and so on. The problem asks you to find out the MINIMUM amount of throws it will take to find that floor. If N=1, then the answer is always H-because you start from the bottom and go up throwing the phone from every floor till it breaks.

Now when N>1 then that's a whole different story. If you have 2 phones you can throw one from the middle of the building, if it breaks, you only need to check floors 1-(middle-1) with your remaining phone, if it doesn't break you need to check floors (middle+1)-top floor.

At first I thought I could check like this
N=2 case
Throw the phone from the 2 floor then 4 then 6 then 8 then 10 till it breaks, once it breaks we throw the remaining phone from the floor beneath it.
N=3 case
Throw the phone from the 3floor then 6 then 9 then 12 till it breaks, once it breaks throw your second phone from the floor below, if that also breaks throw your last phone from the floor beneath that one.

However this does not work.

Keep in mind your program doesn't let you know whether the phone broke or not. The point of the problem is to find an algorithm which tells you the minimum amount of throws it will take to find an answer.

I was told it has to been done with dynamic programming, however I don't know what to try.
Any help?

[Disch]

Do a binary search. Cut the number of floors in half with each throw.
10 floors and 3 phones:

1) throw floor 6
2) throw floor 3 (or 8)
3) throw floor 1,2 (or 4,5.... or 7... or 9,10)
worst case = 4 throws

[Vlykarye]

That's an interesting problem. I'd agree with Disch on this. A binary search would do..

But what do you mean by dynamic programming?

[TiiG]

Thanks but in some cases the binary search doesn't work correctly.
For example N=2 H=10 the answer is supposed to be 4 but with binary search you get 5.

The people that gave this problem to me said that it had to be done either with dynamic programming or recursion.

See for example when N=2
H=4,5,6 the answer is 3
H=7,8,9,10 the answer is 4
H=11,12,13,14,15 the answer is 5
H=16,17,18,19,20,21 the answer is 6

[rollie]

> Keep in mind your program doesn't let you know whether the phone broke or not
What does that mean exactly?

Either way, this is a really cool problem! I don't see the binary search as optimal, because consider the case that you have 2 phones and 1000 floors. You start w/floor 500, and now have 1 phone - worst means 500 throws, avg case 250. If you change the algorithm to take your first phone and throw it from 20, 40, 60, 80, etc, worst case you throw it 49 times to find out it's between 980-1000, then worst case is you binary search at 990, it breaks, and you throw 9 more times to find the exact floor (so 59 worst). Avg would probably be about half that.

Solution? My instinct is to say, the more phones you have the bigger steps you can take, and use recursion. If you have 2 phones, my goal would be to use an upstep for the first phone such that the max number of steps phone 1 goes through == max number of steps phone 2 goes through. In the case of 1000 floors, I think this is 32. Max steps of the first phone is ~31, max steps for second is also ~31. 32 is the sqrt(1000), which makes sense for this algorithm. so with 2 phones, upstep1 is sqrt(H).

What about with N phones? we need a bigger step. lets consider the 'k' root. of 1000, if 3 phones, the cube root is 10. Hm. If we square that we get 100, and using that as initial upstep, with 10 as 2nd upstep, means each iteration has a maximum number of throws ~9, so ~27 max total. Getting better. How to generalize this? Lets look at 4 phones, and see if a pattern can be determined. 4th root of 1000 is ~5. for each iteration. Cube that, and we have a reasonable upstep - 125. Max iterations @125 is 7, upstep of 125 w/3 phones is (cube root of 125, squared) is 25, which has max iterations of 4. Then 4 iterations over 25 with 2 phones, and finally 4 iterations over 5 with 1 phone, for a total of 19 throws. I think we have a good algorithm!

N = number of phones
H = number of floors
Upstep = H^((N-1)/N)

Once you find the group of floors (which will be of size Upstep) which contain the answer, just call the algorithm again recursively over that group, passing in N = N - 1, and H = Upstep

FYI, I just came up with this algorithm sitting here a few mins (unemployment results in lots of free time I find), and I feel that there should be some small alterations because of the fact that if you are throwing at intervals of 100 over 1000 floors, you don't need 10 throws, you need 9, to determine where the 'break' location is. It may be that your upstep should be (k-root(N) - 1) ^ (k-1)

[cire]

For N = 2 and H=10:

 1
 2
 3   
 4   *
 5   
 6   
 7   *
 8   
 9   *
10

A) Your first throw is at 4.

B) If (broke) your next throw sequence is 1, 2, 3. Minimum is 4. {4,1,2,3}

C) It didn't break: Your next throw will be at 7.

D) If it breaks, your next throw sequence will be 5, 6. Minimum is 4. {4,7,5,6}

E) It didn't break: Your next throw will be at 9.

F) If it breaks, your next throw is 8. Minimum is 4 {4,7,9,8}

G) It didn't break: You throw at 10. Minimum is 4{4,7,9,10}


Consider what happens when we try to define each step here in terms of the orginal problem:

B) The solution is (H=3, N=1) + the one throw we already made.

C) We still have 2 phones, but the number of floors we need to try has been reduced. so
the solution is (H=6, N=2) + the one throw we already made.

D) We're again reduced to one phone, and the number of floors to check is 2, so the solution is (H=2, N=1) + the two throws we already made.

E) Our range is reduced to (8-10) and we still have 2 phones, so the solution is (H=3, N=2)+ the two throws we already made.

F) Solution is (H=1, N=1) + three throws already made.

G) Solution is (H=1, N=2) + three throws already made.

Hopefully, that suggests an avenue of approach.