PROBLEM LINK :
Author : Asim Krishna Prasad
Tester : Manish Kumar Sinha
DIFFICULTY :
EASY - MEDIUM
PREREQUISITES :
Probability, Dynamic Programming, Maths.
PROBLEM :
Given total number of Pokemons, number of distinct Pokemons Asya can make happy on a single day and number of days for which Asya visits Pokeworld, you are asked to calculate the probability of exactly Q number of distinct Pokemons being happy after D days.
Note that Asya can meet the same Pokemon on different days
EXPLANATION :
Each test case can be modeled in a dynamic programming problem. The states of DP would be, Day and DistinctPokemonsMadeHappySoFar.
The base case would be, when we reach the Dth Day, we need to check if we have DistinctPokemonsMadeHappySoFar equal to given Q.
If it is true, probability is 1.0 or else 0.0.
Tricky part is the transition from a state as Asya can meet the same Pokemon on different days.
Let us say we are on state (Day, DistinctPokemonsMadeHappySoFar). From this state what are all the possible sates we can jump to?
On this state, we can divide the total number of Pokemons into two sets, DistinctPokemonsMadeHappySoFar and PokemonsNotHAppySoFar.
Now we have to choose exactly A number of Pokemons from these two sets (combined). What we can do is, take zero Pokemons from 1st set and remaining from 2nd set or take 1 Pokemon from 1st set and remaining from 2nd set and so on. The probability for each of these selections gets added up.
What is the probability of each selection?
Well, if our recurrence function is rec(Day, DistinctPokemonsMadeHappySoFar), then :
(
C[DistinctPokemonsMadeHappySoFar][A - i]
* C[P - DistinctPokemonsMadeHappySoFar][i]
* rec(Days + 1, DistinctPokemonsMadeHappySoFar + i)
) / C[P][A]
where i is the number of new Pokemons Asya meets on this day, and i ranges from 0 to A inclusive.
We can pre - process the C[][] matrix.
Complexity of this solution is O(D * P * A) for every test case, that is : 31250 iterations per test case.
Since there can be 100 test cases, so 31250 x 100 = 3.125 x 10 6 which is acceptable.