Where to begin?

It has been a common misconception amongst Competitive Programming(hereafter CP) beginners, that Python is a slower language than C++ and they must learn C++ for CP. Some of the rumours I've come across were Python submissions giving TLE but the same algorithm implemented in C++ cleared the test cases. I intend to write this blog to clear these misconceptions and give a beginner-friendly guide for CP using Python. Before diving further it would be helpful if you are fairly aware of Python syntax.

The $$$10^8$$$ thumb rule

Before jumping in to code any question one needs to think of the logic for it. Every question is given a particular time limit within which your code needs to complete execution and your algorithm needs to be efficient to do so. The thumb rule says that for a question with a 1-sec time limit, your algorithm must perform at most $$$10^8$$$ number of operations. If the time complexity goes beyond this you will certainly get TLE.

Taking Input

The first step in your code is to take the input. The function input() returns the input as a string and at times you will need to convert it into a corresponding integer or float. Sometimes you are given arrays as spaced integers.

N = input()                             # returns a string
N = int(input())                        # returns a single integer
                                     
# if the input is given as some spaced integers
A = input().split()                     # returns an array of strings
A = [int(i) for i in input().split()]   # returns an array of integers
C,D = [int(i) for i in input().split()] # returns two integer variables C & D 

Fast Input/Output

When the size of test cases gets larger the normal input/output methods will give TLE irrespective of the fact that your algorithm is correct. This is because the print() statement takes significant time to actually execute.

import sys                        #importing libraries
from time import perf_counter     #importing perf_counter for finding the execution time

t1 = perf_counter()

for i in range(10):   
	print(i)
t2 = perf_counter()               #using print() to print the output


t3 = perf_counter()

for i in range(10):   
	sys.stdout.write(str(i)+"\n")
t4 = perf_counter()               #using sys.stdout.write(str(i)+"\n") to print the output

print("Exec time: print():",t2-t1)
print("Exec time: sys.write:",t4-t3)         #printing the respective execution time

You can clearly see that with sys.stdout.write() the execution time is significantly better.

Now for faster input, I prefer using the following snippet.

ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    import io,os
    input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

If you want to understand what exactly the code is read the section below else you can skip it..

Now while taking the input when input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline integers won't be affected but while reading strings, they will be read as byte strings instead of normal ones.

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
string = input()
print(string)

If the input string is Shaydiesin it will be printed as b'Shaydiesin'. Here you won't be able to access individual characters of the string and you will need to decode it. For this use string.decode("utf-8") to get the normal string.

Example of a question where you need to use Fast I/O

1670B - Dorms War

TLE : 157394407
Accepted : 157396661

You might wonder when to use Fast I/O and when not to? The best way out is to always use Fast I/O but I've tried to limit test and found that it is required when the number of test cases is of the order $$$10^5$$$.

Other important things.

Some ways of writing code in Python are faster than the others in this section I will be mentioning a few preferable ways of writing.

• List comprehension is faster than for loop.

  Performing an operation on an entire list is faster done using list comprehension.

For Loop:

N = 5000
A = [0]*N

for i in range(N):
    A[i]+=1

List Comprehension:

A = [0]*N

A = [i+1 for i in A]

• Effectively making a multidimensional array.

  In order to initialize a 1-D array in python one can simply write A = [0]*6.
  When we print A we get.
  [0, 0, 0, 0, 0, 0]
  Now when we try the same thing in more than one dimension A = [[0]*6]*2
[[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]
  But if we change any element of the 2-D array A A[0][0] = 4
[[4, 0, 0, 0, 0, 0], [4, 0, 0, 0, 0, 0]]
  You will see that both the arrays are changed even though we just changed the first element of the first array. This is because when we create a list using shallow listing all the elements point to the same object. Essentially the elements of the outer array are pointing towards the same list.
  Instead use list comprehension

A=[[0 for i in range(6)] for j in range(2)]       
A[0][0]=4    

[[4, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]]