Hello Codeforces community!!
This is my first post on codeforces. I am not a regular writer who would post ideas or things because the things i used to find out seemed trivial(This post may seem trivial to many of you :D) to me earlier. But not until 2 days ago when i encountered a kind of mistake in my code. I hope this post help other python3 users or those trying to make a shift to python3.
n = int(input()) if n != 0: if (n+1)%2: print(n+1) else: print(int((n+1)/2)) else: print(0)
Seems the logic is correct so, why it is failing for test case 11. Researched a lot on topics i didn't understood before. Thanks to PikMike and qrfkickit for pointing out the possible source( precision loss while division ). Here is what i found out:
Yeah, it does lose precision when dividing in float numbers. But "how" and "why" questions made me curious to read the python3 docs in detail.
I read the python3 documentation on floating point. I have tried to list down concepts understood on floats and division in python3 point by point after reading from various sources as listed below:
- First of all, '/' is floating point division in python3 by default. So, when we use '/' for division . The numerator n in n/d is converted to floating point number. And, the floating point number are represented using scientific notation( a*10^b ) for representing very small and big float numbers. The a are significant digits and b is power of exponent. But, the scientific notation can represent only 15 significant digits(
sys.float_info.dig) for a. So, here is the catch . The float numbers having significant digits greater than 15 digits will lose some precision while represented as float numbers.
Let me try to show that using an example. I will add int with float.
int + float = float . So, i will try to push the limits of floating point arithmetic.
>> 10**15 + 1.0 1000000000000001.0 # As significant digits are 15 . Result is correct. It doesn't lose precision >> 10**16 + 1.0 1e+16 # 10000000000000000 # As significant digits are 16 (>15). Result is incorrect . Loses precision.
>> 2**53 9007199254740992 >> 2**53 + 1.0 9007199254740992.0
Thus we can see that it is not safe to represent integers as float .
Now, let's talk about easy way to tackle this kind of problem.
- '//' integer division comes to rescue. Integer division in python3 can be handled by builtin operand '//' . Also, the integers in python3 doesn't have a limit. So, this is the safe approach as compared to float or fractional, decimal module.
Now coming to test case 11 for problem 979A-38 .
Input: n = 822981260158260519 Now , (n+1)/2 would first convert n+1 as float But 822981260158260519 + 1 converted to float is 8.229812601582605e+17.
Let's check in interpreter.
>> 822981260158260519 + 1 822981260158260520 # Whereas >> 822981260158260519 + 1.0 8.229812601582605e+17 # we can see the digits '20' are lost while representing the number as float # Converting it to int >> int(8.229812601582605e+17) 822981260158260480 >> int((822981260158260519 + 1)/2) 411490630079130240 >> (822981260158260519 + 1) //2 411490630079130260
Summary: Use '//' integer division for these kind of problem. '/' may work fine with numbers having significant digits less than 16.
>> import sys >> sys.float_info sys.float_info(max=1.7976931348623157e+308, max_exp=1024, max_10_exp=308, min=2.2250738585072014e-308, min_exp=-1021, min_10_exp=-307, dig=15, mant_dig=53, epsilon=2.220446049250313e-16, radix=2, rounds=1)