Competitive Programming

Online judges and time limits, prefix sums, two pointers, binary search on the answer, greedy, DP and graphs with the STL, and contest math.

1
Contests, judges and time limits
How an online judge checks your program, the verdicts it gives, fast input in C++, and how to tell from n whether an idea is fast enough.
2
Prefix sums
One pass of preparation answers every range-sum question in O(1): the most useful trick in contests.
3
Two pointers and sliding windows
Two indexes that only move forward turn many O(n²) searches into O(n): pair sums in a sorted array, and windows.
4
Binary search on the answer
When checking a guess is easy and the answer is a number, search for the best answer with binary search.
5
Sorting first, then greedy
Sort pairs, choose a comparator, and let the order make a greedy choice correct.
6
Dynamic programming in contests
Counting ways modulo 10⁹+7, the longest increasing subsequence, and the 1D knapsack: the DP patterns that keep coming back.
7
Graphs with the STL
Adjacency lists as vector<vector<int>>, BFS with queue, shortest paths on a grid, and Dijkstra with a priority_queue.
8
Math for contests
Modular arithmetic, fast power, gcd and lcm, and a sieve with vector<bool>: the number theory every contestant uses.