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

http://www.codechef.com/viewsolution/7444346

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.

1 Like

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.

1 Like

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.