Chapter 7.2: Problem-Solving Strategies

Knowing algorithms is necessary but not sufficient. You also need to know how to think when facing a problem you've never seen before. This chapter teaches you a systematic approach.

7.2.1 How to Read a Competitive Programming Problem

USACO problems follow a consistent structure. Learn to parse it efficiently.

Problem Structure

1. Story/Setup — a theme (usually cows 🐄). Mostly flavor text — don't get distracted.
2. Task/Objective — the actual question. Read this very carefully.
3. Input format — how to read the data.
4. Output format — exactly what to print.
5. Sample input/output — the examples.
6. Constraints — the most important section for algorithm choice.

Reading Discipline

Step 1: Read the task/objective first. Then read input/output format. Step 2: Read the constraints. These tell you:

• N ≤ 20 → maybe O(2^N) or O(N!)
• N ≤ 1000 → probably O(N²) or O(N² log N)
• N ≤ 10^5 → must be O(N log N) or O(N)
• N ≤ 10^6 → must be O(N) or O(N log N)
• Values up to 10^9 → might need long long
• Values up to 10^18 → definitely long long

Step 3: Work through the sample manually. Verify your understanding.

Step 4: Look for hidden constraints. "All values are distinct." "The graph is a tree." "N is even." These often unlock simpler solutions.

7.2.2 Identifying the Algorithm Type

After reading the problem, ask yourself these questions in order:

Visual: Problem-Solving Flowchart

The flowchart above captures the complete contest workflow. The key step is mapping input constraints to algorithm complexity — use the complexity table below to make that decision quickly.

Visual: Complexity vs Input Size

This reference table tells you immediately whether your chosen algorithm will pass. If N = 10⁵ and you have an O(N²) solution, it will TLE. This table should be your first mental check when designing an approach.

Question 1: Can I brute force it?

• If N ≤ 15, brute force all subsets: O(2^N)
• If N ≤ 8, try all permutations: O(N!)
• Even if brute force is too slow for full credit, it's good for partial credit and for verifying your correct solution

Question 2: Does it involve a grid or graph?

• Grid with shortest path question → BFS
• Grid/graph with connectivity → DFS or Union-Find
• Graph with weighted edges, shortest path → Dijkstra (Gold topic)
• Tree structure → Tree DP or LCA

Question 3: Does it involve sorted data?

• Finding closest elements → Sort + adjacent scan
• Range queries → Binary search or prefix sums
• "Can we achieve value X?" type question → Binary search on answer

Question 4: Does it involve optimal decisions over a sequence?

• "Maximum/minimum cost path" → DP
• "Maximum number of non-overlapping intervals" → Greedy
• "Minimum operations to transform X to Y" → BFS (if small state space) or DP

Question 5: Does it involve counting?

• Counting subsets → Bitmask DP (if small N) or combinatorics
• Counting paths in a DAG → DP
• Frequency of elements → Hash map

The Algorithm Decision Tree

Is N ≤ 20?
├── YES → Try brute force (O(2^N) or O(N!))
└── NO
    Is it a graph/grid problem?
    ├── YES
    │   Is it about shortest path?
    │   ├── YES (unweighted) → BFS
    │   ├── YES (weighted) → Dijkstra (Gold)
    │   └── NO (connectivity) → DFS / Union-Find
    └── NO
        Does sorting help?
        ├── YES → Sort + scan / binary search
        └── NO
            Does it have "overlapping subproblems"?
            ├── YES → Dynamic Programming
            └── NO → Greedy / simulation

7.2.3 Testing with Examples

Always Test the Given Examples First

Before submitting, verify your solution produces exactly the right output for all provided examples.

# Compile
g++ -o sol solution.cpp -std=c++17

# Test with sample input
echo "5
3 1 4 1 5" | ./sol

# Or from file
./sol < sample.in

Create Your Own Test Cases

The provided examples are easy. Create:

1. Minimum case: N=1, N=0, empty input
2. Maximum case: N at max constraint, all values at max
3. All same values: N elements all equal
4. Already sorted / reverse sorted
5. Special structures: Complete graph, path graph, star graph (for graph problems)

Stress Testing

Write a brute-force solution for small N, then compare against your optimized solution on random inputs:

// brute.cpp — simple O(N^3) solution
// sol.cpp — your O(N log N) solution

// stress_test.sh:
for i in {1..1000}; do
    # Generate random test
    python3 gen.py > test.in
    # Run both solutions
    ./brute < test.in > expected.out
    ./sol < test.in > got.out
    # Compare
    if ! diff -q expected.out got.out > /dev/null; then
        echo "MISMATCH on test $i"
        cat test.in
        break
    fi
done
echo "All tests passed!"

Stress testing catches subtle bugs that sample cases miss.

7.2.4 Debugging Tips for C++

Strategy 1: Print Everything

When something's wrong, add cerr statements to trace your program's execution. cerr goes to standard error (separate from standard output):

cerr << "At node " << u << ", dist = " << dist[u] << "\n";
cerr << "Array state: ";
for (int x : arr) cerr << x << " ";
cerr << "\n";

Why cerr not cout? cout goes to standard output where the judge checks your answer. cerr goes to standard error, which the judge usually ignores. So your debug output doesn't pollute your answer.

Strategy 2: Use assert for Invariants

assert(n >= 1 && n <= 100000);   // crashes with a message if condition fails
assert(dist[v] >= 0);            // check BFS invariant

Strategy 3: Check Array Bounds

