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
from time import perf_counter
t1 = perf_counter()
for i in range(10): #10^5
print(i)
t2 = perf_counter()
t3 = perf_counter()
for i in range(10): #10^5
sys.stdout.write(str(i)+"\n")
t4 = perf_counter()
print("Execution time for print():",t2-t1)
print("Execution time for sys.write:",t4-t3)
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
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$$$.
