Complexity & Problem Solving

Before you write a single line of code, you need to understand the problem and figure out what approach will work. This chapter teaches you how to think about problems systematically.

Reading Problem Statements

Every problem has the same structure:

1. Input format: what data you receive and how
2. Output format: what you need to produce
3. Constraints: the limits on input size (this determines your time complexity)
4. Examples: sample inputs and outputs with explanations

The Constraints Tell You Everything

Complexity Analysis

Time complexity measures how the number of operations grows with input size.

Common Complexities

Analyzing Nested Loops

// O(n)
for (int i = 0; i < n; i++) {
    // constant work
}

// O(n²)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // constant work
    }
}

// O(n log n)
for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j *= 2) {
        // j doubles each iteration → log n iterations
    }
}

Amortized Analysis

Sometimes individual operations are expensive, but the average is cheap:

• vector::push_back is O(1) amortized (occasionally O(n) when resizing)
• unordered_map::insert is O(1) average (O(n) worst case with bad hashing)

Brute Force

When in doubt, start with brute force. It works for small constraints and helps you understand the problem:

// Check all pairs — O(n²)
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (a[i] + a[j] == target) count++;
    }
}

Brute force is also useful for:

• Generating test cases
• Verifying smarter solutions
• Getting partial credit on hard problems

Observation Finding

Many problems require you to notice a pattern:

1. Try small examples by hand — look for patterns
2. Draw pictures — geometry and graph problems become clearer visually
3. Work backwards — start from the answer
4. Consider special cases — what if n = 1? What if all elements are equal?

// Problem: given n, find maximum k such that 1+2+...+k <= n
// Observation: 1+2+...+k = k(k+1)/2
// So k ≈ sqrt(2n)
int k = (int)(sqrt(2 * n));
while (k * (k + 1) / 2 > n) k--;

Edge-Case Handling

Before submitting, consider:

• n = 0 or n = 1: does your code handle empty/single-element cases?
• Negative numbers: does your algorithm assume positive values?
• All elements equal: does your sort/comparison work?
• Maximum values: does your answer type (int vs long long) suffice?
• Zero: division by zero, modulo zero

Debugging Techniques

1. Print intermediate values: add debug prints to trace execution
2. Use a checker: brute force your solution on random small inputs
3. Binary search for the bug: comment out half the code, narrow down the problem
4. Read the problem again: you probably misunderstood something

Debug Macro (Contest Shortcuts)

#ifdef LOCAL
    cerr << "DEBUG: " << variable << "\n";
#endif

Stress Testing

Generate random inputs and compare your fast solution against brute force:

mt19937 rng(42);

void solve() {
    int n = uniform_int_distribution<int>(1, 20)(rng);
    vector<int> a(n);
    for (int &x : a) x = uniform_int_distribution<int>(1, 100)(rng);
    
    int ans1 = bruteForce(a);
    int ans2 = smartSolution(a);
    
    if (ans1 != ans2) {
        cerr << "MISMATCH!\n";
        // print input and both answers
    }
}

Summary

• Read constraints first — they determine your required time complexity
• Start with brute force, then optimize
• Look for patterns by trying small examples
• Handle edge cases: n=0, negatives, max values
• Stress test: compare fast solution against brute force on random inputs