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 organized by area (#include "fft/series.hpp", #include "ds/seg_tree.hpp", compiled with -I src), all inside namespace wala. 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/fft/convolution_mod.test.cpp > submission.cpp
scripts/bundle.py fft/series.hpp ds/seg_tree.hpp   # bundle headers together
scripts/bundle.py --minify fft/series.hpp          # compiler-directed minification
scripts/bundle.py --all                            # pregenerate all headers

The script runs in the repo’s uv project (pyproject.toml / uv.lock, which pin competitive-verifier). To run it offline, first populate the environment with

uv sync

Then, you can run

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

Bump the pinned competitive-verifier by editing rev in pyproject.toml and running

uv lock --upgrade-package competitive-verifier

Library Checker verification

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

# Run verification locally
uv run competitive-verifier oj-resolve --include src verify --exclude third_party \
    --config .competitive-verifier/config.toml > verify_files.json
uv run 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	75.1%	4510 / 6 / 6007
Functions	84.9%	1232 / 0 / 1451
Branches	46.3%	10462 / 0 / 22614
Full report

Library Files

• bit_cast.hpp0.0%
• hash_map.hpp0.0%
• optimize.hpp0.0%
• reverse_comparator.hpp20.0%
• smawk.hpp99.2%
• 🧪 smawk.test.cpp
• tensor.hpp56.0%
• 🧪 tensor.test.cpp
• yc.hpp100.0%

combo_games/

• combo_games/cold_games.hpp0.0%

ds/

• ds/bit.hpp0.0%
• ds/cnt_min.hpp0.0%
• ds/order_statistic.hpp100.0%
• ds/rmq.hpp100.0%
• 🧪 ds/rmq.test.cpp
• ds/seg_tree.hpp76.2%
• 🧪 ds/seg_tree.test.cpp

fft/

• fft/all.hpp100.0%
• fft/ap_sampled_poly.hpp68.6%
• 🧪 fft/ap_sampled_poly.test.cpp
• fft/bm.hpp97.6%
• 🧪 fft/bm.test.cpp
• fft/common.hpp75.0%
• fft/core.hpp99.1%
• 🧪 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.hpp93.9%
• 🧪 fft/poly.test.cpp
• fft/series.hpp78.8%
• 🧪 fft/series.test.cpp
• fft/series_core.hpp72.8%
• 🧪 fft/test_util.test.hpp

fft/engines/

• fft/engines/algebras.hpp54.5%
• 🧪 fft/engines/algebras.test.cpp
• fft/engines/crt.hpp96.1%
• fft/engines/ntt.hpp100.0%
• fft/engines/real.hpp96.0%
• fft/engines/split.hpp97.5%

geometry/

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

graph/

• graph/make_st_dag.hpp97.8%
• graph/mcmf.hpp0.0%
• graph/spqr_tree.hpp94.8%
• 🧪 graph/spqr_tree.test.cpp

linalg/

• linalg/char_poly.hpp62.3%

nt/

• nt/dirichlet_series.hpp77.6%
• 🧪 nt/dirichlet_series.test.cpp
• nt/jacobi.hpp0.0%
• nt/lattice_cnt.hpp92.7%
• 🧪 nt/lattice_cnt.test.cpp

num/

• num/fraction.hpp0.0%
• num/linear_fn.hpp100.0%
• 🧪 num/linear_fn.test.cpp
• num/mat.hpp93.8%
• num/modnum.hpp71.3%
• 🧪 num/modnum.test.cpp
• num/nim_prod.hpp33.3%
• num/pairnum.hpp0.0%
• num/quaternion_hurwitz.hpp0.0%
• num/trunc_series.hpp86.7%

seq/

• seq/alphabetic_huffman_code.hpp100.0%
• 🧪 seq/alphabetic_huffman_code.test.cpp
• seq/cartesian_tree.hpp93.9%
• 🧪 seq/cartesian_tree.test.cpp
• seq/manacher.hpp50.0%
• seq/perm_tree.hpp95.2%
• 🧪 seq/perm_tree.test.cpp
• seq/suffix_array.hpp75.2%

tree/

• tree/lct.hpp0.0%
• tree/level_ancestor.hpp78.1%
• tree/static_tree.hpp66.4%
• tree/top_tree.hpp76.1%

Verification Files

verify/

• verify/min_plus_convolution_convex_arbitrary.test.cpp

verify/ds/

• verify/ds/point_add_range_sum.test.cpp
• verify/ds/point_set_range_composite.test.cpp
• verify/ds/range_affine_point_get.test.cpp
• verify/ds/range_affine_range_sum.test.cpp
• verify/ds/staticrmq.test.cpp

verify/fft/

• verify/fft/composition_of_formal_power_series.test.cpp
• verify/fft/composition_of_formal_power_series_large.test.cpp
• verify/fft/convolution_mod.test.cpp
• verify/fft/convolution_mod_1000000007-crt.test.cpp
• verify/fft/convolution_mod_1000000007-fft_split.test.cpp
• verify/fft/convolution_mod_large-crt.test.cpp
• verify/fft/exp_of_formal_power_series.test.cpp
• verify/fft/inv_of_formal_power_series.test.cpp
• verify/fft/kth_term_of_linearly_recurrent_sequence.test.cpp
• verify/fft/log_of_formal_power_series.test.cpp
• verify/fft/multipoint_evaluation.test.cpp
• verify/fft/polynomial_interpolation.test.cpp
• verify/fft/polynomial_taylor_shift.test.cpp
• verify/fft/pow_of_formal_power_series.test.cpp
• verify/fft/shift_of_sampling_points_of_polynomial.test.cpp

verify/geometry/

• verify/geometry/sort_points_by_argument.test.cpp

verify/graph/

• verify/graph/biconnected_components-spqr.test.cpp
• verify/graph/st_numbering.test.cpp
• verify/graph/three_edge_connected_components-spqr.test.cpp
• verify/graph/tree_decomposition_width_2-spqr.test.cpp
• verify/graph/two_edge_connected_components-spqr.test.cpp

verify/linalg/

• verify/linalg/characteristic_polynomial.test.cpp

verify/nt/

• verify/nt/dirichlet_convolution_and_prefix_sums.test.cpp
• verify/nt/dirichlet_inverse_and_prefix_sums.test.cpp
• verify/nt/sum_of_totient_function.test.cpp

verify/num/

• verify/num/nim_product_64.test.cpp

verify/seq/

• verify/seq/cartesian_tree.test.cpp
• verify/seq/common_interval_decomposition_tree.test.cpp
• verify/seq/enumerate_palindromes.test.cpp
• verify/seq/number_of_substrings.test.cpp
• verify/seq/suffixarray.test.cpp

verify/tree/

• verify/tree/dynamic_tree_subtree_add_subtree_sum.test.cpp
• verify/tree/dynamic_tree_vertex_add_subtree_sum.test.cpp
• verify/tree/incremental_minimum_spanning_forest.test.cpp
• verify/tree/jump_on_tree-level_ancestor.test.cpp
• verify/tree/lca-static_tree.test.cpp