BirdsCounting
SRM 435 · 2009-02-12 · by almelv
SRM 435 · 2009-02-12 · by almelv · Dynamic Programming, Math
Problem Statement
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.
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.
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)
9 3 4 7 Returns: 0.42061467444120504
2)
3 1 5 1 Returns: 0.012345679012345678
3)
13 1 2 0 Returns: 0.0
4)
8 3 3 7 Returns: 0.2582908163265306
Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BirdsCounting with a public method double computeProbability(int birdsNumber, int caughtPerDay, int daysNumber, int birdsMarked) · 82 test cases · 2 s / 256 MB per case