PROBLEM LINK:
Author: Sergey Nagin
Tester: Mugurel Ionut Andreica
Editorialist: Lalit Kundu
DIFFICULTY:
Easy-Medium
PREREQUISITES:
maths, probability
PROBLEM:
Sereja is playing a game with his friends. There are a total of N players where everyone is numbered from 1 to N. Sereja chose number 1 for himself.
Game consist of M rounds numbered 1 to M. Probability that a player numbered i wins round numbered j is P_{i, j}. After completion of M rounds if someone has won all rounds, he is declared as winner of the game and the game terminates. Otherwise, game starts again from first round. This process completes until there is a winner.
Now Sereja is interested in the probability with what he will ever win the game.
QUICK EXPLANATION:
Define P_{i,\textrm{win}} as the probability of i^{th} player winning a single turn(i.e. a game of M rounds) and P_{\textrm{draw}} as the probability that no players wins a single turn of the game. The probability of Sereja ever winning the game can be define as sum of Geometric Progression series \prod_{i=0}^{\inf} (P_\textrm{draw})^i * P_{1,\textrm{win}} which can be written as \frac{P_{1, \textrm{win}}}{1- P_{\textrm{draw}}}.
where, P_{i,\textrm{win}} = \prod_{j=1}^{M} P_{i,j} and P_\textrm{draw} = 1 - \sum_{i=1}^{N}P_{i,\textrm{win}}.
To take care of precision represent all intermediate values in form of x*10^{-y}, where x \ge 0.
================
EXPLANATION:
================
Itâs a classic probability problem. Letâs denote by Pr_{i,j} where i \ge 0 the probability that i^{th} player will win the game in the j^{th} turn of game(a turn means we have played M rounds). So, the probability of Sereja ever winning the game is \sum_{i=0}^{\inf} Pr_{1,i}. Now, letâs see how we calculate Pr_{1,i} and try to obtain a closed formula because of course, we canât sum till infinity.
So, letâs see how we calculate Pr_{i, 1}. Whatâs the probability that that player i wins the first turn? Winning a game means winning all the M rounds. So probability of winning is product of probabilities of winning all individual rounds because all rounds are independent as said in statement. So, the probability of i^{th} player winning first turn is \prod_{j=1}^{M} P_{i, j}. Letâs call this probability P_{i, \textrm{win}}. Now, interesting thing to note is that this probability of winning a turn for any player i will remain constant always.
Now, letâs see whatâs the probability of Sereja winning the game in second turn. The probability is product of nobody winning in the first turn and Sereja winning in second turn. First letâs see whatâs the probability of nobody winning the first turn. Itâs P_{\textrm{draw}} = 1 - \sum_{i=1}^{N} P_{i, \textrm{win}} because each playerâs winning chances are independent. So, Pr_{1, 2} can be written as P_{\textrm{draw}} * P_{1, \textrm{win}}.
Similarly, probability of Sereja winning in third turn is product of probability of draw in first two turns and Sereja winning the third turn. So, we can write probability of Sereja winning ever as \sum_{i = 0}^{\inf} (P_{\textrm{draw}})^{i} * P_{1, \textrm{win}}. Now, we notice that itâs a Geometric Progression. Sum of \sum_{i=0}^{\inf} r^{i}*a can be written as \frac{a}{1-r} if r \lt 1, which is true in this case since its a probability.
So, our sum of infinite series is \frac{P_{1, \textrm{win}}}{1- P_{\textrm{draw}}} which is basically \frac{P_{1, \textrm{win}}}{\sum_{i=1}^{N}P_{i,\textrm{win}}}. A corner case here would be if P_{1, \textrm{win}} is 0, then our answer is 0.
Now, letâs see what issues can occur in the implementation. Even \textrm{long double} data type can store information upto 18 digits with precision. But, we are going to take product of probabilities for each player, that means for any i, P_{i,\textrm{win}} could be upto 10^{-N}, surely we canât store data with such precision. But, interesting observation would be that our numerator and denominator both could be upto 10^{-N}, so why not take the powers of 10 common? So, while calculating P_{i,\textrm{win}}, at each step we will store the most significant digits of our answer in the form x*10^{-y}. And then while preforming division, weâll subtract the powers of 10 of the denominator.
The following pseudo code will make the method clear:
long double arr[M];
int powers[M];
cin >> n >> m;
for(int i = 0; i < n; i++){
long double pIWin = 1; //probability i'th player wins a turn
int powTen = 0; //store in the form pIWin*10^(-powTen)
for(int j = 0; j < m; j++){
long double pIJ;
cin >> pIJ;
//makes pIJ >= 0
pIJ *= 1e4;
//increasing negative power of ten by 4
powTen += 4;
//multiplying with pIWin
//now since we are multiplying pIWin with numbers > 1
//it might exceed 10^10000 soon
//so we store only 4 most significant digits
pIWin *= pIJ;
if(pIWin>1e4){
pIWin /= 1e4;
powTen -= 4;
}
}
//store both values in an array
//which we use later to calculate denominator and numerator
arr[i] = pIWin;
powers[i] = powTen;
}
//numerator and denominator
long double num=arr[0],den;
for(int i = 0; i < n; i++){
//pIWin is arr[i]*10^(-powers[i])
//whereas our numerator is at index 0
//so, we bring power of numberator down to the denominator
//actual value of pIWin can be written as arr[i]*10^(powers[0]-powers[i])
//if numerator's value is arr[0]
den += arr[i]*pow(10,((ten[0]-ten[i])));
}
if(abs(num)<1e-9)printf("%.9Lf\n",(long double)0);
else printf("%.9Lf\n",(num/den));
COMPLEXITY:
Complexity is O(N*M).
ALTERNATE METHOD FOR PRECISION:
You can convert probabilities to integers and for multiplying them you need to multiply a large number with a small number at each step which can be done quickly using methods such as by using divide and conquer and using a fast multiplication algorithm when combining the results from the two halves of the divide and conquer algorithm - a fast multiplication algorithm could be something like Karatsuba or maybe something based on FFT, but it would be an overkill in my opinion.
