Introduction to Competitive Programming

Competitive programming is a buzzword in today’s software industry. It combines two topics: the design of algorithms and the implementation of algorithms. The primary goal of the competitive programming is to prepare a programmer such that his/her logical ability increases and he/she is able to write efficient code for the challenging situations. Here efficient means both time and memory efficient code is expected. Finally, the solutions are graded by testing an implemented algorithm using a set of test cases.

It takes a long time to become a good competitive programmer, but let us begin with Time Complexity of the code and checking the implementation with test cases by taking an example.

Python Time Module:

Python’s standard library is very extensive, and offers a wide range of facilities using built-in modules (written in C) that provide access to system functionality such as file I/O as well as modules written in Python that provide standardized solutions for many problems that occur in everyday programming. One such module is a timer module that provides various time-related functions for time access and conversions. Using time() functions in time module, you can create a way to check the time taken by the respective code block. The function time. time() returns time elapsed in seconds(float) since 00:00:00 hrs January 1, 1970(often referred to as epoch). Another function time_ns() returns the time in units of nanoseconds.

Example: Python Program for testing primality of a number

Let us take a problem to find the time to check primality of an input integer number. The number is prime only when you find number 1 and the number itself as its divisors. Here we are comparing two ways to decide the range of divisors that are checked to decide the primality. The more the number of divisors we take, more is the time complexity. The program prints the time required for execution using both the limits: one with half the number being tested and the other with square root of the number.

An inefficient version of the code tests divisors from 2 to n/2 where n is a number being tested for primality, is given below. Run with the test cases given at the end of this article.

import math     # for sqrt() function
import time     # for measuring time required for primality test
divisor_found=False
n=int(input("Enter a positive integer:"))
start_time=time.time_ns()
# for large primes, using n//2 limit requires more time for deciding # primality as the range of divisors is much larger
divisor_limit1= (n//2+1)
for divisor in range(2, divisor_limit1):
  if n % divisor == 0:
            divisor_found = True
            break
end_time=time.time_ns()
extime=end_time-start_time
if divisor_found: # check on flag
        print(f"{n} is not prime as it has {divisor} as a divisor")
else:
        print(f"{n} is a prime number")
print(f"Time required for primality testing using n/2 limit is {extime} ns")

The output given by my MacBook Pro using PyCharm IDE is

Enter a positive integer:99991

99991 is a prime number
Time required for primality testing using n/2 limit is 6626000 ns

Let us take an efficient version of this logic that check the divisors upto sqrt(n) .

divisor_found=False
n=int(input("Enter a positive integer:"))
start_time=time.time_ns()
# for large primes, using sqrt(n) limit requires less time for 
# deciding primality as the range of divisors is much smaller
divisor_limit2=int(math.sqrt(n)+1)
for divisor in range(2, divisor_limit2):
    if n % divisor == 0:
            divisor_found = True
            break
end_time=time.time_ns()
extime=end_time-start_time
if divisor_found: # check on flag
        print(f"{n} is not prime as it has {divisor} as a divisor")
else:
        print(f"{n} is a prime number")
print(f"Time required for primality testing using sqrt(n) limit is {extime} ns")

The output given in this case is:

Enter a positive integer:99991

99991 is a prime number
Time required for primality testing using sqrt(n) limit is 93000 ns

This code is about 71 times faster than the first logic.

Great achievement indeed ! Now you may try various sample test cases given below and verify yourself.

Sample test cases for prime numbers: {997,9973,99991,999983,9999991,99999989,999999937,5915587277,100529784361,987654321346789}

Sample test cases for non prime numbers:{51,121,19781,3670831,99999987,997210243}

I hope this highlights and clearly explains one important aspect of competitive coding to the beginners. Happy coding !