Register Now
Member Count: 256,877 - July 29, 2010  [Get Time]
Login
forums   
Round Tables
News Discussions
Algorithm Matches
High School Matches
Assembly Contests
Marathon Matches
Software Forums
Sponsor Discussions
Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Forums News Discussions 2008 TopCoder Open Shortest 250 in Qual 1 [ 1 2 ]    NEXT >
Shortest 250 in Qual 1 | Reply
Turns out that you don't need B after all... Can someone prove it?

public class MonstersAndBunnies
{
	public double survivalProbability(int M, int B)
	{
		return ++M%2./M;
	}
}


EDIT: I love how Java lets you take modulo of a double!
Re: Shortest 250 in Qual 1 (response to post by dimkadimon) | Reply
Can someone prove it?

Yeah. Order the monsters together with yourself in the order that you're called up to fight. You live iff the number of monsters is even and you're last in the order, which happens with probability 1/(M+1).
Re: Shortest 250 in Qual 1 (response to post by Minilek) | Reply
No I meant prove the fact that you don't need B.
Re: Shortest 250 in Qual 1 (response to post by dimkadimon) | Reply
you don't need Bunnies just because they haven't any role for saving your life, if we have at least one monster all bunnies will be eaten so you stay you and the monster(s) and then you do like Minilek did ... , and if there is no monster then we will live
Re: Shortest 250 in Qual 1 (response to post by dimkadimon) | Reply
His explanation of the solution didn't include B at all, that kind of proves that you don't need it ;).

Also, the C++ version here is still shorter.
Re: Shortest 250 in Qual 1 (response to post by aussie) | Reply
Yeah I agree its shorter, but mine is prettier :p because i can do %2.
Re: Shortest 250 in Qual 1 (response to post by Minilek) | Reply
Nice proof,thanks. I will not forget this problem. I was on the right track, and needed about 3 more minutes for the right solution, but ran out of time. I did a different rationale, using gauss summation, combinations and recursion. This passed the system test (In the practice room).

double Prob(int M)
{
  if (!M)
    return 1;
 
  if (M % 2)
    return 0;
 
  return (M - 1.0L) / (M + 1.0L) * IT (M - 2);
}
 
double
MonstersAndBunnies::survivalProbability(int M, int B)
{
  return Prob(M);
}


The first factor in the return statement is the simplification of:
((M - 1 ) * M / 2) / (M! / (2! * (M - 2)!)
Re: Shortest 250 in Qual 1 (response to post by dimkadimon) | Reply
my favorite quote from last night: stupid irrelevant bunnies...
Re: Shortest 250 in Qual 1 (response to post by dimkadimon) | Reply
Sadly, I coded the correct solution and even tested a couple of cases by hand, but just before submitting, I decided that bunnies had to matter and changed my code. It didn't help that the only 2 examples with bunnies were trivial and didn't show that you didn't need them. My thought was the number of bunnies ultimately would impact the probability; I'm still not convinced it wouldn't. But more people seem to be saying they don't than do.
Re: Shortest 250 in Qual 1 (response to post by enefem21) | Reply
Off-topic: enefem21, could you please explain your solution in detail: http://www.topcoder.com/stat?c=problem_solution&rm=268839&rd=12007&pm=8595&cr=20092786?
Re: Shortest 250 in Qual 1 (response to post by armansuleimenov) | Reply
1. realize that bunnies don't matter
2. make the following observation:
The game contains me and M monsters. What happens in the next event?
There are A=(M+1 choose 2) possible meetings, out of those B=(M choose 2) don't involve me. In these cases I'm still in the game, and M-2 monsters are left.
Thus:
probability(win with M monsters) = B/A * probability(win with M-2 monsters).
Re: Shortest 250 in Qual 1 (response to post by Minilek) | Reply

Order the monsters together with yourself in the order that you're called up to fight. You live iff the number of monsters is even and you're last in the order


Is this a direct conclusion of M!/(M+1)! ?
Re: Shortest 250 in Qual 1 (response to post by misof) | Reply
Got it, thank you very much!
Re: Shortest 250 in Qual 1 (response to post by karthik_1986) | Reply
karthik_1986:


Order the monsters together with yourself in the order that you're called up to fight. You live iff the number of monsters is even and you're last in the order.

Is this a direct conclusion of M!/(M+1)! ?


Just an example and I hope it makes it clear. 4 Monster and You. The possibilities are:

YMMMM
MYMMM
MMYMM
MMMYM
MMMMY <= You only survive here.

So, it is 1 / (M + 1) if the number of monsters is even. Try with more monsters and see for yourself.
Re: Shortest 250 in Qual 1 (response to post by Uranium-235) | Reply
If only they included a larger case with more bunnies then everything would be so much easier...
Forums News Discussions 2008 TopCoder Open Shortest 250 in Qual 1
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >

RSS