Common out-of-bounds patterns:

int arr[100];
arr[100] = 5;   // Bug! Valid indices are 0-99

// Use this to detect bounds issues while debugging:
// Compile with -fsanitize=address (AddressSanitizer)
// g++ -fsanitize=address,undefined -o sol sol.cpp

Strategy 4: Rubber Duck Debugging

Explain your code line by line, out loud or in writing. The act of explaining forces you to notice inconsistencies. Many bugs are found this way — not by staring at the screen, but by articulating what each line is supposed to do.

Strategy 5: Reduce the Problem

If your code fails on a large input, manually create the smallest input that still fails. Fix that. Repeat.

Strategy 6: Read Compiler Warnings

g++ -Wall -Wextra -o sol sol.cpp

The -Wall -Wextra flags enable all warnings. Read them! Uninitialized variables, unused variables, signed/unsigned mismatches — all common USACO bugs.

7.2.5 USACO-Specific Debugging

Check Your I/O

The #1 cause of Wrong Answer on correct algorithms: wrong input/output format.

• Did you read the right number of values?
• Are you printing the right number of lines?
• Is there a trailing space or missing newline?

Test Timing

To check if your solution is fast enough:

time ./sol < large_input.in

USACO typically allows 2–4 seconds. If your solution takes 10 seconds locally, it'll time out.

Estimate Complexity First

Before coding, calculate: "My algorithm is O(N²). N = 10^5. That's 10^10 operations. Way too slow."

Rough guide for what runs in 1 second with C++:

• 10^8 simple operations
• 10^7 complex operations (like map lookups)
• 10^5 × 10^3 = 10^8 for nested loops with simple body

7.2.6 From Bronze to Silver Checklist

Use this checklist to evaluate your readiness for Silver:

Algorithms to Know

• Prefix sums (1D and 2D)
• Binary search (including on the answer)
• BFS and DFS on graphs and grids
• Union-Find (DSU)
• Sorting with custom comparators
• Basic DP (1D DP, 2D DP, knapsack)
• STL: map, set, priority_queue, vector, sort

Problem-Solving Skills

• Can identify whether a problem needs BFS vs. DFS vs. DP vs. Greedy
• Can implement BFS from scratch in 10 minutes
• Can implement DSU from scratch in 5 minutes
• Can model grid problems as graphs
• Knows how to binary search on the answer
• Comfortable with 2D arrays and grid traversal

Contest Skills

• Can write a clean template with fast I/O in 30 seconds
• Never forget long long when needed
• Always test with sample cases before submitting
• Can read and understand constraints quickly
• Has practiced at least 20 Bronze problems
• Has solved at least 5 Silver problems (even with hints)

Practice Plan

1. Solve all easily available USACO Bronze problems (2016–2024)
2. For each problem you can't solve in 2 hours: read editorial, implement from scratch
3. After solving 30+ Bronze problems, attempt Silver: start with 2016–2018 Silver
4. Keep a problem log: problem name, techniques used, key insight

7.2.7 Resources

Official

• USACO website: usaco.org — contest archive, editorials
• USACO training: train.usaco.org — old but good structured curriculum

Unofficial

• USACO Guide: usaco.guide — excellent community-written guide, highly recommended
• Codeforces: codeforces.com — more problems and contests
• AtCoder: atcoder.jp — high-quality educational problems

Books

• Competitive Programmer's Handbook by Antti Laaksonen — free PDF, excellent
• Introduction to Algorithms (CLRS) — the bible for theory (heavy reading)

Chapter Summary

📌 Key Takeaways

🧩 "Problem-Solving Mindset" Quick Checklist

❓ FAQ

Q1: What to do when you encounter a completely unfamiliar problem type?

A: ① First write a brute force for small data to get partial credit; ② Draw diagrams, manually compute small examples to find patterns; ③ Try simplifying the problem (if 2D, think about the 1D version first); ④ If still stuck, move to the next problem and come back later.

Q2: How to improve "problem recognition" ability?

A: Deliberate categorized practice. After each problem, record its "tags" (BFS, DP, greedy, binary search, etc.). After enough practice, you'll immediately associate similar constraints and keywords with the right algorithm. The Pattern Cheat Sheet in Chapter 7.1 of this book is a good starting point.

Q3: In a contest, should you write brute force first or go straight to the optimal solution?

A: Write brute force first. Brute force code usually takes only 5 minutes and serves three purposes: ① gets partial credit; ② helps you understand the problem; ③ can be used for stress testing to verify the optimal solution. Even if you're confident in your solution, it's recommended to write brute force first.

Q4: How to use stress testing for efficient debugging?

A: Write three programs: brute.cpp (correct brute force), sol.cpp (your optimized solution), gen.cpp (random data generator). Run them in a loop and compare outputs. When a discrepancy is found, that small test case is your debugging clue. This is the most powerful debugging technique in competitive programming.

🔗 Connections to Other Chapters

• The algorithm decision tree in this chapter covers the core algorithms from all chapters in this book
• Chapter 7.1 covers USACO contest rules and problem categories; this chapter covers "how to solve problems"
• The Bronze-to-Silver Checklist summarizes all knowledge points from Chapters 2.1–6.3
• The Stress Testing technique in this chapter can be applied to Practice Problems in all chapters

The journey from Bronze to Silver is about volume of practice combined with deliberate reflection. After each problem you solve — or fail to solve — ask: "What was the key insight? How do I recognize this type faster next time?"

Good luck, and enjoy the cows. 🐄