Problem Solving Strategies and Competitive Programming

From knowing tools to choosing tools

You have now covered the core crash-course toolkit:

• Introduction to Data Structures: lists, stacks, queues, and container behavior
• Algorithm Basics and Complexity Analysis: Big O and growth tradeoffs
• Recursive Algorithms and Backtracking: search trees and pruning
• Trees and Graphs: DFS, BFS, and representations
• Dynamic Programming Essentials: state, transitions, memoization, tabulation
• Greedy Algorithms: local choices and correctness intuition
• Heaps and Hash Tables: fast lookup and priority ordering
• Graph Algorithms: shortest paths and connectivity

This final lesson is about the skill that ties everything together: when you see a new problem, how do you decide what to try first?

Competitive programming is not only about typing fast. It is about quickly recognizing patterns, choosing constraints-friendly approaches, testing edge cases, and learning from misses.

A repeatable 6-step loop

When a problem feels unfamiliar, do not jump straight into code. Use this loop:

1. Restate the problem in your own words.
2. List examples including tiny and weird cases.
3. Read constraints and estimate acceptable Big O.
4. Match patterns from the toolkit.
5. Write the invariant: what must stay true as your algorithm runs?
6. Code, test, revise.

A beginner mistake is treating every problem as unique. Most easy and medium problems are combinations of familiar patterns.

Problem statement
      ↓
Examples + constraints
      ↓
Pattern guess
      ↓
Algorithm sketch
      ↓
Code + tests
      ↓
Review in 2 days

You are given an array of integers and need to find whether any two numbers add up to a target. The input can contain up to 100,000 numbers.

What is usually the best first pattern to consider?

Ask better questions

Pattern recognition improves when you ask targeted questions instead of staring at the statement.

If the input is an array or string

Ask:

• Need pairs or complements? → hash table / set
• Need contiguous window? → sliding window / prefix sums
• Need sorted order? → two pointers / binary search
• Need top K or repeated minimum? → heap

If the input is choices or paths

Ask:

• Need all valid combinations? → backtracking
• Need best value from overlapping subproblems? → DP
• Can a local best choice be proven safe? → greedy

If the input is relationships

Ask:

• Unweighted shortest path? → BFS
• Weighted shortest path with nonnegative weights? → Dijkstra
• Groups or reachability? → DFS/BFS/Union-Find idea

This is not a law. It is a starting map.

Let input size reject bad ideas

Before coding, translate constraints into a rough time budget.

Common competitive-programming intuition:

• n <= 20: exponential/backtracking may be possible
• n <= 1,000: O(n²) may pass
• n <= 100,000: usually aim for O(n log n) or O(n)
• n >= 1,000,000: likely O(n), maybe with careful memory use

Here is a tiny helper that demonstrates how constraints guide strategy selection. It is not a real judge rule, but it trains the habit.

```python
def suggest_complexities(n):
    if n <= 20:
        return ['O(2^n) backtracking may be okay', 'O(n!) only for very tiny n']
    if n <= 1_000:
        return ['O(n^2) may be okay', 'O(n log n) is safer']
    if n <= 100_000:
        return ['O(n log n) is usually okay', 'O(n) is excellent']
    return ['Aim for O(n)', 'Watch memory and constant factors']

for n in [12, 800, 50_000, 2_000_000]:
    print(f'n = {n}:')
    for idea in suggest_complexities(n):
        print('  -', idea)
```

Fill in the blank:

If a problem has n = 100,000, an O(n²) solution usually means about 10,000,000,000 pair checks, so you should first look for something closer to ____ or O(n).

Keep coding friction low

In competitive programming, you want a simple structure:

1. Parse input.
2. Solve with a focused function.
3. Print exactly what the problem asks.

Even outside contests, this habit helps. It separates problem logic from input/output mechanics.

Below is a standalone example using the classic complement/hash-set pattern from earlier.

```python
import sys
import io

# Demo input:
# n target
# array of n integers
sys.stdin = io.StringIO('5 9\n2 7 11 15 1\n')

def has_two_sum(nums, target):
    seen = set()
    for x in nums:
        if target - x in seen:
            return True
        seen.add(x)
    return False

def solve():
    n, target = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))
    print('YES' if has_two_sum(nums, target) else 'NO')

solve()
```

True or false?

If a greedy algorithm passes the sample tests, then it is safe to assume the greedy choice is correct.

Test like a problem setter

Good competitors do not only test the happy path. They actively try to break their code.

Use edge-case categories:

• Empty or smallest valid input
• One element
• Duplicates
• Already sorted / reverse sorted
• Negative numbers if allowed
• Large values near limits
• Cases where no answer exists

Here is a small test harness for binary search. Notice how each test protects one assumption.

```python
def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

tests = [
    ([], 3, -1),
    ([5], 5, 0),
    ([5], 2, -1),
    ([1, 2, 3, 4, 5], 4, 3),
    ([1, 2, 3, 4, 5], 6, -1),
    ([-10, -3, 0, 7], -3, 1),
]

for nums, target, expected in tests:
    actual = binary_search(nums, target)
    print(nums, target, '=>', actual, 'PASS' if actual == expected else 'FAIL')
```

Your crash-course retention system

This course was designed around revisiting problems every 2 days. That is not busywork — it is how patterns become automatic.

Day 0: Learn

Solve with notes. It is okay to look at hints after a real attempt.

Day 2: Re-code

Re-solve from memory. Focus on the template and key invariant.

Day 4: Vary

Change one condition:

• array becomes sorted
• graph becomes weighted
• return count instead of boolean
• optimize space

Day 7+: Mix

Do random problems so the title does not reveal the pattern.

Your goal is not to memorize every answer. Your goal is to build fast recognition: constraints → pattern → invariant → implementation.

A 45-minute practice routine

Use this routine for your next month of practice:

1. 5 minutes: read, restate, list constraints.
2. 10 minutes: try examples and choose a pattern.
3. 20 minutes: implement.
4. 5 minutes: test edge cases.
5. 5 minutes: write a short review note.

Your review note can be simple:

Problem:
Pattern:
Key invariant:
Mistake I made:
Revisit date:

For a beginner Python learner aiming to get proficient, this loop matters more than speed at first. Speed comes from repeated clean reps.

You now have the full crash-course toolkit. Keep rotating through arrays, recursion, graphs, DP, greedy, heaps, hashes, and shortest paths — and revisit the same problems every 2 days until the patterns feel natural.