How to Solve Problems

Quick Revisit

• USE WHEN: Starting any problem -- follow the process before writing code
• INVARIANT: Read -> Model -> Estimate -> Edge cases -> Code -> Verify (never skip steps under pressure)
• TIME: O(5 min) pre-coding process | SPACE: O(1) mental checklist
• CLASSIC BUG: Jumping to code before enumerating edge cases (n=0, n=1, all-same, max values)
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

META-01 | The thinking framework that connects reading a problem statement to writing correct code -- the process skills that separate a 1100 from an 1800 coder.

Difficulty: [Beginner] | Prerequisites: Basic C++ fluency, familiarity with time complexity notation | CF Rating Range: 1100-1500 (foundations used at every level)

---

Contents

• Intuition
• Anatomy of a CP Problem
• Constraint-to-Algorithm Selection
• Edge Case Enumeration Before Coding
• Before You Code—Checklist
• Loop Invariants as a Correctness Tool
• What to Do When Stuck
• Greedy Correctness—The Exchange Argument
• Brute Force as an Explicit Strategy
• When NOT to Use This Framework
• Contest Cheat Sheet
• Common Mistakes and Debugging
  • Debug This!
  • Rating Progression
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

Most competitive programmers spend their first year trying to memorize more algorithms. The ones who break through faster learn something different: the constraint block at the top of the problem statement is already telling you which algorithm to use. Read N <= ... and the search space collapses before you've even understood the problem. The constraints are the solution—everything else is execution.

When Everything Goes Wrong on Problem A

You open a Codeforces round. Problem A looks easy. Something about counting pairs. You read the statement once, start typing immediately. Two minutes later you submit.

Wrong Answer on test 3.

You re-read the problem. Oh -- "print YES or NO" and you printed "Yes". Fix it, resubmit.

Wrong Answer on test 5.

You stare at the sample. Wait -- the problem says $1$-indexed but you read input into a $0$-indexed array. Fix it, resubmit.

Wrong Answer on test 12.

Panic. You add random +1s and -1s. Resubmit. Wrong again. You open the editorial after the contest and realize: $n=1$ is a special case that your loop doesn't handle. The fix was one if statement.

Thirty minutes and four wrong submissions on an "easy" problem. Not because you didn't know the algorithm—you did. Not because you can't code—you can. The culprit was the process before coding, or rather the complete absence of one.

This happens to everyone. It happens less often to people who follow a system.

The Core Realization

The difference between a 1100 and an 1800 coder isn't knowing more algorithms -- it's having a systematic process: read -> model -> estimate -> enumerate edge cases -> code -> verify.

Think of a pilot's preflight checklist. Pilots don't skip engine checks because they've flown a thousand times—they follow the checklist because confidence under time pressure is exactly when critical steps get dropped. Your pre-coding routine is the same idea: a fixed sequence of mental checks that surface bugs before they become Wrong Answers.

Where the analogy stops: a pilot's checklist is identical every flight. Your process adapts to the problem, but the categories of things to check stay constant. And unlike a pilot, your "crash" costs only rating points—so use the checklist aggressively.

The Problem-Solving Flowchart

Here is the full process as a flowchart. Every competitive programmer who doesn't flame out on Problem A follows some version of this—consciously or not:

  +---------------------+
  |   READ the problem   |
  |  (twice, slowly)     |
  +----------+----------+
             |
             v
  +---------------------+
  | EXTRACT constraints  |
  | n, m, t, value range |
  +----------+----------+
             |
             v
  +---------------------+
  | WORK examples by     |
  | hand (pen + paper)   |
  +----------+----------+
             |
             v
  +---------------------+      +---------------------+
  | ESTIMATE: what O(?)  +----->| Constraint table     |
  | complexity fits?     |      | (see below)          |
  +----------+----------+      +---------------------+
             |
             v
  +---------------------+
  | CHOOSE algorithm /   |
  | approach             |
  +----------+----------+
             |
             v
  +---------------------+
  | LIST edge cases      |
  | (checklist below)    |
  +----------+----------+
             |
             v
  +---------------------+
  | CODE the solution    |
  +----------+----------+
             |
             v
  +---------------------+      no     +------------------+
  | TEST on samples +   +------------>| DEBUG: check edge |
  | edge cases -- pass?  |             | cases, invariants |
  +----------+----------+             +--------+---------+
             | yes                              |
             v                                  |
  +---------------------+                      |
  |       SUBMIT         |<---------------------+
  +---------------------+

The steps before "CODE" take 5-10 minutes and save 20-40 minutes of debugging. That is the best return on investment in competitive programming.

The Underlying Rule

+-------------------------------------------------------------------+
| RULE: Never write code until you can state, in one sentence,      |
| what your algorithm does and why it is fast enough.               |
|                                                                   |
| "I will sort the array and use two pointers to find all pairs     |
|  summing to k. This is O(n log n) which fits n <= 2*10^5."       |
|                                                                   |
| If you cannot say this sentence, you are not ready to code.       |
+-------------------------------------------------------------------+

When to Apply This Framework

Always. Every problem, including "trivial" Problem A. Two minutes on an easy problem, ten minutes on a hard one—the process pays for itself by preventing the opening-story scenario.

A few specific moments where it matters most:

• Any contest problem -- follow the full flowchart, even when the answer feels obvious
• Stuck or unfamiliar territory -- when nothing matches a template you know, the flowchart gives you a mechanical way to generate approaches instead of staring blankly
• Upsolving -- work through "CHOOSE algorithm", then check the editorial if you're still stuck
• Practice -- slow down on purpose; contest speed comes from internalizing the steps, not skipping them

The Discipline Is the Point

The flowchart is sequential, not optional. Knowing the steps and following the steps are different things. Under contest pressure, the overwhelming urge is to skip straight to code—especially on a problem that looks easy. That's precisely when the discipline matters most: the problems that wreck your round aren't the hard ones, they're the easy ones you blew up by rushing.

  WHERE MOST WA HAPPENS (time cost comparison):

  Skip the process:
  +------+         +----------+         +---------+
  | READ |-------->|   CODE   |-------->| submit  |--> WA
  | 1min |         |  15 min  |         |         |    |
  +------+         +----------+         +---------+    |
                                                       v
                                              +----------------+
                                              | panic-debug    |
                                              | 30 min         |
                                              +----------------+
                                              Total: ~46 min

  Follow the process:
  +------+  +------+  +------+  +------+  +------+  +------+
  | READ |->|CONSTR|->| EXAM |->| EDGE |->| CODE |->|submit|--> AC
  | 2min |  | 1min |  | 3min |  | 2min |  |10min |  | test |
  +------+  +------+  +------+  +------+  +------+  +------+
                                              Total: ~20 min

