Page 1 of 1

10218 - Let's Dance !!!

Posted: Sat Jun 07, 2003 8:08 am
by Andhika Dharma
i`ve been given an assignment from my lecturrer.
it`s about the "let`s dance!!" topic problem set no 10218
would somebody please help me , at least about the algorythm
i can`t even understand the problem

10218 - Let's Dance!!

Posted: Sun Jun 08, 2003 5:37 pm
by Andhika Dharma
could somebody please explain to me about problems no 10218
i can`t understand the problems totaly.
PLEASE........

Posted: Wed Jun 18, 2003 11:47 am
by Observer
Yes...

Someone plz explain the problem description to us!! Thx in advance!!

Posted: Tue Dec 09, 2003 11:27 am
by Observer
Still... no reply... after half a year... :(

Posted: Sat Jan 17, 2004 8:51 pm
by UFP2161
Is the sample input/output correct?

From the problem description, I do this for the second example input (10 20 7):

There are 30 people total. We choose any 7. Total number of possible groups is 30 choose 7 or 2,035,800.

Now, the only way to split CC equally among 2 groups is if the number of men is 0, 2, 4, or 6. The number of groups that exist are:

10 choose 0 * 20 choose 7 plus
10 choose 2 * 20 choose 5 plus
10 choose 4 * 20 choose 3 plus
10 choose 6 * 20 choose 1 equals 1,018,800

1,018,800 / 2,035,800 equals 0.5004421 which is not the expected 0.5002286.

Is there something in the problem that I'm misinterpreting?

I also wrote a brute force checker and the numbers turn out as above.

Posted: Sat Feb 14, 2004 11:44 pm
by Noim
hi all,

after a hard effort , i manage to solve this problem :lol: .

i assume that, i have c candy and i am gonna give the first candy to one of all(w+m) people. after that i am ready to give second candy to again one of all (w+m) people. this mean the candy does not identical or something like that, but the order of the candy does not matter. and i also assume all the men are identical and all the women are identical. and a man can hold more than one candy or no candy which does not matter for this problem. i have to just distribute the candy to a group of man whatever one of them take more than one or all of the take more then one. and every time i am going to distribute the candy into all people .

i am not sure that i am using the right assumption to solve the problem. if i am wrong please tell me that .

i think these will help.

Re: 10218 - Let's Dance!!

Posted: Mon May 19, 2008 10:19 pm
by Robert Gerbicz
Here it is the exact values for the sample input:

Code: Select all

f(10,20,20)=1743392201/3486784401
f(10,20,7)=1094/2187
As you can see in the first testcase the result is very close to 0.5, but it is differ from that in reality.

Re: 10218 - Let's Dance !!!

Posted: Tue May 26, 2015 3:09 am
by predicate
The problem statement should be a little more clear.
It took me a while to figure out what the problem statement actually wants to say. We have m men and w women who are identical and c candies which are not identical. So, we have to take into account the type of candies that people receive, the distinction has to be made just between men and women and not which men or women gets the candy.
  • P(that a man gets a candy) = m / (m + w) = p
  • P(that a women gets a candy) = w / (m + w) = (1 - p)
Now we have to distribute candies so that men get an even number of candies,
(c choose 0) * (p^0) * ((1-p)^c) + (c choose 2) * (p^2) * ((1-p)^(c-2)) + (c choose 4) * (p^4) * ((1-p)^(c-4)) + ---
this is the binomial expansion of ((a+b)^n + (-a+b)^n) / 2, where a = p; b = (1-p)