10218 - Let's Dance !!!

All about problems in Volume 102. 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
Andhika Dharma
New poster
Posts: 2
Joined: Sat Jun 07, 2003 7:51 am

10218 - Let's Dance !!!

Post by Andhika Dharma » Sat Jun 07, 2003 8:08 am

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

Andhika Dharma
New poster
Posts: 2
Joined: Sat Jun 07, 2003 7:51 am

10218 - Let's Dance!!

Post by Andhika Dharma » Sun Jun 08, 2003 5:37 pm

could somebody please explain to me about problems no 10218
i can`t understand the problems totaly.
PLEASE........

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Jun 18, 2003 11:47 am

Yes...

Someone plz explain the problem description to us!! Thx in advance!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Dec 09, 2003 11:27 am

Still... no reply... after half a year... :(
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Sat Jan 17, 2004 8:51 pm

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.

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Sat Feb 14, 2004 11:44 pm

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.
__nOi.m....

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 10218 - Let's Dance!!

Post by Robert Gerbicz » Mon May 19, 2008 10:19 pm

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.

predicate
New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm
Location: Hyderabad, India

Re: 10218 - Let's Dance !!!

Post by predicate » Tue May 26, 2015 3:09 am

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)

Post Reply

Return to “Volume 102 (10200-10299)”