"What am I recomputing?" is the single most powerful unsticking question. When stuck, most people stare harder at the problem statement, as if the insight is hiding in the words. It isn't. Write the brute force, then look at what work it repeats on every iteration—that's a mechanical question, not inspiration, and it's exactly how prefix sums, memoization, and hash maps reveal themselves. The subarray-sum-equals-$k$ example below is canonical: once you see that brute force recomputes the same prefix sums over and over, the hash-map solution writes itself.

  "What am I recomputing?" in action:

  Problem: count subarrays with sum = k
  Array: [1, 2, 3, -1, 2], k = 4

  Brute force checks ALL (l, r) pairs:
  l=0: sum[0..0]=1, sum[0..1]=3, sum[0..2]=6, sum[0..3]=5, sum[0..4]=7
  l=1: sum[1..1]=2, sum[1..2]=5, sum[1..3]=4*,sum[1..4]=6
  l=2: sum[2..2]=3, sum[2..3]=2, sum[2..4]=4*
              ^                        ^
              |                        |
        Recomputing prefix[r] - prefix[l-1] each time!

  Insight: for each r, we need count of prefix[l-1] = prefix[r] - k
  --> Hash map of prefix sums seen so far
  --> O(n) instead of O(n^2)

---

Anatomy of a CP Problem

Every Codeforces problem is built from the same parts. The difference between a fast solve and a frustrating one often comes down to which part you read first—and how carefully.

The Constraint Block (Read This First)

Don't read the story first. Read the constraints. They tell you what algorithm complexity is permitted before you've even understood what the problem is asking—and once you know the allowed complexity, the candidate approaches collapse to a manageable list.

  +---------------------------------------------------------------+
  |  Constraints:                                                  |
  |  1 <= t <= 10^4          <-- multiple test cases               |
  |  1 <= n <= 2 * 10^5      <-- main input size                  |
  |  1 <= a_i <= 10^9        <-- values can be large (overflow?)   |
  |  Sum of n over all test  <-- total work budget, not per-test   |
  |  cases <= 2 * 10^5                                             |
  +---------------------------------------------------------------+

Key things to extract:

Constraint detail	What it tells you
$n\le 2\times {10}^5$	Need $O(n\log n)$ or better
$1\le a_i\le {10}^9$	Values don't fit in frequency array; watch for int overflow in sums
"Sum of $n$ over all test cases $\le 2\times {10}^5$"	Total work is bounded -- don't re-initialize huge arrays per test case
$n\le 20$	Bitmask / exponential approaches likely intended
$n\le 5000$	$O(n^2)$ is fine, $O(n^2\log n)$ might be tight
No explicit lower bound on $n$	$n=0$ or $n=1$ might be valid -- check!

Input Format

Three things to confirm before you write a single line of input parsing:

• 0-indexed vs 1-indexed. Codeforces almost always uses 1-indexed input. If you store in a 0-indexed array, adjust before processing—not mid-algorithm.
• Edge ordering. "The next $m$ lines contain $u_i$ and $v_i$" says nothing about direction. The prose tells you whether edges are directed or undirected; the input format does not.
• Multiple test cases. The first line is $t$. Forget to read it and your entire solution shifts by one. Forget to reset your data structures and test 2 inherits test 1's garbage.

Output Format

The output format is where careless reading becomes a Wrong Answer. Five traps to check before you code:

• "YES" / "NO" -- case matters. "Print YES or NO" means all caps. "Print Yes or No" is different. Match the problem's exact casing; some judges are lenient, but you can't count on it.
• "any valid answer" -- this is a gift. You don't need the smallest, the prettiest, or the most elegant. Greedy and constructive approaches become available the moment you see this phrase.
• "lexicographically smallest" -- this is not a gift. A specific answer is required, and your algorithm must guarantee it, not just stumble onto it.
• "modulo ${10}^9+7$" -- apply the modulus throughout your computation, not just at the end. Intermediate values overflow long long before you ever reach the final step.
• "-1 if impossible" -- some inputs have no valid answer. Your code must detect them explicitly; a missing if here is a guaranteed WA.

Working the Examples

Do not just read the examples. Trace through them by hand.

Take the first sample input and run your proposed approach on it—on paper, step by step—before you open an editor. If your hand trace doesn't match the sample output, you've misunderstood the problem. That's a five-second correction right now versus a twenty-minute debugging session after you've committed to a wrong model.

  +------------------------------------------------------------------+
  | EXAMPLE TRACE CHECKLIST                                          |
  |                                                                  |
  | 1. Read sample input. Write down what each value represents.     |
  | 2. Trace your proposed algorithm on this input, by hand.         |
  | 3. Compare your answer with sample output.                       |
  | 4. If they don't match: re-read the problem.                     |
  | 5. If they match: try the second sample (it usually tests a      |
  |    different case -- often an edge case or corner case).          |
  +------------------------------------------------------------------+

---

Constraint-to-Algorithm Selection

In a textbook you analyze an algorithm and derive its complexity. In a contest you run that process backward: read the constraints, determine what complexity is allowed, then narrow the candidate algorithms to those that fit. The constraint table below is the lookup that makes this fast.

The Constraint Table

Memorize this table. No single heuristic in competitive programming pays off more consistently:

Max $n$	Max allowed complexity	Typical approaches
$n\le 10$	$O(n!)$	Permutation brute force, full enumeration
$n\le 20$	$O(2^n)$ or $O(n\cdot 2^n)$	Bitmask DP, subset enumeration
$n\le 25$	$O(2^{n/2})$	Meet in the middle (Meet in the Middle)
$n\le 100$	$O(n^4)$	DP with multiple dimensions, small flow networks
$n\le 500$	$O(n^3)$	Floyd-Warshall, cubic DP, matrix operations, Gaussian elimination
$n\le 5000$	$O(n^2)$	Quadratic DP, pairwise comparisons, Contribution Technique
$n\le {10}^5$	$O(n\log n)$	Sorting, binary search, segment trees, BIT, merge sort tree
$n\le {10}^5$	$O(n\sqrt{n})$	Mo's algorithm, sqrt decomposition
$n\le {10}^6$	$O(n)$ or $O(n\log n)$	Linear scans, prefix sums, two pointers, suffix arrays, KMP/Z-function
$n\le {10}^7$	$O(n)$ only	Sieve of Eratosthenes, linear recurrence, bucket techniques
$n\le {10}^8$	$O(n)$ only	Simple iteration, mathematical formula
$n\le {10}^{18}$	$O(\log n)$ or $O(\sqrt{n})$	Binary search, math, matrix exponentiation, binary lifting

