Competitive Programming: Think Fast, Code Faster

Competitive Programming: Think Fast, Code Faster

What is Competitive Programming?

Competitive programming is solving algorithmic problems under time and memory constraints. It develops problem-solving skills, teaches data structures and algorithms, and is a global competition platform.

Popular Indian Platforms

• CodeChef: Indian platform, problems in multiple languages, contests monthly
• Codeforces: Russian platform, very popular among Indian programmers
• HackerRank: Interview prep and contests
• HackerEarth: Contests with college hackathons
• ZCO/INOI: Indian National Olympiad in Informatics - school-level competitions
• ICPC: International Collegiate Programming Contest

Time Complexity Analysis

Big O Notation

# Rule of thumb: 10^8 operations per second
# n = 10^6: need O(n log n) or better
# n = 10^4: can afford O(n^2)
# n = 100: can afford O(n^3) or even O(n^4)

# Common complexities
# O(1) - constant
def access_array(arr, index):
    return arr[index]

# O(log n) - logarithmic
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# O(n) - linear
def linear_search(arr, target):
    for num in arr:
        if num == target:
            return True
    return False

# O(n log n) - linearithmic
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# O(n^2) - quadratic
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# O(2^n) - exponential (avoid!)
def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n-1) + fibonacci_naive(n-2)

# Complexity table for different n
import time
print("Time Limit Exceeded (TLE) if time > 1-2 seconds")
print("n=10: O(n^5) = 100,000 ops ✓")
print("n=100: O(n^3) = 1,000,000 ops ✓")
print("n=1,000: O(n^2) = 1,000,000 ops ✓")
print("n=10,000: O(n log n) ≈ 130,000 ops ✓")
print("n=100,000: O(n) = 100,000 ops ✓")
print("n=1,000,000: O(log n) ≈ 20 ops ✓")

Two Pointers Technique

Use two pointers moving towards each other or same direction to solve array problems in O(n).

Example: Two Sum II (Sorted Array)

def two_sum_sorted(arr, target):
    """Find two numbers that sum to target in sorted array"""
    left = 0
    right = len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

# Test
arr = [2, 7, 11, 15]
print(two_sum_sorted(arr, 9))  # [1, 2]

Example: Container With Most Water

def max_area(heights):
    """Find max water area between two bars - O(n)"""
    left = 0
    right = len(heights) - 1
    max_area_val = 0
    
    while left < right:
        width = right - left
        area = width * min(heights[left], heights[right])
        max_area_val = max(max_area_val, area)
        
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    
    return max_area_val

# Test: bars at heights [1,8,6,2,5,4,8,3,7]
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49

Sliding Window Technique

Maintain a window of fixed or variable size, slide it across array/string.

Maximum Sum of Subarray (Fixed Window)

def max_sum_k_subarray(arr, k):
    """Max sum of k consecutive elements - O(n)"""
    if k > len(arr):
        return 0
    
    # Calculate first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide the window
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        max_sum = max(max_sum, window_sum)
    
    return max_sum

# Test
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
print(max_sum_k_subarray(arr, 4))  # 24 (10+2+3+1+8 nope... 4+2+10+2=18? no)
# Actually: 2+3+1+0+20=26? No. 4+2+10+2=18, 2+10+2+3=17, 10+2+3+1=16, 2+3+1+0=6, 3+1+0+20=24 ✓

Longest Substring Without Repeating Characters (Variable Window)

def longest_substring_no_repeat(s):
    """Find longest substring with unique characters - O(n)"""
    char_index = {}
    max_length = 0
    left = 0
    
    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1
        
        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Test
print(longest_substring_no_repeat("abcabcbb"))  # 3 (abc)
print(longest_substring_no_repeat("bbbbb"))     # 1 (b)
print(longest_substring_no_repeat("pwwkew"))    # 3 (wke)

Greedy Algorithm

Make locally optimal choices hoping to find global optimum.

Activity Selection Problem

