10934 - Dropping water balloons

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

10934 - Dropping water balloons

Post by Towhid » Sun Oct 16, 2005 9:42 am

Hi
I couldn't understand the problem statement :oops:
Can anybody tell me what it says?????
From 0 to 0

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » Sat Oct 22, 2005 1:52 pm

Same problem here... waiting.....
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Thu Nov 17, 2005 10:31 am

Ditto....

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Thu Nov 17, 2005 5:01 pm

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
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Mon Nov 21, 2005 12:29 am

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Nov 21, 2005 2:21 am

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
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:

Post by Niaz » Thu Nov 24, 2005 10:37 am

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. :oops:
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Thu Nov 24, 2005 2:41 pm

Niaz wrote: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. :oops:
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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun Jun 18, 2006 9:33 pm

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].
Last edited by shanto86 on Wed Jun 21, 2006 8:39 am, edited 2 times in total.
Self judging is the best judging!

DRONZER
New poster
Posts: 1
Joined: Tue Jun 20, 2006 2:29 am

Post by DRONZER » Tue Jun 20, 2006 2:36 am

@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
New poster
Posts: 8
Joined: Fri Jan 21, 2011 8:13 am

Re:

Post by bill8124 » Fri Feb 18, 2011 5:59 pm

DRONZER wrote: 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
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10934 - Dropping water balloons

Post by DD » Sat Apr 09, 2011 3:33 am

bill8124 wrote:
DRONZER wrote: 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.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

paulliu
New poster
Posts: 1
Joined: Fri Apr 24, 2015 8:07 pm

Re: 10934 - Dropping water balloons

Post by paulliu » Fri Apr 24, 2015 8:16 pm

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.

Post Reply

Return to “Volume 109 (10900-10999)”