Additional constraint patterns for specialized algorithms:

Constraint pattern	Typical approaches
String length $\le {10}^6$	Suffix array, suffix automaton, KMP, Z-function, Aho-Corasick
Polynomial degree $\le {10}^5$	FFT/NTT for convolution, $O(n\log n)$
Matrix size $\le 100$, exponent $\le {10}^{18}$	Matrix exponentiation for linear recurrences
$n\le {10}^5$, updates + queries	Segment tree, BIT (Fenwick tree), lazy propagation
$n\le {10}^5$, offline queries	Mo's algorithm, offline techniques
Graph: $V+E\le {10}^5$	BFS, DFS, Dijkstra, topological sort
Graph: dense, $V\le 500$	Floyd-Warshall, Hungarian algorithm, $O(V^3)$ flow
Value range $\le {10}^6$	Frequency array, counting sort, value-indexed structures

Rule of thumb: A modern computer does roughly $3\times {10}^8$ to ${10}^9$ simple operations per second. With a 2-second time limit, you can do about $6\times {10}^8$ operations. Divide that by your $n$ to find the allowed per-element work.

Pattern Fingerprint: N <= [bound] -> Constraint table lookup -> Algorithm family -> Implementation template

See also: Data Structure Selection Guide for detailed guidance on choosing the right structure once you know the complexity budget.

Worked Examples

Example 1: "Given $n\le 20$ items, find the subset with maximum value that fits in a knapsack of capacity $W$."

Constraint read: $n\le 20$ means $2^{20}\approx {10}^6$ subsets total. You can enumerate every one of them, compute its total weight and value, and keep the best that fits. $O(2^n)$ is fast enough—this is bitmask enumeration by design, not brute force by accident.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];

    int best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        // Invariant: best = max value among all subsets [0..mask-1] that fit
        int tw = 0, tv = 0;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) {
                tw += w[i];
                tv += v[i];
            }
        }
        if (tw <= W) best = max(best, tv);
    }
    cout << best << "\n";
}

Example 2: "Given an array of $n\le 2\times {10}^5$ integers, answer $q\le 2\times {10}^5$ queries: what is the sum of elements in range $[l,r]$?"

Constraint read: $n,q\le 2\times {10}^5$. A naïve per-query scan costs $O(n\cdot q)=O(4\times {10}^{10})$—nowhere near fast enough. You need $O(1)$ per query, which means $O(n)$ preprocessing. That's prefix sums by definition.

Example 3: "Given $n\le {10}^5$ points, find the pair with minimum distance."

Constraint read: $n\le {10}^5$. Checking every pair is $O(n^2)={10}^{10}$, which is too slow by two orders of magnitude. $O(n\log n)$ is the target. This is the classic closest pair problem, solved by divide and conquer or sweep line.

Two Constraints Working Together

Many problems hand you two parameters. Neither is decorative. When you see $n$ and $m$ (or $n$ and $k$), multiply them mentally before you commit to an approach:

  n <= 10^5, m <= 10^5     -->  O((n + m) log n) or similar
  n <= 500,  m <= 500       -->  O(n * m) or even O(n^2 * m) might work
  n <= 10^5, k <= 20        -->  O(n * 2^k) -- bitmask over k, linear over n

If $n\times m\le {10}^8$, an $O(n\times m)$ solution is borderline but often squeaks through. If $n\times m>{10}^9$, the product alone rules out a naïve nested loop—you need a smarter factoring.

---

Edge Case Enumeration Before Coding

More Wrong Answers come from edge cases than from wrong algorithms. The fix is structural: enumerate them before you write a single line of code, not while staring at a failing submission. By the time you're debugging, you're already paying the time penalty.

The Universal Checklist

Run through this list for every problem:

  +------------------------------------------------------------------+
  | EDGE CASE CHECKLIST                                              |
  +------------------------------------------------------------------+
  |                                                                  |
  | INPUT SIZE:                                                      |
  |   [ ] n = 1 (or minimum allowed n)                               |
  |   [ ] n = 0 (if constraints allow)                               |
  |   [ ] n = max (stress test for TLE)                              |
  |                                                                  |
  | INPUT VALUES:                                                    |
  |   [ ] All elements equal                                         |
  |   [ ] All elements distinct                                      |
  |   [ ] Already sorted ascending                                   |
  |   [ ] Already sorted descending                                  |
  |   [ ] Negative numbers (if a_i can be negative)                  |
  |   [ ] a_i = 0 (if allowed)                                      |
  |   [ ] a_i at maximum value (overflow when summing?)              |
  |                                                                  |
  | OUTPUT:                                                          |
  |   [ ] Answer is 0                                                |
  |   [ ] Answer is -1 / impossible                                  |
  |   [ ] Answer overflows int (use long long)                       |
  |   [ ] Answer requires modular arithmetic                         |
  |                                                                  |
  | GRAPH-SPECIFIC:                                                  |
  |   [ ] Disconnected graph                                         |
  |   [ ] Self-loops / parallel edges                                |
  |   [ ] Tree (n-1 edges)                                           |
  |   [ ] Star graph / path graph (degenerate trees)                 |
  |                                                                  |
  | ARRAY-SPECIFIC:                                                  |
  |   [ ] Single element array (n=1)                                 |
  |   [ ] All elements identical                                     |
  |   [ ] Maximum/minimum values at boundaries (first/last position) |
  |   [ ] Array is a permutation (all distinct, 1..n)                |
  |   [ ] Two elements only (n=2, check pairwise logic)              |
  |                                                                  |
  | STRING-SPECIFIC:                                                 |
  |   [ ] Empty string or single character                           |
  |   [ ] All characters the same ("aaaa...")                        |
  |   [ ] Palindrome input                                           |
  +------------------------------------------------------------------+

The Cost of Skipping Edge Cases

