CP with Python Essentials

Правка en9, от Shaydiesin, 2022-05-30 14:16:19

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

Fast I/O

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

Теги python, cp in python

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en19 Английский Shaydiesin 2022-06-01 20:58:23 303
en18 Английский Shaydiesin 2022-06-01 13:43:07 142
en17 Английский Shaydiesin 2022-05-31 14:52:34 0 (published)
en16 Английский Shaydiesin 2022-05-31 14:46:56 0 (saved to drafts)
en15 Английский Shaydiesin 2022-05-31 14:09:45 0 (published)
en14 Английский Shaydiesin 2022-05-31 14:09:05 1470 Tiny change: 'ument and st_size to return' -> 'ument and `st_size` to return'
en13 Английский Shaydiesin 2022-05-30 16:13:35 8
en12 Английский Shaydiesin 2022-05-30 16:10:21 1192
en11 Английский Shaydiesin 2022-05-30 15:04:08 55
en10 Английский Shaydiesin 2022-05-30 14:31:20 274 Tiny change: 'r loop.\n--kSKak \n' -> 'r loop.\n- - \n\n'
en9 Английский Shaydiesin 2022-05-30 14:16:19 1 Tiny change: 'he order $t10^5$.\n\n' -> 'he order $10^5$.\n\n'
en8 Английский Shaydiesin 2022-05-30 14:15:51 307 Tiny change: ' Fast I/O\n[problem' -> ' Fast I/O\\\n\n[problem'
en7 Английский Shaydiesin 2022-05-30 13:59:36 671 Tiny change: 'se `stringdecode("ut' -> 'se `string.decode("ut'
en6 Английский Shaydiesin 2022-05-30 13:23:25 311
en5 Английский Shaydiesin 2022-05-30 13:03:43 92
en4 Английский Shaydiesin 2022-05-29 13:20:07 1427 Tiny change: 'n~~~~~\n\n\n\n\n\n\n' -> 'n~~~~~\n\nFast Input/Output\n------------------\n\n\n\n\n'
en3 Английский Shaydiesin 2022-05-29 12:20:15 428
en2 Английский Shaydiesin 2022-05-29 12:11:40 549
en1 Английский Shaydiesin 2022-05-27 17:38:15 60 Initial revision (saved to drafts)