Skip to content

Foundations -> Complexity And Invariants

Reasoning tools for contests: estimate time honestly, define loop invariants, and learn to justify greedy and implementation choices before coding.

  • Topic slug: foundations/complexity-and-invariants
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 3
  • Repo companion pages: 1
  • Curated external problems: 8

Microtopics

  • asymptotic-estimation
  • worst-case-thinking
  • amortized-analysis
  • loop-invariants
  • exchange-arguments
  • counterexamples
  • proof-by-induction

Learning Sources

Source Type
MIT 6.006 Course
Principles of Algorithmic Problem Solving Reference
Competitive Programmer's Handbook Reference

Practice Sources

Source Type
CSES Problem Set Practice
USACO contest archive Practice

Repo Companion Material

Material Type
Foundations cheatsheet quick reference

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Collecting Numbers CSES Easy - Proof-Heavy; Implementation-Heavy Permutations; Index Mapping; Loop Invariants Permutations; Position-Mapping; Positions Good practice for turning a process into a simple invariant over positions.
Missing Coin Sum CSES Medium - - - Sorting Classic smallest-unreachable-sum invariant.
Stick Lengths CSES Medium - - - Median; Absolute-Deviation; Sorting Shows why the median is optimal.
Collecting Numbers II CSES Hard - - - Updates; Swap-Delta Same invariant, but maintained under swaps.

Variants

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Distinct Values Subarrays CSES Medium - Proof-Heavy; Implementation-Heavy Two Pointers; Frequency Counts; Subarray Reasoning Two-Pointers; Distinctness; Subarrays A good bridge from basic sliding windows to counting arguments based on a maintained invariant.
Playlist CSES Medium - Proof-Heavy; Data-Structure-Heavy Two Pointers; Hash Maps; Amortized Analysis Sliding-Window; Distinctness; Amortized-Analysis A neat amortized two-pointer invariant problem with a clean linear-time proof.

Classics

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Towers CSES Medium - Proof-Heavy; Data-Structure-Heavy Greedy Reasoning; Binary Search; Sorted Containers Patience-Sorting; Lower Bound A classic proof-oriented greedy where the invariant is the sorted tower tops.

Theory / Course

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Increasing Array CSES Easy - Proof-Heavy; Greedy-Heavy Greedy Reasoning; Prefix Invariants; Arrays Prefix-Maintenance; Prefix-Max A compact proof-by-invariant problem that rewards understanding why the greedy step is optimal.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
FACTORYMACHINES Factory Machines secondary medium answer binary search; monotone feasibility; production rate accumulation Note Code
INCREASINGARRAY Increasing Array primary easy loop invariant scan; greedy repair; running maximum maintenance Note Code
MOVIEFESTIVAL Movie Festival secondary easy finish-time sorting; interval scheduling; exchange argument greedy Note Code

Regeneration

python3 scripts/generate_problem_catalog.py