Consider this concrete scenario. Problem: "Given an array of $n$ integers, find the maximum subarray sum."

You recognize Kadane's algorithm immediately and code it fast:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int best = 0, cur = 0;          // <-- bug is here
    for (int i = 0; i < n; i++) {
        // Invariant: cur = max subarray sum ending at i; best = global max so far
        cur = max(a[i], cur + a[i]);
        best = max(best, cur);
    }
    cout << best << "\n";
}

You test it on the sample: [-2, 1, -3, 4, -1, 2, 1, -5, 4] -> output 6. Correct. Submit.

Wrong Answer. The hidden test is [-3, -5, -1, -8]: all negatives. Your code outputs 0 because best starts at 0, but the correct answer is -1 (the largest single element). The fix is a one-liner—initialize best = a[0] and start the loop from i = 1, or use best = INT_MIN. Three seconds to fix once you know where to look. Thirty minutes of flailing to find it after the fact.

If you'd run through the checklist—"Negative numbers? All elements equal?"—you would have tested [-5] before submitting and caught this immediately.

Overflow: The Silent Killer

Problem: "Find the sum of all pairwise products $\sum _{i<j}{a}_i\cdot a_j$."

With $n\le 2\times {10}^5$ and $a_i\le {10}^9$, the numbers escalate fast:

• Each individual product reaches up to ${10}^{18}$—fits in long long.
• But there are $n^2/2\approx 2\times {10}^{10}$ such products, so the total sum can reach $2\times {10}^{28}$. That doesn't fit in unsigned long long, let alone long long.

You need modular arithmetic or __int128. A long long accumulator silently wraps and produces a plausible-looking wrong answer. The checklist item "$a_i$ at maximum value—overflow when summing?" catches this before you submit.

---

Before You Code—Checklist

• [ ] I read the constraints and identified the algorithm family
• [ ] I enumerated edge cases (n=0, n=1, all same, overflow)
• [ ] I can state the loop invariant in one sentence
• [ ] I have a brute-force solution I can diff against
• [ ] I checked for integer overflow (will values exceed 2^31?)

---

Loop Invariants as a Correctness Tool

A loop invariant is a statement that holds before the loop begins, survives every iteration unchanged, and is still true when the loop exits. Stating the invariant precisely is not a formality—it's the proof that your code is correct. If you can articulate it clearly, you almost certainly have no off-by-one bugs. If you can't, you probably do.

Binary Search from the Invariant

Most people learn binary search as a memorized template—lo = 0, hi = n - 1, mid = (lo + hi) / 2—and then spend contest after contest fighting off-by-one errors because they don't know why the boundaries move the way they do. The fix is to derive binary search from its invariant instead of memorizing the template.

Problem: In a sorted array a, find the smallest index $i$ such that $a[i]\ge x$.

Choose the invariant:

+-------------------------------------------------------------------+
| INVARIANT: a[lo - 1] < x  and  a[hi] >= x                        |
|                                                                   |
| (lo - 1 might be "before the array" -- that's fine,              |
|  it represents "everything to the left is too small")             |
+-------------------------------------------------------------------+

Initialization: Set lo = 0, hi = n. The invariant holds vacuously: a[-1] is conceptually $-\mathrm{\infty }<x$, and a[n] is conceptually $+\mathrm{\infty }\ge x$.

Maintenance: Each iteration, compute mid = lo + (hi - lo) / 2.

  Case 1: a[mid] >= x
    --> mid satisfies the "hi" side of the invariant
    --> set hi = mid  (shrink from the right)
    --> invariant still holds: a[lo-1] < x, a[hi] >= x

  Case 2: a[mid] < x
    --> mid satisfies the "lo-1" side of the invariant
    --> set lo = mid + 1  (shrink from the left)
    --> invariant still holds: a[lo-1] < x, a[hi] >= x

Termination: When lo == hi, the invariant says a[lo - 1] < x and a[lo] >= x. So lo is the answer.

#include <bits/stdc++.h>
using namespace std;

// Returns smallest i such that a[i] >= x, or n if no such i exists.
int lower(const vector<int>& a, int x) {
    int lo = 0, hi = (int)a.size();
    // Invariant: a[lo-1] < x and a[hi] >= x
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= x)
            hi = mid;       // a[mid] >= x, so mid is a valid hi
        else
            lo = mid + 1;   // a[mid] < x, so mid is a valid lo-1
    }
    return lo;  // lo == hi, this is the answer
}

int main() {
    vector<int> a = {2, 5, 8, 11, 14, 17, 21, 25};
    cout << lower(a, 14) << "\n";  // 4
    cout << lower(a, 15) << "\n";  // 5
    cout << lower(a, 1) << "\n";   // 0
    cout << lower(a, 30) << "\n";  // 8 (not found)
}

Visual Trace of the Invariant

Searching for $x=15$ in [2, 5, 8, 11, 14, 17, 21, 25]:

  Step 0: lo=0, hi=8
          [ 2 | 5 | 8 | 11 | 14 | 17 | 21 | 25 ] .
            ^                                        ^
           lo                                       hi
          Invariant: a[-1]=-inf < 15, a[8]=+inf >= 15   OK

  Step 1: mid=4, a[4]=14 < 15 --> lo=5
          [ .   .   .   .   .  | 17 | 21 | 25 ] .
                                  ^                ^
                                 lo               hi
          Invariant: a[4]=14 < 15, a[8]=+inf >= 15      OK

  Step 2: mid=6, a[6]=21 >= 15 --> hi=6
          [ .   .   .   .   .  | 17 | 21 | .  ]
                                  ^    ^
                                 lo   hi
          Invariant: a[4]=14 < 15, a[6]=21 >= 15        OK

  Step 3: mid=5, a[5]=17 >= 15 --> hi=5
          [ .   .   .   .   .  | 17 | .    .  ]
                                  ^
                                lo=hi=5
          Invariant: a[4]=14 < 15, a[5]=17 >= 15        OK

  lo == hi == 5. Answer: index 5, which holds 17
  (the first element >= 15).

At every step the invariant holds—that's what makes the code correct, not the template. No guessing, no "maybe I need lo <= hi", no checking whether the final answer is lo or lo - 1. The invariant tells you.

Two-Pointer Invariant Example

Problem: In a sorted array, find two elements that sum to $S$.

Invariant:

