TopCoder problem "NearBirthdays" used in TCO05 Finals (Division I Level Two)



Problem Statement

    

If more than 23 people are selected at random, the chance that two of them have birthdays on the same day is more than 50%. While this may sound counterintuitive, it is fairly easy to verify that this indeed is the case. Furthermore, only 14 people are needed for there to be more than a 50% chance that at least two of them have birthdays within one day of each other.

Create a class NearBirthdays containing the method probability which calculates the probability that at least two people among noPeople have birthdays within withinDays days (inclusive) of each other. The method should take as input an int noPeople, an int withinDays, and an int daysInAYear, the number of days in a year, and return the probability as a double. Assume that each day in a year is equally likely to be a birthday for someone.

 

Definition

    
Class:NearBirthdays
Method:probability
Parameters:int, int, int
Returns:double
Method signature:double probability(int noPeople, int withinDays, int daysInAYear)
(be sure your method is public)
    
 

Notes

-The last day of a year is within one day of the first day of a year.
-A solution will be judged correct if the absolute error is less than 1e-9.
 

Constraints

-noPeople will be between 2 and 100, inclusive.
-withinDays will be between 0 and 100, inclusive.
-daysInAYear will be between 100 and 1000, inclusive.
 

Examples

0)
    
2
99
200
Returns: 0.995
If the first person's birthday is on day 1 in the 200 day long year, the only time the second person's birthday isn't within 99 days is if he has a birthday on day 101. Hence the probability that both persons have birthdays within 99 days of each other is 199/200 = 0.995.
1)
    
30
0
365
Returns: 0.7063162427192686
This is a typical school class version: in a school class with 30 people, the likelihood that two of them are born on the same day is roughly 70%.
2)
    
6
6
500
Returns: 0.33373900738431983

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4786

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8096&pm=4786

Writer:

Yarin

Testers:

PabloGilberto , lbackstrom , Olexiy

Problem categories:

Dynamic Programming, Math