ecnerwala’s Competitive Programming Book

This is my library of reference code for competitive programming. The goal is to write generic, fast, and clean algorithm implementations for use in contests like CodeForces or ICPC.

The library lives in src/ as standalone headers (#include "fft.hpp", compiled with -I src). The library requires C++23 (the whole toolchain builds with -std=c++23, e.g. g++ >= 13). Browsable source, verification results, and coverage are hosted at https://ecnerwala.github.io/cp-book/.

Building and testing

cmake -B build && cmake --build build
ctest --test-dir build          # or ./build/tests

Bundling

Unfortunately, some files (e.g. full power series with all fft engines) are too long to fit in CF’s submission limit, so we need to bundle/minify them for submission.

scripts/bundle.py verify/convolution_mod.test.cpp > submission.cpp
scripts/bundle.py fft.hpp seg_tree.hpp     # bundle headers together
scripts/bundle.py --minify fft.hpp         # compiler-directed minification
scripts/bundle.py --all                    # pregenerate all headers

To run the bundler offline, first initialize the UV cache by running

uv sync --script scripts/bundle.py

Then, you can run

UV_OFFLINE=1 scripts/bundle.py ...
uv run --offline --script scripts/bundle.py ...

Upgrade the bundler’s lockfile with

uv lock --script scripts/bundle.py --upgrade

(Make sure to rerun the sync afterwards.)

Library Checker verification

verify/ holds Library Checker solutions, verified in CI with competitive-verifier.

# Run verification locally
uvx competitive-verifier oj-resolve --include src verify --exclude third_party \
    --config .competitive-verifier/config.toml > verify_files.json
uvx competitive-verifier verify --verify-json verify_files.json

Contest tooling

contest/ holds standalone tooling for contests: a problem-directory template (Makefile with sanitizers and precompiled headers), a layered .template instantiator (make_prob.py), and a Competitive Companion listener (download_prob.py). See contest/README.md. Contest programs are standalone; vendor book code in as needed (e.g. with scripts/bundle.py).

License and attribution

All code is written by me and CC0 licensed unless otherwise noted in the file. Inspiration is largely drawn from KACTL and other references.

Coverage

	Coverage	Exec / Excl / Total
Lines	63.5%	2866 / 0 / 4515
Functions	91.2%	1089 / 0 / 1194
Branches	72.3%	6911 / 0 / 9558
Full report

Library Files

• alphabetic_huffman_code.hpp100.0%
• 🧪 alphabetic_huffman_code.test.cpp
• bit.hpp0.0%
• bit_cast.hpp0.0%
• bm.hpp97.6%
• 🧪 bm.test.cpp
• cartesian_tree.hpp93.9%
• 🧪 cartesian_tree.test.cpp
• char_poly.hpp62.3%
• cnt_min.hpp0.0%
• dirichlet_series.hpp77.6%
• 🧪 dirichlet_series.test.cpp
• fraction.hpp0.0%
• hash_map.hpp0.0%
• jacobi.hpp0.0%
• lattice_cnt.hpp92.7%
• 🧪 lattice_cnt.test.cpp
• lct.hpp0.0%
• level_ancestor.hpp78.1%
• manacher.hpp50.0%
• mcmf.hpp0.0%
• modnum.hpp57.7%
• 🧪 modnum.test.cpp
• nim_prod.hpp33.3%
• optimize.hpp0.0%
• order_statistic.hpp100.0%
• perm_tree.hpp95.2%
• 🧪 perm_tree.test.cpp
• quaternion_hurwitz.hpp0.0%
• reverse_comparator.hpp20.0%
• rmq.hpp100.0%
• 🧪 rmq.test.cpp
• seg_tree.hpp76.2%
• 🧪 seg_tree.test.cpp
• smawk.hpp99.2%
• 🧪 smawk.test.cpp
• static_tree.hpp66.4%
• suffix_array.hpp75.3%
• tensor.hpp56.0%
• 🧪 tensor.test.cpp
• top_tree.hpp0.0%
• yc.hpp100.0%

combo_games/

• combo_games/cold_games.hpp0.0%

fft/

• fft/all.hpp100.0%
• fft/ap_sampled_poly.hpp68.6%
• 🧪 fft/ap_sampled_poly.test.cpp
• fft/common.hpp75.0%
• fft/core.hpp98.8%
• 🧪 fft/core.test.cpp
• fft/engine.hpp75.0%
• 🧪 fft/engines.test.cpp
• fft/multiply.hpp100.0%
• fft/online.hpp93.3%
• 🧪 fft/online.test.cpp
• fft/poly.hpp92.9%
• 🧪 fft/poly.test.cpp
• fft/series.hpp84.9%
• 🧪 fft/series.test.cpp
• fft/series_core.hpp72.8%
• 🧪 fft/test_util.test.hpp

fft/engines/

• fft/engines/algebras.hpp64.6%
• 🧪 fft/engines/algebras.test.cpp
• fft/engines/crt.hpp92.9%
• fft/engines/ntt.hpp100.0%
• fft/engines/real.hpp95.7%
• fft/engines/split.hpp93.6%

geometry/

• geometry/point.hpp17.6%
• geometry/point3d.hpp0.0%

graph/

• graph/make_st_dag.hpp97.8%

Verification Files

verify/

• verify/cartesian_tree.test.cpp
• verify/characteristic_polynomial.test.cpp
• verify/common_interval_decomposition_tree.test.cpp
• verify/composition_of_formal_power_series.test.cpp
• verify/composition_of_formal_power_series_large.test.cpp
• verify/convolution_mod.test.cpp
• verify/convolution_mod_1000000007-crt.test.cpp
• verify/convolution_mod_1000000007-fft_split.test.cpp
• verify/convolution_mod_large-crt.test.cpp
• verify/dirichlet_convolution_and_prefix_sums.test.cpp
• verify/dirichlet_inverse_and_prefix_sums.test.cpp
• verify/enumerate_palindromes.test.cpp
• verify/exp_of_formal_power_series.test.cpp
• verify/inv_of_formal_power_series.test.cpp
• verify/jump_on_tree-level_ancestor.test.cpp
• verify/kth_term_of_linearly_recurrent_sequence.test.cpp
• verify/lca-static_tree.test.cpp
• verify/log_of_formal_power_series.test.cpp
• verify/min_plus_convolution_convex_arbitrary.test.cpp
• verify/multipoint_evaluation.test.cpp
• verify/nim_product_64.test.cpp
• verify/number_of_substrings.test.cpp
• verify/point_add_range_sum.test.cpp
• verify/point_set_range_composite.test.cpp
• verify/polynomial_interpolation.test.cpp
• verify/pow_of_formal_power_series.test.cpp
• verify/range_affine_point_get.test.cpp
• verify/range_affine_range_sum.test.cpp
• verify/shift_of_sampling_points_of_polynomial.test.cpp
• verify/sort_points_by_argument.test.cpp
• verify/st_numbering.test.cpp
• verify/staticrmq.test.cpp
• verify/suffixarray.test.cpp
• verify/sum_of_totient_function.test.cpp