Competitive Programming in Python: What you need to know?

Featured Img Competitive Programming

Hello, there coder! I am pretty sure you are familiar with what Competitive Programming is. But there are some important things one needs to keep in mind when coding in python. These small things can create a huge difference in your code.

Competitive Programming in Python

Let’s study a few of them one after another.

1. Use of Generators

The use of Generators can end up reducing both space and time complexities and are better than using functions. An illustration of a generator function is shown below.

It is also helpful in returning multiple values one after another at the same time.

def FirstGen():
    yield 1
    yield 2
    yield 3
for i in FirstGen():
    print(i,end=" ")

2. Use of Built-in Functions

Using built-in functions and libraries is a better approach than the normal approach. Let us look at a simple program below to have a new list that contains the square of elements of the first list.

To illustrate the difference better, we will calculate the execution time of the programs as well with the help of the time time module.

import time
start_time = time.time()

def get_square(x):
    return x**2
l1 = [i for i in range(100000)]
l2 = []
for i in l1:
    l2.append(get_square(i))
print(len(l2))

print("Time taken by the code: %s seconds."% (time.time() - start_time))

The above approach shows the correct output in 0.06881594657897949 seconds which is no doubt decent enough.

Now let’s try the same program using the in-built function, map and apply the function declared to the list directly.

import time
start_time = time.time()

def get_square(x):
    return x**2
l1 = [i for i in range(100000)]
l2 = list(map(get_square,l1))
print(len(l2))

print("Time taken by the code: %s seconds."% (time.time() - start_time))

Here we saw that the time taken by the same list is 0.048911094665527344 seconds which might seem like a very minor difference but for even larger data this difference can tend to get bigger.

3. Using itertools

The itertools the module can be really helpful to solve some complex problems. For instance, look at the program given below to find all permutations of a list.

import itertools
x = list(itertools.permutations([1,2,3]))
print(x)

The same can be done by creating your own logic and functions but that would be way too complex and will have a worse time complexity.

4. Using map function

Whenever we are required to take input of all the elements of an integer array in one single line separated by white spaces, the map function is the best shot in achieving the same.

l1 = list(map(int,input("Enter all the elements: ").split()))
print(l1)

Using the map function simplifies the complexity of handling multiple values being entered in a single line.

5. String Concatenation

To concatenate multiple strings together we can use two approaches: Adding strings to strings or using join function.

Using join function is recommended as it performs the whole concatenation process in a single line and decreases the complexity if the no of strings is huge.

Let’s look at the first approach: Using the addition operation on strings. The program given below ends up having 0.00498509407043457 seconds as the execution time.

import time
start_time = time.time()
l = [str(i) for i in range(10000)]
st=""
for i in l:
    st+=i
print(len(st))
print("Time taken by the code: %s seconds."% (time.time() - start_time))

Whereas, the second approach: Using the join operation gives a time complexity of just 0.002988576889038086 seconds which is obviously lesser.

import time
start_time = time.time()
l = [str(i) for i in range(10000)]
st = ""
st.join(l)
print(len(st))
print("Time taken by the code: %s seconds."% (time.time() - start_time))

Conclusion

Congratulations! Today you learned some very basic but important things to keep in mind when doing competitive programming in the python programming language.

The tricks can surely help you in increasing the efficiency and accuracy of our solutions to a great extent.

Try out by yourself! Happy coding!