+-------------------------------------------------------------------+
| INVARIANT: No valid pair exists entirely to the left of L          |
| or entirely to the right of R.                                    |
+-------------------------------------------------------------------+

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, S;
    cin >> n >> S;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    int lo = 0, hi = n - 1;
    // Invariant: no valid pair exists entirely left of lo or entirely right of hi
    while (lo < hi) {
        int sum = a[lo] + a[hi];
        if (sum == S) {
            cout << a[lo] << " " << a[hi] << "\n";
            return 0;
        } else if (sum < S) {
            lo++;   // a[lo] is too small; no pair with lo works
        } else {
            hi--;   // a[hi] is too large; no pair with hi works
        }
    }
    cout << "No pair found\n";
}

Why lo++ when sum < S? Because the array is sorted, a[lo] + a[hi] is the largest sum that a[lo] can participate in—a[hi] is already the biggest remaining element. If that combination is still too small, no pairing of a[lo] with anything to its right can reach $S$ either. Discard a[lo] with confidence. The invariant is maintained.

The Invariant Mindset

+-------------------------------------------------------------------+
| If you can state the invariant, your code is probably correct.    |
| If you can't state the invariant, your code probably has a bug.   |
|                                                                   |
| When debugging, don't add random +1/-1. Instead ask:              |
| "What is my invariant, and where does it break?"                  |
+-------------------------------------------------------------------+

---

What to Do When Stuck

You've read the problem, analyzed the constraints, worked through the examples by hand—and you still don't see it. That's fine. Being stuck is not the problem; staying stuck is. Here is the meta-loop for getting unstuck systematically rather than by inspiration:

The Unsticking Sequence

  +-------------------------------------------------------------------+
  | WHEN STUCK -- FOLLOW THIS SEQUENCE                                |
  +-------------------------------------------------------------------+
  |                                                                   |
  | 1. SOLVE TINY CASES BY HAND                                      |
  |    n=1, n=2, n=3. Write down the answer for each.                |
  |    Look for a pattern in your hand-computed answers.              |
  |                                                                   |
  | 2. TRY BRUTE FORCE                                               |
  |    If n is small enough in the actual constraints,                |
  |    submit brute force. No shame -- a correct O(n^3) beats        |
  |    a wrong O(n log n).                                            |
  |                                                                   |
  | 3. WHAT ARE YOU RECOMPUTING?                                      |
  |    Look at your brute force. What work is repeated?               |
  |    Can you precompute it? (prefix sums, memoization, DP)          |
  |                                                                   |
  | 4. DOES SORTING HELP?                                             |
  |    Many problems become easier on sorted data.                    |
  |    Sorting unlocks: binary search, two pointers,                  |
  |    greedy left-to-right scans.                                    |
  |                                                                   |
  | 5. IS THE ANSWER MONOTONIC?                                       |
  |    "Can we achieve X with budget B?"                              |
  |    If yes for B, also yes for B+1 --> binary search on answer.    |
  |                                                                   |
  | 6. SIMPLIFY THE PROBLEM                                           |
  |    What if all elements were positive?                            |
  |    What if n was even? What if the graph was a tree?              |
  |    Solve the simpler version first, then generalize.              |
  |                                                                   |
  | 7. READ THE TAGS                                                  |
  |    On Codeforces, problem tags exist. Use them.                   |
  |    Learning > ego. A tag that says "greedy, sortings"             |
  |    tells you the high-level approach. You still need              |
  |    to figure out the details.                                     |
  +-------------------------------------------------------------------+

Worked Example: Getting Unstuck

Problem: Given an array of $n$ integers, find the number of subarrays with sum equal to $k$.

Step 1: Tiny cases by hand.

Array: [1, 2, 3], $k=3$.

• Subarrays: [1]=1, [2]=2, [3]=3, [1,2]=3, [2,3]=5, [1,2,3]=6
• Those with sum 3: [3] and [1,2]. Answer: 2.

Step 2: Brute force. For each pair $(l,r)$, compute the sum. $O(n^2)$ pairs, $O(n)$ per sum = $O(n^3)$. With prefix sums, $O(n^2)$.

Step 3: What are we recomputing? For each ending position $r$, we scan back over all starting positions $l$ and recompute the subarray sum as prefix[r] - prefix[l-1]. We want this to equal $k$, which means we want prefix[l-1] == prefix[r] - k. So the question for each $r$ is: "how many previous prefix sums are exactly prefix[r] - k?" That's a frequency lookup—use a hash map, and the scan disappears entirely.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    unordered_map<long long, int> freq;
    freq[0] = 1;  // empty prefix
    long long prefix = 0;
    int count = 0;
    for (int i = 0; i < n; i++) {
        // Invariant: freq contains counts of all prefix sums for indices [0..i-1]
        prefix += a[i];
        count += freq[prefix - k];
        freq[prefix]++;
    }
    cout << count << "\n";
}

$O(n)$—from stuck to optimal by asking one mechanical question.

What Would You Do If...?

1. You pass all samples but get WA? -> Generate random small tests, compare with brute force. The bug is in an edge case your samples don't cover.
2. You get TLE on the last test case? -> Your algorithm is correct but too slow. Look at your constraint table: can you shave a log factor? Is there a two-pointer or prefix-sum optimization?
3. You can't even think of an approach? -> Shrink N to 3-4 and solve by hand. Draw pictures. The pattern will emerge from the small case.

---

Greedy Correctness—The Exchange Argument

Greedy algorithms are easy to invent and deceptively hard to validate. Most greedy ideas that feel right are actually wrong—there's a counterexample hiding somewhere in the input space. The exchange argument is the standard weapon for either proving your greedy is correct or discovering the counterexample that kills it.

The Framework

  +------------------------------------------------------------------+
  | EXCHANGE ARGUMENT                                                |
  +------------------------------------------------------------------+
  |                                                                  |
  | 1. Let G = your greedy solution, O = some optimal solution.      |
  | 2. Find the first point where G and O differ.                    |
  |    G chooses element g, O chooses element o.                     |
  | 3. Construct O' by replacing o with g in O.                      |
  | 4. Show O' is still feasible (all constraints satisfied).        |
  | 5. Show cost(O') <= cost(O)  (O' is no worse).                  |
  | 6. Repeat: each swap makes O agree with G on one more            |
  |    position, without worsening cost.                             |
  |    After all swaps, O = G --> G is optimal.                      |
  +------------------------------------------------------------------+

