×

# SEAGM2 - Editorial

Author: Sergey Nagin
Tester: Mugurel Ionut Andreica
Editorialist: Lalit Kundu

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.

# AUTHOR'S, TESTER'S SOLUTIONS:

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

19.8k350498541

 7 I've a less complex solution for this problem: http://www.codechef.com/viewsolution/7413020 I Changed the formula a bit, Now in the solution I don't have to deal much with precision so it will work always :-) answered 13 Jul '15, 15:42 71●3 accept rate: 0% 1 @amaneureka: can you explain your logic? (13 Jul '15, 16:09) ayushj103★ Please explain your solution (13 Jul '15, 16:44) mjbpl5★ 4 Wow! this is a really good solution! He has just played around with the formula and calculated Ai / A1 on the fly without actually calculating the whole Ai first. Ai is the product of numbers in the ith row (probability that ith guy wins). The answer initially is A1 / (A1 + A2 + ... + An). Divide both sides by A1 and you get 1 / (1 + A2/A1 + A3/A1 + ... + An/A1). nice! (13 Jul '15, 20:15) oh. nice soln. he nailed it :) (13 Jul '15, 20:58) ayushj103★ Yeah, @rushilpaul explained it very correctly. Thanks :-) The variable 'waah' takes care of when the probability is zero (13 Jul '15, 21:25)
 3 The test cases were weak ; the following solution gets 100 points : http://www.codechef.com/viewsolution/7474964 All I did was scale all the elements by 25. answered 13 Jul '15, 16:30 53●3 accept rate: 0% 1 ...I HAD TO USE MY OWN bignum LIBRARY IN C AND YOU JUST WALTZ IN AND SCALE THE ELEMENTS BY 25...(so depressed) (13 Jul '15, 17:36) 2 +1 for the variable names. (14 Jul '15, 02:24) ambarpal5★
 1 I used BigInteger in Java, but got WA on the large input set.. Unable to understand why.. Is there a way to look at 1 sample test from large input set ? === Ok I understand my mistake. I share it with you, because it's very stupid and not easy to find. I read the p[i][j] as doubles, then multiply them by 10000, then converting them to Integer. This is were the bug was. Because of the following: if double x=0.0710 then x*10000=709.99999999 and when casting to Int, this gives 709...(!!!) This is a lesson. Never cast a double to an int basically.. answered 13 Jul '15, 15:36 5★beroul 132●3 accept rate: 6%
 1 Got AC with big integer calculation without any fast multiplication optimization. The only trick I used is when you divide big integer on another big integer the only precision you need is first 6 digits after decimal point. So it is enough to divide up to 9th digit and the stop dividing. answered 13 Jul '15, 16:45 3★rotozoom 41●2 accept rate: 0% Your solution is similar to my solution because we both multiplied by scalars instead of using a bignum multiplication algorithm. (I saw your solution here.) (13 Jul '15, 17:52)
 0 i had the same logic...just messed up with the precision thing !!...nice problem though!!! answered 13 Jul '15, 15:28 2★coolsduy 165●9 accept rate: 25%
 0 exactly the same logic.....just precision errors..... Also, the first test case was weak though, even my guess solution which i first applied for finding minimum of every row and printing the minimum of first row passed. This should not have happened.... Still a good question. Came to know about the importance of precision of numbers and how to take care of it. answered 13 Jul '15, 15:43 6★likecs 3.7k●23●80 accept rate: 9%
 0 I used the BigDecimal class in java and got it accepted. Here's the link to my solution http://www.codechef.com/viewsolution/7465863 . answered 13 Jul '15, 15:44 80●5 accept rate: 10% How did your solution pass? It went over the time limit of 3 seconds! (13 Jul '15, 17:47) Time limit for java is not 3 seconds. It is for C/C++, I guess. JAVA is slow. (13 Jul '15, 19:30)
 0 I have used the BigDecimal class in java. Here is the link to my solution. http://www.codechef.com/viewsolution/7465863 answered 13 Jul '15, 15:44 80●5 accept rate: 10%
 0 This problem really pissed me off. I was very confident of my solution but I kept getting WA's. I still don't know the reason though. My maths is the same as author's but my answer may be more precise because I am never rounding off (PYTH). I opened up a discussion for this. It will be helpful if someone provides any guidance. answered 13 Jul '15, 17:08 4★aviaryan 60●1●1●6 accept rate: 25%
 0 I don't understand why the author suggests a "fast multiplication method like Karatsuba or FFT" for multiplying bignums. All of the probabilities can be expressed as scalars from 0 ＜= n ＜= 1000000, so all you ever need to do is multiply by scalars which takes O(s) time where s is the size of the bignum. This is even faster than Karatsuba and FFT because we're not multiplying bignums by bignums. Here's my solution. In this solution, I simply find the product of all of the probabilities by having one bignum called curProduct and repeatedly taking inputs as scalars (long longs) and then multiplying them into curProduct. Then, in the end, I take the first one and multiply it by 1000000 into sereja and add them all up into sum. I then use binary search to divide sereja by sum and output the resulting number with a decimal point. No Karatsuba or FFT necessary! answered 13 Jul '15, 17:44 128●13 accept rate: 16%
 0 @amaneureka Nice idea, but the following test case should not work: 2 10000 0.0001 0.0001 ... (5000 times) 0.9999 0.9999 0.9999 ... (5000 times) 0.9999 0.9999 0.9999 ... (5000 times) 0.0001 0.0001 ... (5000 times) answered 14 Jul '15, 01:47 1 accept rate: 0% @amaneureka: Sorry, I didn't mean to not let you sleep because of my comment. If you have time, could you swap the 3rd and the 4th 'for' loop? The idea of my test case was that (0.0001/0.9999)^5000 would be 0 because of the precision and that multiplying back by (0.9999/0.0001)^5000 cannot change that. (For example http://paste.ideaslabs.com/show/CvvvJDHinq returns 0 and 0 in Java). (14 Jul '15, 12:40)
 0 @spagiarri Here :-) PS: After watching your comment (at 04:00AM) from mobile, Just to prove my code I booted laptop again :P I can give you brief explanation that why it worked, but its 4AM and I'm very tired so, sorry :-) answered 14 Jul '15, 04:14 71●3 accept rate: 0%
 0 Why dies my solution passes the subtask 2 but now 1? In JAVA Link : link text answered 12 Jul '16, 09:05 187●2●9 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,682
×1,672
×1,186
×246
×141
×11

question asked: 29 Jun '15, 20:37

question was seen: 4,506 times

last updated: 12 Jul '16, 09:05