Day 60: Competitive Programming Techniques and Wrap-up#

Welcome to the final day of our 60 Days of Coding Algorithm Challenge! Today, we’ll cover some key competitive programming techniques and wrap up our journey through algorithms and data structures.

Competitive Programming Techniques#

1. Fast I/O#

For competitive programming, fast input/output is crucial. In Python, you can use:

1import sys
2input = sys.stdin.readline
3
4# For faster output
5from io import StringIO
6import sys
7out = StringIO()
8sys.stdout = out

2. Modular Arithmetic#

Useful for dealing with large numbers:

1MOD = 10**9 + 7
2
3def mod_add(a, b):
4    return (a + b) % MOD
5
6def mod_mult(a, b):
7    return (a * b) % MOD

3. Binary Search#

Quick way to search in sorted arrays or find optimal values:

 1def binary_search(arr, target):
 2    left, right = 0, len(arr) - 1
 3    while left <= right:
 4        mid = (left + right) // 2
 5        if arr[mid] == target:
 6            return mid
 7        elif arr[mid] < target:
 8            left = mid + 1
 9        else:
10            right = mid - 1
11    return -1

4. Two Pointers Technique#

Useful for array problems:

 1def two_sum(arr, target):
 2    left, right = 0, len(arr) - 1
 3    while left < right:
 4        current_sum = arr[left] + arr[right]
 5        if current_sum == target:
 6            return [left, right]
 7        elif current_sum < target:
 8            left += 1
 9        else:
10            right -= 1
11    return []

5. Prefix Sum#

Efficient for range sum queries:

1def prefix_sum(arr):
2    prefix = [0] * (len(arr) + 1)
3    for i in range(1, len(prefix)):
4        prefix[i] = prefix[i-1] + arr[i-1]
5    return prefix
6
7def range_sum(prefix, left, right):
8    return prefix[right+1] - prefix[left]

Wrap-up#

Over the past 60 days, we’ve covered a wide range of algorithms and data structures:

1. Basic data structures (Arrays, Linked Lists, Stacks, Queues)
2. Advanced data structures (Trees, Heaps, Graphs)
3. Sorting and searching algorithms
4. Dynamic Programming
5. Greedy Algorithms
6. Graph Algorithms
7. String Algorithms
8. Bit Manipulation

Key takeaways:

• Understanding the underlying principles of algorithms is crucial
• Choosing the right data structure can significantly impact performance
• Practice and implementation are key to mastering algorithms
• Time and space complexity analysis helps in comparing algorithms

Next Steps#

1. Continue practicing on platforms like LeetCode, HackerRank, Codeforces
2. Participate in coding contests
3. Implement data structures and algorithms from scratch
4. Explore more advanced topics like advanced graph algorithms, computational geometry
5. Apply algorithmic thinking to real-world problems

Summary#

Congratulations on completing the 60 Days of Coding Algorithm Challenge! You’ve built a strong foundation in algorithms and data structures. Remember, this is just the beginning of your journey. Keep practicing, keep learning, and keep coding!

Thank you for joining us on this adventure. Happy coding!

Exercise#

A classic contest warm-up that combines prefix sums and hashing: given an integer array and a target k, count how many contiguous subarrays sum to exactly k. Aim for a single linear pass.

Solution#

 1# Count contiguous subarrays that sum to k using prefix sums plus a hash map.
 2# Key idea: a subarray (i, j] sums to k when prefix[j] - prefix[i] == k,
 3# so for each running prefix we look up how many earlier prefixes equal
 4# (prefix - k).
 5def subarrays_with_sum(nums, k):
 6    count = 0
 7    running = 0
 8    seen = {0: 1}  # One empty prefix of sum 0 before we start.
 9    for x in nums:
10        running += x
11        # Every earlier prefix equal to running - k closes a valid subarray.
12        count += seen.get(running - k, 0)
13        seen[running] = seen.get(running, 0) + 1
14    return count
15
16print(subarrays_with_sum([1, 1, 1], 2))        # 2
17print(subarrays_with_sum([1, 2, 3], 3))        # 2
18print(subarrays_with_sum([3, 4, 7, 2, -3, 1, 4, 2], 7))  # 4