Step 5 is where the work actually lives. Steps 1-4 are mechanical; step 5 requires problem-specific reasoning about why swapping doesn't hurt. If you can't complete it, your greedy is almost certainly wrong.

Example: Activity Selection

Problem: Given $n$ activities with start and end times, select the maximum number of non-overlapping activities.

Greedy rule: Sort by end time. Among all activities that don't overlap with what you've already selected, always pick the one that finishes earliest.

Exchange argument:

Let $G=\{g_1,g_2,\dots ,g_k\}$ (greedy solution, sorted by end time) and $O=\{o_1,o_2,\dots ,o_m\}$ (optimal solution, sorted by end time). Assume $m>k$ and derive a contradiction.

Key claim: $\text{end}(g_i)\le \text{end}(o_i)$ for all $i$.

• Base case: $g_1$ is the activity with globally earliest end time (greedy's first choice). So $\text{end}(g_1)\le \text{end}(o_1)$.
• Inductive step: Suppose $\text{end}(g_{i-1})\le \text{end}(o_{i-1})$. Any activity compatible with $o_{i-1}$ is also compatible with $g_{i-1}$ (it finishes no later). Greedy picks the compatible activity with earliest end time among all remaining options, so $\text{end}(g_i)\le \text{end}(o_i)$.

The claim means every greedy choice finishes no later than the corresponding optimal choice, so greedy can match every pick that optimal makes—$k\ge m$. But $m$ is optimal, so $k=m$. Greedy is optimal.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> act(n);
    for (auto& [s, e] : act) cin >> s >> e;

    sort(act.begin(), act.end(), [](auto& a, auto& b) {
        return a.second < b.second;  // sort by end time
    });

    int count = 0, last_end = -1;
    for (auto& [s, e] : act) {
        // Invariant: count = number of selected non-overlapping activities so far;
        //            last_end = end time of the last selected activity
        if (s >= last_end) {
            count++;
            last_end = e;
        }
    }
    cout << count << "\n";
}

Example: Fractional Knapsack

Problem: $n$ items with weight $w_i$ and value $v_i$. Knapsack capacity $W$. You can take fractions of items. Maximize total value.

Greedy rule: Sort by value-to-weight ratio $v_i/w_i$ descending. Take items greedily.

Exchange argument: Suppose optimal $O$ takes less of item $g$ (the one with higher $v/w$) than greedy $G$ does, and compensates with more of some item $o$ (lower $v/w$). Transfer $ϵ$ units of weight from $o$ to $g$ in $O$: total weight is unchanged (feasible), but value strictly increases because $v_g/w_g>v_o/w_o$. That means $O$ was not optimal—contradiction. Greedy is optimal.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<double> w(n), v(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];

    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) {
        return v[a] / w[a] > v[b] / w[b];
    });

    double total = 0, cap = W;
    for (int i : idx) {
        // Invariant: total = value collected from items processed so far; cap = remaining capacity
        if (cap <= 0) break;
        double take = min(cap, w[i]);
        total += take * (v[i] / w[i]);
        cap -= take;
    }
    cout << fixed << setprecision(6) << total << "\n";
}

When Exchange Argument Fails: You Need DP

When step 5 stalls—when the swap you construct either isn't feasible or makes things worse—that's not a proof gap. That's the counterexample hiding in plain sight. Your greedy is wrong; you almost certainly need dynamic programming.

Classic illustration: 0/1 Knapsack. Items: values [60, 100, 120], weights [10, 20, 30], capacity $W=50$.

Greedy by value/weight ratio picks item 1 ($6.0$), then item 2 ($5.0$)—total weight $30$, remaining capacity $20$. Item 3 weighs $30$, won't fit. Total value: $160$.

The optimal is items 2 and 3: weight $50$, value $220$.

The exchange argument breaks down because items can't be fractured—swapping item 2 for item 1 in the optimal set displaces exactly enough capacity to rule out item 3. The swap is not weight-neutral, and the greedy can't recover. When you hit that wall, reach for DP. See DP Intro and DP vs Greedy Decision Guide.

---

Brute Force as an Explicit Strategy

Brute force gets a bad reputation it doesn't deserve. When constraints allow it, brute force isn't laziness—it's the correct strategy, and reaching for a clever solution instead is what wastes time.

When Brute Force IS the Solution

If $n\le 10$, the problem author expects brute force. An $O(n!)$ solution handles $10!=3.6\times {10}^6$ states in well under a second. Spending twenty minutes hunting for an elegant $O(n\log n)$ solution when the constraints scream "enumerate everything" is a net loss—you're solving a harder version of the problem than the one you were given.

  +------------------------------+
  | n <= 8   -->  O(n!) is fine  |
  | n <= 20  -->  O(2^n) is fine |
  | n <= 500 -->  O(n^3) is fine |
  +------------------------------+

Brute Force as a Stepping Stone

Even when the constraints demand an efficient solution, code brute force first:

1. It validates your problem model. If brute force passes the samples, you've understood the problem correctly before committing to an approach.
2. It gives you an oracle. When your optimized solution gets WA on test 17, you can stress-test the two implementations against each other on small random inputs and isolate the discrepancy.
3. Its structure often points directly to the optimization. The repeated work in your brute force is usually the DP state you need, or the redundancy that a greedy order eliminates.

Brute Force as an Oracle

When your optimized solution gets Wrong Answer and the bug isn't visible from inspection:

  +------------------------------------------------------------------+
  | STRESS TESTING LOOP                                              |
  |                                                                  |
  | 1. Write a brute-force solution (slow but correct).              |
  | 2. Write a random test generator.                                |
  | 3. Run both on the same random inputs.                           |
  | 4. Find the smallest input where they disagree.                  |
  | 5. Debug your optimized solution on that input.                  |
  +------------------------------------------------------------------+

// stress_test.cpp -- run this locally, not on the judge
#include <bits/stdc++.h>
using namespace std;

int brute(vector<int>& a) {
    // O(n^2) or O(n^3) correct solution
    // ...
    return 0; // placeholder
}

int fast(vector<int>& a) {
    // your O(n log n) solution that might have a bug
    // ...
    return 0; // placeholder
}

int main() {
    mt19937 rng(42);
    for (int iter = 0; iter < 100000; iter++) {
        int n = rng() % 10 + 1;   // small n for brute force
        vector<int> a(n);
        for (int& x : a) x = rng() % 21 - 10;  // values in [-10, 10]

        int b = brute(a);
        int f = fast(a);
        if (b != f) {
            cerr << "MISMATCH on iteration " << iter << "\n";
            cerr << "n = " << n << ", a = ";
            for (int x : a) cerr << x << " ";
            cerr << "\nbrute = " << b << ", fast = " << f << "\n";
            return 1;
        }
    }
    cerr << "All tests passed\n";
}

This technique surfaces bugs that code review misses every time—the failure manifests on a concrete 6-element input, not in the abstract. See Debugging and Stress Testing for a full treatment.

---

When NOT to Use This Framework

• You already recognize the problem pattern -- if you see "shortest path" and know it's Dijkstra, skip the flowchart. Don't slow yourself down.
• The problem is ad-hoc / constructive -- constraint tables help less for problems where the key insight is a mathematical observation rather than an algorithmic pattern. See Constructive Algorithms.
• Time pressure in a contest -- if you have 10 minutes left, trust your gut rather than working through a formal checklist.

---

Contest Cheat Sheet

Mnemonic: "CERBI" -- Constraints, Edge cases, Read examples, Brute force, Invariant.

If I Had 5 Minutes

• Read constraints FIRST -- they reveal the algorithm family
• Check edge cases: n=0, n=1, all same, max values
• Write brute force; only optimize if TLE is certain
• Loop invariant = one sentence per loop = zero bugs
• When stuck: draw it, shrink it, flip it

+--------------------------------------------------------------------+
| HOW TO SOLVE PROBLEMS -- QUICK REFERENCE                           |
+--------------------------------------------------------------------+
|                                                                    |
| BEFORE CODING:                                                     |
|   1. Read problem TWICE. Note constraints, output format.          |
|   2. Constraints --> allowed complexity (use the table).            |
|   3. Trace samples by hand.                                        |
|   4. State your approach in one sentence.                          |
|   5. List edge cases (n=1, all equal, negatives, overflow).        |
|                                                                    |
| CONSTRAINT TABLE:                                                  |
|   n<=10: O(n!)   n<=20: O(2^n)    n<=500: O(n^3)                  |
|   n<=5000: O(n^2)  n<=10^5: O(n log n)  n<=10^6: O(n)             |
|                                                                    |
| WHEN STUCK:                                                        |
|   1. Solve n=1,2,3 by hand     4. Does sorting help?              |
|   2. Code brute force           5. Binary search on answer?        |
|   3. What are you recomputing?  6. Simplify the problem            |
|                                                                    |
| GREEDY CHECK:                                                      |
|   Can you do the exchange argument? If step 5 fails --> use DP.   |
|                                                                    |
| DEBUGGING:                                                         |
|   State the loop invariant. Where does it break?                   |
|   Stress test: brute force vs fast on random small inputs.         |
+--------------------------------------------------------------------+

---

Common Mistakes and Debugging

Common Process Mistakes

Mistake	Consequence	Fix
Start coding immediately after reading	Misunderstand problem, waste 20+ min	Read twice, trace samples, state approach first
Ignore constraints	Choose wrong algorithm complexity	Read constraints FIRST, use the table
Test only on given samples	Miss edge cases	Run through the edge case checklist
Debug by adding random +1/-1	Introduces new bugs	State the invariant, find where it breaks
Refuse to use brute force	Overcomplicate small-constraint problems	Check constraints -- if brute force fits, use it
Don't test $n=1$	Off-by-one in loops, empty output	Always test minimum valid input

The int vs long long Decision

+-------------------------------------------------------------------+
| Use long long when:                                               |
|   - a_i up to 10^9 and you compute sums/products of two values   |
|   - n up to 10^5 and you sum elements (sum can reach 10^14)      |
|   - The answer could exceed 2 * 10^9                              |
|                                                                   |
| Safe default: use long long for all intermediate computations     |
| when a_i > 10^4 or n > 10^4. The performance cost is negligible. |
+-------------------------------------------------------------------+

Output Format Traps

• "YES"/"NO" vs "Yes"/"No": Copy the exact casing from the problem statement. Some judges are lenient; the ones that aren't will penalize you precisely because you assumed they would be.
• Trailing spaces: Usually fine, but some problems on non-CF judges are strict.
• Newline after last line: Always print "\n" after your last output line.
• Floating point precision: When the problem says "absolute or relative error $\le {10}^{-6}$", use cout << fixed << setprecision(9).

The "I'm Sure It's Right" Trap

You're confident it's right, but it gets WA. Run this checklist in order—it covers 95% of the causes:

1. Re-read the output format. Case sensitivity, trailing newline, floating-point precision—read it verbatim from the problem statement.
2. Test $n=1$. The most common edge-case miss, every time.
3. Test all-same input. [5, 5, 5, 5, 5] finds a surprising number of bugs.
4. Check overflow. Add #define int long long temporarily and resubmit. If it now passes, you have an overflow.
5. Check 0-indexed vs 1-indexed. Particularly in graph adjacency lists and tree problems.
6. Stress test. A brute-force oracle on small random inputs will find the counterexample in seconds.

Mental Traps

"I know this pattern." You see "subarray" and immediately reach for sliding window. But the problem has negative numbers—and negative numbers break the monotonicity that makes sliding window work. Pattern-matching to the wrong technique doesn't save time; it costs more than starting cold, because you've also committed emotionally to an approach and have to un-commit under pressure.

  WRONG thinking:                   RIGHT thinking:

  "Subarray problem?                "Subarray problem.
   Sliding window!"                  Let me check..."
       |                                |
       v                                v
  Code sliding window              Does it have negatives?
       |                            /            \
       v                          NO              YES
  WA on test 5                     |               |
  (negative numbers)               v               v
       |                        Sliding         Prefix sums +
       v                        window          hash map
  Debug for 30 min                OK             (Kadane / etc.)

"I'll just code it and see." Coding is the slowest phase of problem-solving—slower than thinking, slower than hand-tracing, slower than running through the edge-case checklist. If you haven't convinced yourself the algorithm is both correct and fast enough before you open an editor, you're staking 20+ minutes of implementation on a guess. The cost table below is not theoretical:

  Cost analysis of "code first, think later":

  +------------------------------------------+
  | Action            | Time    | Outcome     |
  +------------------------------------------+
  | Think + trace     | 5 min   | Correct 90% |
  | Code immediately  | 20 min  | Correct 50% |
  | Debug WA          | 15 min  | Maybe fix   |
  +------------------------------------------+
  | Total (think)     | ~25 min | AC          |
  | Total (code)      | ~35 min | Maybe AC    |
  +------------------------------------------+

  The 5 min investment saves 10+ min every time.

Treating edge cases as unlikely. "$n=1$ probably won't appear in the tests." It will—it's test 1. "All elements equal? That seems contrived." That's test 3. Problem setters write the degenerate cases first, because those are the cases that reveal bugs. Edge cases aren't rare corner scenarios you might be unlucky enough to hit; they're the default input distribution for the first dozen tests.

  What you think tests look like:

  Test 1: n=5, normal random array       <-- you test this
  Test 2: n=100, normal random array     <-- and this
  Test 3: n=100000, large random         <-- and this

  What tests ACTUALLY look like:

  Test 1: n=1                            <-- did you test this?
  Test 2: n=2, already sorted            <-- or this?
  Test 3: all elements equal             <-- or this?
  Test 4: all negative                   <-- or this?
  Test 5-50: random large cases          <-- these are easy to pass

The Mistake That Teaches

I once spent 45 minutes on a Div2-C building a segment tree. The constraints said $N\le 5000$. What I needed was an $O(N^2)$ DP—a simple nested loop, maybe 8 lines. The segment tree compiled, passed the samples, and TLE'd on test 7. The constant factor was too high for $N=5000$ with heavy queries. The $O(N^2)$ solution passed in 0.3 seconds. The constraints were whispering the answer the whole time. I was too busy being clever to listen.

---

Debug This!

Bug 1: Why does this give WA on n=1?

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 1; i < n; i++) {  // Bug: starts at i=1, skips a[0]
        ans = max(ans, a[i]);
    }
    cout << ans << endl;
}

Answer: When n=1, the loop never executes, and ans stays 0. If a[0] is negative or the answer should be a[0], this is wrong. Fix: initialize ans = a[0] and start loop at i=1, or start ans = INT_MIN.

Bug 2: Why does this overflow?

int n = 200000;
int sum = 0;
for (int i = 1; i <= n; i++) sum += i;
// sum should be n*(n+1)/2 = 20,000,100,000 > INT_MAX

Answer: n*(n+1)/2 exceeds 2^31-1 ~= 2.1x10^9. Use long long.

Bug 3: Why does this comparator cause RE?

sort(a.begin(), a.end(), [](int x, int y) {
    return x <= y;  // Bug: not strict weak ordering
});

Answer: <= violates strict weak ordering (requires <). On some compilers/STLs, this causes undefined behavior or segfault.

---

Rating Progression

• At CF 1200: You can solve A/B by reading constraints and picking brute force vs. sorting
• At CF 1500: You use the constraint table reflexively; you check edge cases before submitting
• At CF 1800: You combine two constraint hints (e.g., N*log(N) + value range -> segment tree)
• At CF 2100: You derive algorithms from invariants; exchange arguments and proof sketches are routine

---

Self-Test

If you can't do each of these cold—without looking—the process hasn't been internalized yet:

• [ ] Given a problem with $n\le 2\times {10}^5$, immediately name the allowed complexity class and three algorithm families that fit it.
• [ ] Recite the full problem-solving flowchart (all 8 steps from "read" to "submit") from memory.
• [ ] Given a sample problem statement, demonstrate reading constraints first and extracting: input size, value range, multiple test cases, and output format traps ("YES" vs "Yes", modular arithmetic, "-1 if impossible").
• [ ] For a problem you just solved, enumerate at least 5 edge cases from the universal checklist: $n=1$? $n=0$? All elements equal? Already sorted? Reverse sorted? Maximum values causing overflow?
• [ ] Walk through the "what am I recomputing?" technique: start with brute force for subarray-sum-equals-$k$, identify the redundancy, and derive the prefix-sum + hash-map $O(n)$ solution.
• [ ] State the invariant for binary search ($a[\text{lo}-1]<x$ and $a[\text{hi}]\ge x$) and trace it through a 4-step example without hesitation.
• [ ] Describe three signals that you should abandon your current approach and try something different instead of continuing to patch it.

---

Practice Problems

These problems are chosen for process work, not algorithm difficulty. The algorithm is usually straightforward; careful reading, edge-case enumeration, and constraint analysis are what separate an AC from a penalty.

#	Problem	Source	Difficulty	Key Process Skill
1	Watermelon	CF 4A	800	Edge case: $n=2$
2	Way Too Long Words	CF 71A	800	Careful output format reading
3	Next Round	CF 158A	800	Edge case: all equal, score = 0
4	Nearly Lucky Number	CF 110A	800	Read problem statement precisely
5	Two Arrays and Swaps	CF 1353B	800	Constraint analysis: $n\le 30$ allows brute force
6	Mahmoud and Longest Uncommon Subseq.	CF 766A	1000	Trick: re-read carefully, answer is simpler than it seems
7	Yet Another Palindrome Problem	CF 1324B	1100	Edge case enumeration, $n\le 5000$ -> $O(n^2)$
8	Maximum Median	CF 1201C	1400	Binary search on answer + constraint analysis

How to use this table: Don't grind these for speed. Use them to practice the process. For each problem:

1. Follow the full flowchart from the Intuition section—even on the 800-rated ones.
2. Name which edge cases from the universal checklist are live for that problem specifically.
3. Confirm your constraint-to-complexity mapping before you write a line of code.

---

Further Reading

• Binary Search -- invariant-based derivation of binary search in depth
• Greedy -- full treatment of greedy algorithms and exchange arguments
• Complete Search -- brute force techniques and when to apply them
• Debugging and Stress Testing -- the stress testing loop in detail
• DP Intro -- when greedy fails, DP is usually the answer
• Competitive Programmer's Handbook -- Chapter 1 covers problem-solving process
• CF Blog: How to practice -- advice on deliberate practice and upsolving
• Practice Ladder 1100-1400 -- structured problem sets for building process skills
• DP vs Greedy Decision Guide -- when the exchange argument fails and DP is the answer
• Data Structure Selection Guide -- choosing the right data structure from constraints

---

What to Solve Next

Work through the practice problems above using the full flowchart for each one. Then continue to Simulation -- the next lesson applies these process skills to a specific problem type. For structured progression beyond individual problems, see the Practice Ladder 1100-1400.