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.

What happened: I got wrong answer for Problem A 979A . As a normal user i checked, rechecked my logic for it. Read editorial also, it matched my logic too. Looked into test case that made it fail.

My Code

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 awoo 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. 
 

More examples

>> 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)