"Talk is cheap. Show me the code"
- Linus Torvalds
Competitive programming has two main components:
-
Design
This requires problem-solving skills and involves mathematical thinking. The designed algorithm has to be correct and efficient. Theoretical knowledge of algorithms is important as a solution is typically a combination of well-known techniques and new insights.
-
Implementation
This requires good programming skills. Just knowing the idea of the solution is not enough; the implementation has to be precise. Typically, time is of the essence and writing the code should not take too long.
Competitive programming has many benefits:
- Participating in competitions enhances problem-solving skills.
- It prepares you well for technical interviews.
- Not only will you learn about the fundamentals in algorithm design, you will also be familiar with their implementations.
- You can make new friends when collaborating in a team of programmers
- It is a fun sport!
The time complexity of an algorithm estimates how much time the algorithm will use for some input. The efficiency of algorithms is important in competitive programming.
Generally, it is easy to design an algorithm that solves the problem slowly but it's challenging to write a fast algorithm.
By calculating the time complexity, we can check whether our algorithm is fast enough without actually implementing it.
The time complexity is often denoted in Big O notation.
A program would have a time complexity of O(...) where the 3 dots represent some function.
Usually, the variable n denotes the input size.
For example, if the input is a list of numbers, n will be the length of the list.
The following table shows some complexity classes in decreasing order of speed/efficiency:
| Complexity | Description |
|---|---|
O(1) |
constant |
O(log n) |
logarithmic |
O(n) |
linear |
O(n log n) |
linearithmic |
O(n²) |
quadratic |
O(n³) |
cubic |
O(2ⁿ) |
exponential |
O(n!) |
factorial |
Most competitive programming websites that host competitions allow 10⁸ operations per second, while a few still allow 10⁷ operations.
| Input Size | Required Time Complexity |
|---|---|
| n ≤ 10 | O(n!) |
| n ≤ 20 | O(2ⁿ) |
| n ≤ 500 | O(n³) |
| n ≤ 5000 | O(n²) |
| n ≤ 10⁶ | O(n log n) |
| n ≤ 10⁸ | O(n) |
| n is large | O(1) or O(log n) |
Let us do a few examples.
Read the problem statement.
class Solution:
def climbStairs(self, n: int) -> int:
f0, f1 = 0, 1
for i in range(n):
f2 = f0 + f1
f0 = f1
f1 = f2
return f2Read the problem statement.
This is a brute force approach
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if (nums[i] + nums[j] == target):
return [i, j]
This solution sorts the list first
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
nums[i] = [nums[i], i]
nums.sort()
low = 0
high = len(nums) - 1
while low < high:
sum = nums[low][0] + nums[high][0]
if sum == target:
return [nums[low][1], nums[high][1]]
elif sum < target:
low += 1
else:
high -= 1This solution uses a dictionary
def twoSum(self, nums: List[int], target: int) -> List[int]:
map = dict()
for i in range(len(nums)):
complement = target - nums[i]
if complement in map:
return [i, map[complement]]
else:
map[nums[i]] = i3Sum is a variation to this problem.
Read the problem statement.
This approach first sorts the list
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
return nums[len(nums) // 2]This approach uses a dictionary.
class Solution:
def majorityElement(self, nums: List[int]) -> int:
map = dict()
for num in nums:
map[num] = map.get(num, 0) + 1
if map[num] > len(nums) / 2:
return numThis approach is based on the Boyer-Moore Algorithm
def majorityElement(self, nums: List[int]) -> int:
counter = 0
for num in nums:
if counter == 0:
m = num
if m == num:
counter += 1
else:
counter -= 1
return m
Majority Element II is a variation to this problem.
Read the problem statement.
def lengthOfLongestSubstring(self, s: str) -> int:
map = dict()
length = low = high = 0
for i in range(len(s)):
char = s[i]
if char in map:
low = max(map[char] + 1, low)
map[char] = i
length = max(high - low + 1, length)
high += 1
return length
There are plenty of platforms for you to practice:
- ACM CP is a SIG ( Special Interest Group ) where student members of ACM who share interests in algorithms and competitive programming come together on a regular basis to meet, discuss and solve problems together.
- It builds on top of what you have just learnt in the coding bootcamp.
- SIG Sessions are held during the even semester of the academic year.
- Visit the official ACM CP page on our website here.
- You can find resources from previous sessions along with member showcases.
We covered:
