C++ problem-solving patterns.

A pattern is a compact description of the state that removes repeated work. “Contiguous and longest” suggests a window because the useful state has two moving boundaries. “Minimum steps with unweighted edges” suggests BFS because the queue processes vertices in nondecreasing distance. The chapter links below explain that connection, establish the invariant, and then implement it in C++.

Chapters

Recognition map

Use the statement and constraints to narrow the candidates. The signal is not a proof. It tells you which invariant to test against the examples and constraints.

From direct solution to maintained state

1. Read constraints first. A quadratic loop can be correct for n ≤ 2,000 and impossible for n = 200,000.
2. Write the direct operation count. “For each right endpoint, I scan every earlier value” is more useful than only writing O(n²).
3. Name the repeated query. Examples: “Have I seen this complement?”, “What is the largest live value?”, or “Which prefixes differ by k?”
4. Choose state supporting that query. Hash table, deque, heap, bitset, tree, or DP table.
5. State the invariant before implementation. Every movement or update must restore it.
6. Count how often each item changes state. This establishes the actual complexity of windows, stacks, deques, and amortized structures.
7. Test the direct and optimized versions together. Randomized differential tests are especially effective for prefix counts, trees, and range structures.

C++ mechanics that affect otherwise-correct algorithms

Promote before arithmetic

Casting after a signed overflow does not repair it. At least one operand must be widened before the operation.

wide_arithmetic.cpplong long product = 1LL * left * right;
long long distance = static_cast<long long>(a) + b;
int middle = low + (high - low) / 2;

Use half-open ranges consistently

The chapters use [begin, end). Length is end - begin, an empty range has equal endpoints, and adjacent ranges compose without adding or subtracting one.

half_open.cpplong long range_sum(
    const std::vector<long long>& prefix,
    std::size_t begin,
    std::size_t end
) {
    return prefix[end] - prefix[begin];
}

Fast input without mixed buffering

For input-heavy programs, detach C++ streams from the C stdio buffers and stop flushing cout before each read. After doing this, keep all input on cin. Do not mix it with scanf.

io_setup.cpp#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int count;
    std::cin >> count;
    // Use '\n' for ordinary line endings; std::endl also flushes.
}