CUCaTS logo of a white cat in ASCII art CUCaTS

Competitive Programming

Read the constraints before choosing an algorithm. They limit both the work and memory your solution can use.

Reading the bound

Small bounds may allow exhaustive search. Larger bounds often need sorting, dynamic programming or more efficient query structures. These are hints, not guarantees about the intended solution.

Check limits across all test cases as well as within one case. Runtime also depends on the language, data layout and judge hardware.

Decomposition

  • Square-root decomposition splits work into blocks.
  • Fenwick trees handle prefix sums; segment trees support a broader range of associative operations.
  • Sparse tables support static range queries, with constant-time queries for idempotent operations such as minimum.
  • Heavy-light and centroid decomposition help reduce tree queries to smaller problems.

Choose the simplest structure that meets the bound.

Amortisation and offline reasoning

An expensive operation can still be efficient overall if it happens rarely. Small-to-large merging uses this idea by moving elements into progressively larger sets.

If queries can be answered offline, sorting and sweeping may replace a more complex online structure. Persistent structures keep earlier versions available for queries.

The shapes worth recognising

For dynamic programming, define the state and transition before looking for an optimisation. Techniques such as divide-and-conquer optimisation require specific conditions.

Matching and selection problems may reduce to flow. String matching may use prefix functions, Z-functions or Aho–Corasick, depending on whether there is one pattern or many.

Constant factors that change the verdict

Once the complexity fits, check memory use, input handling and recursion depth. Flat storage and bitsets can help some workloads. Measure before adding low-level optimisations.

Practice that works

Try a problem before reading its editorial. Afterwards, implement the solution yourself. Compare against brute force on small generated inputs to catch mistakes.

A solution checklist

  1. State what the input represents and what the output must satisfy.
  2. Choose a representation and identify an invariant.
  3. Explain why each transition or greedy choice preserves correctness.
  4. Bound the time and memory over the whole input.
  5. Check edge cases before submitting.

A plausible pattern from small inputs is a starting point, not a proof.

Common implementation failures

Check whether arithmetic needs a wider type before multiplication happens. Confirm whether intervals are closed or half-open. Reset state between test cases and distinguish unreachable states from valid zero values.

Recursion depth can depend on input shape. A tree-shaped input can still be a long chain. Sorting comparators must satisfy the ordering rules expected by the language.

Reviewing a contest

Separate an algorithm mistake from an implementation mistake or a time-management mistake. Re-solve problems you nearly finished before moving to entirely new material. Keep short notes on the missing idea rather than copying a full editorial.

For a difficult optimisation, keep the slow correct version as a comparison tool on small inputs. See Testing and Profiling.

Practice resources