Algorithmic programming

estimating how fast or slow an algorithm is (big-O notation)

arrays: storing and processing a sequence of values

step-by-step execution of the rules of the task in code

brute force - try every possibility

putting data in order, and why that helps

set and dictionary: fast searching and counting

a greedy approach - choose the locally best option

nodes and edges: how to represent a network/connections

fast summation of a range using precomputed sums

two pointers - two indices that walk through an array

halving the range; searching for the smallest valid answer

priority queue/heap - always extract the smallest or the largest

traversing a graph breadth-first and depth-first

colouring a connected region (like the ‘bucket’ in painting)

a tree - a graph with no cycles, a root and children

working with bits (AND, OR, XOR, shifts)

DP - break the problem into subproblems and remember the solutions

DP over subsets represented by bits

DP over every subinterval of an array

counting numbers in a range with some property, digit by digit

prime numbers, divisibility, modular arithmetic

the shortest path in a graph with edge weights

minimum spanning tree - the cheapest way to connect everything

a structure for merging sets and checking membership

an ordering of tasks that respects dependencies

a binary indexed tree for fast sums and updates

flattening a tree into an array for queries on subtrees

the lowest common ancestor of two nodes in a tree

dynamic programming over the structure of a tree

fast comparison of strings/substrings via hash values

vectors, the cross product, orientation - the foundation of geometry

a segment tree with lazy propagation for range updates

segment trees for large/sparse and 2D ranges

splitting into blocks of about √n for faster queries

jumps by powers of two - the k-th ancestor and LCA

heavy-light decomposition of a tree for queries along a path

recursive splitting of a tree by its centroid

small-to-large: efficient queries on subtrees

sum-over-subsets - DP over all subsets

DP optimisation by splitting (divide & conquer)

convex hull trick / Li Chao for DP optimisation

a moving line that processes events in order

convex hull - the smallest enclosure of a set of points

inclusion-exclusion in counting

max-flow - the greatest possible flow through a network

matching - pairing in a (bipartite) graph

advanced pattern search in text (above the IOI syllabus)

a fast transform for multiplying polynomials (above the IOI syllabus)

winning/losing positions and Grundy numbers (above the IOI syllabus)

fast maximum flow and minimum-cost flow (above the IOI syllabus)

structures that remember past states (versions over time)

statements, implications, and what a valid proof looks like

the basic mathematical language for everything else

relations, equivalences, and partial orders

the greatest common divisor by Euclid’s algorithm

calculating with remainders (like a clock, ‘mod n’)

counting - how many possibilities there are

the sum and product rules, and proof by bijection

true/false logic: AND, OR, NOT

proof by induction, including on a structure

a quantity that does not change - the key to a proof

solving recurrence relations (e.g. T(n))

solving linear recurrence sequences

estimating growth and the Master theorem (divide and conquer)

equations modulo n and fast exponentiation

Dirichlet’s principle - more pigeons than holes

inclusion-exclusion in counting

properties of graphs: degrees, connectivity, colouring

chances, events, and the basic rules

conditional probability, independence, and Bayes’ theorem

generating functions for counting and recurrences

the Chinese remainder theorem and division modulo n

Fermat’s little theorem, Euler’s theorem, φ and the idea of RSA

the mean and the spread of a random variable

how far a random variable deviates from its expectation

a random walk and its properties

fast computation of sequences via matrices

proofs about colouring, matching and Hall’s theorem

a formal proof that an algorithm works correctly