Learn the main ideas that form the backbone of contest problem solving. This course covers dynamic programming, number theory, graph traversals, shortest paths, geometry, scanline, basic game theory, and more advanced forms of binary search.
Dynamic Programming with Path Restoring (DP with Path Restoring)
Primality testing in $O(\sqrt{n})$, Sieve of Eratosthenes, Factorization in $O(\sqrt{n})$
In this section we will study checking a number for primality, how to find all divisors of a number up to $\sqrt{N}$ and factoring a number into prime numbers
Learn about sieve of Eratosthenes
DFS, BFS, Visit components, 2-coloring the graph, Cycle detection (in oriented and non-oriented), Topological Sorting
Learn Depth-First Search (DFS)
Learn Breadth-First Search (BFS)
Bipartiteness check
Finding connected components
Topological Sort
Dijkstra Algorithm, Bellman-Ford, Floyd Warshall
Dijkstra - finding shortest paths from given vertex
Floyd-Warshall
Bellman–Ford algorithm
Game Theory - Basics
Learn basics of game states
Introduction to Geometry
Signed area of a triangle
Basic Geometry
Harder geometry problems
Binary Search on Answer, Binary Search on floating numbers, Ternary Search, 2-pow Binary Search
Searching over the possible values of an integer answer, using a fast feasibility check and monotonicity to halve the range each step. Applied to a production-scheduling problem where machines run in parallel.
The continuous variant of binary search on answer: instead of stopping when the borders meet, run a fixed number of iterations to shrink the closed real segment around the optimum.
The optimization sibling of binary search: when the function goes down and then up, or up and then down, two probes at the one-third and two-third marks let you throw away the wrong outer piece each step and close in on the extremum.
Binary search by powers of two