TopCoder problem "BirdsCounting" used in SRM 435 (Division II Level Three)



Problem Statement

    In ecology, there are several ways of estimating the size of a population in a given area. We are interested in estimating the size of a population of birds. To do this, we will use the following procedure.



First, there will be a data collection phase that lasts exactly daysNumber days. Initially, all the birds are unmarked. During each day of data collection, we will catch exactly caughtPerDay birds. At the end of each day, we will examine each of the birds we have caught. If a bird is unmarked, we will mark it. If a bird is already marked, we will leave it alone (and it will remain marked). We will then release all of them back into the wild before the next day begins.



After the data collection phase is complete, we can use the number of unmarked birds caught each day to estimate the size of the population.



To help our fellow ecologists in analyzing the collected data, we must compute the probability that after daysNumber days of data collection, there will be exactly birdsMarked marked birds assuming that there are birdsNumber birds in this area. Assume that the probability of being caught is exactly the same for every bird on every day.
 

Definition

    
Class:BirdsCounting
Method:computeProbability
Parameters:int, int, int, int
Returns:double
Method signature:double computeProbability(int birdsNumber, int caughtPerDay, int daysNumber, int birdsMarked)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9.
 

Constraints

-birdsNumber will be between 1 and 20, inclusive.
-caughtPerDay will be between 1 and birdsNumber, inclusive.
-daysNumber will be between 1 and 5, inclusive.
-birdsMarked will be between 0 and birdsNumber, inclusive.
 

Examples

0)
    
3
1
2
2
Returns: 0.6666666666666666
After the first day, there will be exactly one marked bird. During the second day, there is a 1/3 chance that we will catch this marked bird (which means we will have 1 marked bird after 2 days), and a 2/3 chance that we will catch an unmarked bird (in which case, we will mark it and have 2 marked birds after 2 days).
1)
    
3
1
5
1
Returns: 0.012345679012345678
2)
    
8
3
3
7
Returns: 0.2582908163265306
3)
    
5
3
2
4
Returns: 0.6
4)
    
20
6
5
17
Returns: 0.30035494805367574

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13697&pm=10243

Writer:

almelv

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, Math