I made a simple solution in Python to solve the problem but it failed on all large testcases. The precision cannot be an issue because I am multiplying all probabilities by 10^4 and converting them to int.
Here is the link to my solution
Please help… I just wasted 2 days thinking my maths was wrong.
Just so you know, we can use decimal module.
My solution: CodeChef, Gist.
I think your code is wrong…
It should be “if sj == 0:” instead of “if ts == 0:”.
Yes I saw one solution using Decimal module. But I still wonder why my solution fails on all testcases. Any ideas ?
I managed to get AC without using decimal module. But scaling up with 100 or 10000 is giving WA for some reason I don’t understand.
Scaling up with 25 however, gave me AC. ~ My Solution
May be scaling up with 100 or above (I don’t know the exact point where this happens) takes the product above long integer range and big integers come into play and somehow this leads to lose of precision.
Anyway, when you need precision in future, always use decimal module.
I will keep that in mind. Thanks for your help.
ts is total sum of probabilities. sj is Sereja’s probability. If ts is 0, sj is already 0. BTW I got AC by changing the multiplier to 25 instead of 10^4
Interestingly, the 25x version fails (gives nan) on even a smooth testcase like this whereas the 10000x version gives the correct answer. So it was the 25x float version which lost the number. Next time, I will make sure to use decimal to keep floats intact.
You are not getting
nan in 10000x version because you are explicitly converting the resulting numbers to ints.
And yeah scaling up with 25 is not correct solution. It’s just a hack.
And depending on the input, you may need to increase precision of Decimal class of decimal module which we didn’t need to… in this question.