Advanced Algorithms in Competitive Programming Problems

This repository is a curated collection of solutions developed for the course Advanced Algorithms in Competitive Programming Problems.

Each problem is organized as a self-contained project, including implementation, test cases, and (when relevant) detailed algorithmic documentation.

The repository emphasizes not only correct solutions, but also modeling, reduction techniques, and reproducible engineering structure.

---

Highlights

This repository demonstrates:

• advanced graph algorithms (SCC, MST, matching, connectivity)
• geometric algorithms (sweep line, spatial reasoning)
• advanced data structures (segment tree, splay tree, AVL)
• algorithmic design techniques (greedy, binary search, parametric search)
• mathematical methods (number theory, Stern–Brocot, Diophantine equations)

Several problems involve multi-stage reductions, transforming complex problem statements into classical algorithmic formulations.

---

Repository Goals

This repository is intended to serve as:

• a structured archive of course problem solutions
• a technical portfolio of algorithmic modeling and implementation
• a reference for clean project organization around competitive programming problems

The focus is on:

• truthful documentation
• clear engineering structure
• reproducibility of results

---

Quick Start

Requirements

• Python 3
• GCC or Clang
• GNU Make

On Linux or WSL, build and test all 17 main problems with:

make
make test
make clean

The root workflows continue through every problem, print a per-problem result, and return a nonzero status if any build or test fails. Archived problems are available separately through make archive, make archive-test, and make archive-clean.

To build and test one problem:

make -C apd/src
make -C apd/src test

The per-problem Makefiles accept compiler overrides such as make -C apd/src CC=clang.

The root-level Windows wrappers require Python 3, GNU Make available as make, and GCC or Clang available on PATH. They invoke the same Python orchestration scripts as the Linux workflow, and those scripts use GNU Make internally.

With those tools installed, use:

build_all.bat
test_all.bat

If GNU Make is not available, individual problems can still be built by running build.bat from the problem's src\ directory. After building, run run_tests.bat from that problem's tests\ directory; the test wrapper requires Python 3.

The included tests verify the provided test cases using token-based output comparison. They make the preserved submissions reproducible; they do not prove exhaustive algorithm correctness.

---

Repository Structure

Most problem directories follow a consistent layout:

• problem/ — original problem statement
• src/ — final implementation
• tests/ — sample inputs, outputs, and automated test scripts
• docs/ — algorithm explanation and annotated material

Some problems additionally include:

• solutions/ — alternative implementations or complexity variants
• versions/ — historical or intermediate solution versions
• templates/ — reusable components

Additional problems with lighter documentation are stored in:

• archive/

---

Suggested Entry Points

If you are reviewing this repository, the following problems are good starting points:

• tas — geometry + data structures (sweep line + AVL + union-find)
• xap — problem reduction to bipartite matching / minimum vertex cover
• bur — multi-stage modeling with multiple implementations
• phr — mathematical reconstruction using Stern–Brocot trees

---

Problem Index

The main collection contains 17 documented problems.

Problem	Theme	Core Techniques	Level
apd	compatible set under conflicts	parameterized reduction, branching, vertex cover duality	Advanced
bur	sequential voting game	backward analysis, k-smallest maintenance, order statistics	Advanced
cat	grid travel optimization	geometric reformulation, sparse graph, Dijkstra	Core
fal	falling time under deletions	reverse processing, union-find, offline connectivity	Core
grr	alternating reachability	SCC compression, DAG reasoning	Core
luc	minimizing max wins	graph modeling, binary search, augmenting paths	Core
paw	equal-length cycle validation	Tarjan BCC, structural graph classification	Core
phr	rational reconstruction	interval reconstruction, Stern–Brocot, path LCP	Advanced
ppm	prefix-free string set	greedy tree expansion, heap optimization	Core
pss	interval distinct value maximization	sweep line, contribution transfer, lazy segment tree	Advanced
rai	time-dependent reward ordering	linear functions, splay tree, lazy propagation	Advanced
sli	minimum-effort ordering	greedy direction choice, constructive optimization	Core
sus	signalling cost minimization	Dijkstra, MST, multi-source shortest paths	Core
tas	geometric connectivity	sweep line, AVL tree, union-find	Advanced
tpe	substring periodicity	divisor enumeration, rolling hash	Core
tuv	tree detection counting	tree decomposition, interval counting, binary search	Advanced
xap	radar removal	geometric reduction, bipartite matching, vertex cover	Advanced

---

Archive

The archive/ directory contains additional course problems preserved for completeness.

These problems:

• follow the same core structure (problem/, src/, tests/)
• preserve their original implementations and reproducible sample-test workflows
• typically have lighter documentation or simpler structure

See the archive index.

---

How to Use This Repository

Browse a problem

Open any problem directory (e.g., tas/, phr/, bur/).

Start with:

• README.md — overview
• docs/ — explanation and annotated material
• src/ — final implementation
• tests/ — verification

---

Build

From a problem directory, use make -C src on Linux or WSL. See its src/README.md for Linux and Windows details.

---

Test

From a problem directory, use make -C src test on Linux or WSL. The tests/README.md describes the shared runner, wrappers, and comparison semantics.

---

Documentation Style

This repository follows an algorithm-explanation-oriented documentation style.

Each problem is documented to highlight:

• the modeling step
• the key reduction or structural insight
• the final algorithm
• implementation reasoning

The goal is to preserve how the solution is derived, not only the final code.

---

Notes

• Directory names use the original three-letter problem abbreviations from the course
• Not all problems have the same level of documentation
• Structure consistency is prioritized across all problems

---

Status

This repository preserves a structured collection of course solutions, including:

• 17 main documented problems
• 4 additional archived problems
• reproducible build and sample-test workflows