def activity_selection(activities):
    """Select max non-overlapping activities - O(n log n)"""
    # activities = [(start, end), ...]
    # Sort by end time
    activities.sort(key=lambda x: x[1])
    
    selected = [activities[0]]
    
    for i in range(1, len(activities)):
        # If start time >= last selected end time, no overlap
        if activities[i][0] >= selected[-1][1]:
            selected.append(activities[i])
    
    return selected

# Example: school class schedule
activities = [(9, 10), (9, 11), (10, 11), (11, 12), (10, 13)]
print(activity_selection(activities))  # [(9, 10), (10, 11), (11, 12)]

Fractional Knapsack Problem

def fractional_knapsack(items, capacity):
    """Take items with best value/weight ratio - O(n log n)"""
    # items = [(weight, value), ...]
    # Sort by value/weight ratio (descending)
    items.sort(key=lambda x: x[1] / x[0], reverse=True)
    
    total_value = 0
    remaining_capacity = capacity
    
    for weight, value in items:
        if weight <= remaining_capacity:
            remaining_capacity -= weight
            total_value += value
        else:
            total_value += (remaining_capacity / weight) * value
            break
    
    return total_value

# Example: jewelry heist
items = [(10, 100), (20, 200), (30, 150)]  # (weight, value)
capacity = 30
print(fractional_knapsack(items, capacity))  # 400

Problem-Solving Strategies

1. Understand the problem: Read carefully, identify input/output, constraints
2. Think of examples: Work through small examples by hand
3. Identify pattern: Look for repeating structure, known algorithms
4. Code and test: Implement, test with edge cases
5. Optimize: Improve time/space complexity if needed

Example Problem Analysis

# Problem: Given array, find element that appears > n/3 times
# Constraints: n <= 10^5, time limit: 1 second

# Approach 1: Brute force - O(n^2) ✗ Too slow
def find_majority_slow(arr):
    for num in arr:
        count = arr.count(num)
        if count > len(arr) // 3:
            return num

# Approach 2: Hash map - O(n) space, O(n) time ✓ Good
def find_majority_hash(arr):
    count = {}
    for num in arr:
        count[num] = count.get(num, 0) + 1
    
    for num, cnt in count.items():
        if cnt > len(arr) // 3:
            return num

# Approach 3: Boyer-Moore voting - O(n) time, O(1) space ✓ Optimal
def find_majority_voting(arr):
    candidate1, candidate2 = None, None
    count1, count2 = 0, 0
    
    for num in arr:
        if num == candidate1:
            count1 += 1
        elif num == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1, count1 = num, 1
        elif count2 == 0:
            candidate2, count2 = num, 1
        else:
            count1 -= 1
            count2 -= 1
    
    return candidate1 if arr.count(candidate1) > len(arr) // 3 else candidate2

Common Patterns in Competitive Programming

India Context: Competitive Programming Scene

CodeChef

Indian platform founded in 2009. Hosts monthly contests with problems for all skill levels. Large Indian community, prizes for top performers.

ZCO/INOI (Zonal Computing Olympiad / Indian National Olympiad in Informatics)

School-level competition in India. Gateway to IOI (International Olympiad in Informatics). Three stages: ZCO → INOI → IOI.

ICPC in India

Asia-Bangalore, Asia-Kolkata, Asia-Chennai regions host ICPC. Indian teams regularly qualify for World Finals.

Practice Problems (CodeChef Style)

1. FLOW008: Find average of n numbers (warm-up)
2. CHFBARN: Cow barn painting (greedy + simulation)
3. STICKS: Minimize total cutting (greedy algorithm)
4. MAXFUN: Maximize function value (observation + formula)
5. LUNCHTIME: Find minimum and second minimum

Key Takeaways

• Time complexity is crucial - 10^8 operations per second is typical
• Two pointers and sliding window solve many array/string problems in O(n)
• Greedy works when locally optimal choice leads to global optimum
• Always code with edge cases and constraints in mind
• Practice on CodeChef, Codeforces, HackerEarth regularly
• Learn standard algorithms: BFS, DFS, binary search, DP, greedy
• Read problem carefully - many WA (wrong answers) from misunderstanding
• Contest tips: Code fast, test thoroughly, optimize if needed, then submit