10934 - Dropping water balloons

[Towhid]

Hi
I couldn't understand the problem statement
Can anybody tell me what it says?????

[Niaz]

Same problem here... waiting.....

[mido]

Ditto....

[misof]

Well, the statement is pretty clear. You want to determine an unknown height H such that a balloon will burst if dropped from the height H, but not, if it is dropped from a lower height. You want to minimize the required number of balloon throws in the worst possible case.

N is the height of the building, K is the number of balloons you have.

Example 1. K=1. You only have 1 balloon. Once it bursts, you are out of balloons and you have to know the correct answer. Thus, the only strategy that guarantees that you will find H is to try to drop the balloon from the first floor, if it doesn't break, try the second floor, then the third one, etc. In the worst case you need N throws.

Example 2. K=100, N=15. Now we have plenty of balloons. The best strategy is to use binary search. I.e., in the first step throw a balloon from the 8th floor. If it bursts, the answer is between 1 and 8, if it doesn't, the answer is larger than 8. Four (or maybe five, I'm too lazy to check) throws are enough in this case.

[mido]

I still don't get how 14 is the answer for k=2 and n=100. From what I understood, we would throw a balloon at level 50. Assuming that it bursts, then we would need 49 trials to test the range from 1 till 49.

[little joey]

Just try it:
- throw the first balloon from the 14th floor, if it bursts, you'll have 13 more tries for floors 1 to 13;
- if it doesn't burst, throw it from the 27th floor, if it bursts, you'll have 12 more tries for floors 15 to 26;
- if it doesn't burst, throw it from the 39th floor, if it bursts, you'll have 11 more tries for floors 28 to 38;
- if it doesn't burst, trow it from the 50th floor, etc.

Got it?

[Niaz]

Now the problem is clear to me. But, still have one more question about the solution. How did you find that the starting position would be 14! Would you please explain a little about your algorithm? As the solving rate is very high, I guess, this is an easy problem but stuck over there.

[misof]

Now the problem is clear to me. But, still have one more question about the solution. How did you find that the starting position would be 14! Would you please explain a little about your algorithm? As the solving rate is very high, I guess, this is an easy problem but stuck over there.

Don't be mistaken. This is NOT an easy problem. Note that the total number of submissions is really low when compared to other problems from the same set. The high solving rate only says "once you get it, it's unlikely you will make a mistake in coding it".

The trick is to consider an "inverse" question: Given K balloons and the opportunity to make L drops, what is the tallest building that can still be solved?

[shanto86]

well... is the second case 10 786599 wrong? i mean the output is given 21. but it needs more than 63 moves.

BTW, i am getting WA can anyone plz check this?

Code: Select all

AC

just find answer recursively. then convert it to DP. say you want to find ans[n][m]. it will depend on ans[n-1][0 to m-1].

[DRONZER]

@little joey: i can understand how 2 100 case works. last two cases are:

Code: Select all

63 9223372036854775807

Due to binary search the result is 63 for the last case.

But how does:

Code: Select all

10 786599
60 1844674407370955161

will work? I mean for k>2 how will it work?

for k=2, it seems we have just the sequnce 1,2,3,4...
what for k=3, 4, ... ?

[bill8124]

for k=2, it seems we have just the sequnce 1,2,3,4...
what for k=3, 4, ... ?

You can try this instead of binary search:
f(b,t)=f(b-1, t-1)+1+f(b, t-1)
f: the highest floor you can definitely find the floor where the water balloon will burst
b: water balloons you have
t: the number of times you can try

then it becomes a dynamic programming problem
hope this helps!
---
last post was June 2006 ....kerker
I solved this problem because of submission mistake XD
(I sent the code of 10924 to 10934..)

[DD]

for k=2, it seems we have just the sequnce 1,2,3,4...
what for k=3, 4, ... ?

You can try this instead of binary search:
f(b,t)=f(b-1, t-1)+1+f(b, t-1)
f: the highest floor you can definitely find the floor where the water balloon will burst
b: water balloons you have
t: the number of times you can try

then it becomes a dynamic programming problem
hope this helps!
---
last post was June 2006 ....kerker
I solved this problem because of submission mistake XD
(I sent the code of 10924 to 10934..)

I use similar method to solve this problem. First, I build a f(b,t) table for all possible combinations of b and t according to problem description. Then for each k and n, I use binary search to find the answer.

[paulliu]

35 4564996047803285891
63 10200434957544002416
6 8594083207451185996
26 11596953366899797872
94 13934715367743307893
100 2427617038504671597
13 5662331197191996410
83 3251182759881391873
56 9830927489542347198
59 14389584202107743284
0 0

What about this input? Is this input valid?

For
63 10200434957544002416
I think it should output "More than 63 trials needed.".
Because 63 balloons with 63 trails can only reach 9223372036854775807.
But uDebug outputs only 63.