Week 1 - Warm-up
As a warm-up, let's try to solve some easiest problems this weekend. They require almost no algorithmic techniques and you should be able to spend less than 10 minutes from the instant you start reading a problem statement to the point you submit your codes and get an "Accepted". (When you are proficient enough, the time consumed can be even less than 5 minutes for some problems.) Usually there will be at least 1 easy problem in every ACM programming contest; sometimes a rather long problem may turn out to be very easy.
Examples:
https://vjudge.net/contest/168739. Password: hkuacm.
Week 2 - Dynamic Programming
Let's start from
dynamic programming (DP). In general, solving a problem by dynamic programming consists of 2 parts: designing states and finding the transition function.
This week we cover only the most basic DP problems. Actually DP may take so many forms, including interval DP, digit DP, DP on trees, etc.. If you are eager to learn more, you are encouraged to search for these keywords online, which we will cover in the future.
Recommended learning material: Section 1, The Hitchiker's Guide to Programming Contests (You can find it at
Utilities.)
Training:
https://vjudge.net/contest/208188.
Week 3 - Search & Topological Sort
This week, let's learn
depth-first search (DFS),
breadth-first search (BFS) and
topological sort.
Recommended learning material: Section 2.1 & 2.2, The Hitchiker's Guide to Programming Contests (You can find it at
Utilities.)
Both DFS and BFS have their own strengths and are thus used to solve different types of problems. Performing a DFS is somewhat straightforward as you don't need to remember all the states (nodes) you have seen but have yet to explore, because you always focus on the current node you are visiting and go back until there is no way ahead; a DFS is usually implemented via a
backtracking. However, by a BFS you will be able to find the least number of steps (shortest path on an unweighted graph) to reach a node, at the cost of building up a
queue (you can either simulate it with an array or use std::queue).
Sometimes both DFS and BFS are suitable if a problem (or a subtask of some problem) is simple enough.
When the "graph" inside a problem is not that clear, you may have to construct the graph yourself (at least in your mind, not necessarily in your code).
There are many ways to do topological sorting. Besides the one described in the recommended material, another approach is to keep removing vertices with indegree 0 from the graph.
Training:
https://vjudge.net/contest/209520.
Week 4 - Shortest Path
This week, let's start graph theory from
shortest path problems.
Recommended learning material: Section 2.3 - 2.5, The Hitchhiker's Guide to Programming Contests (You can find it at
Utilities.)
Before solving any problem in graph theory, we have to know how to represent a graph in memory. There are two popular means:
adjacency matrix and
adjacency list. As an adjacency matrix requires O(N^2) space where N is the number of vertices, when the graph is really large (for example, N = 100,000), adjacency list is the only choice.
There are 3 widely-used shortest path algorithms: Dijkstra, Bellman-Ford and Floyd-Warshall. Denote the number of vertices and edges as N and M, respectively.
Dijkstra's algorithm runs in O(N^2) time and can be optimized to O(MlogN) or O(MlogM) (depending on the implementation) with data structures such as heap.
Bellman-Ford algorithm runs in O(NM) time, but is able to
detect negative cycles; an improvement of it, called
SPFA, is also used in contests occasionally. While both Dijkstra and Bellman-Ford are
single-source shortest path algorithms,
Floyd-Warshall algorithm is an
all-pair shortest path algorithm, with running time O(N^3). (You may find the code of Floyd-Warshall algorithm surprisingly short, which has only 3 nested for loops.)
As we grasp more and more tools, some problems may appear to have more than one solution.
Training:
https://vjudge.net/contest/211037.
Week 5 - Minimum Spanning Tree & Disjoint-Set Data Structure
This week, let's learn
minimum spanning tree (MST) algorithms and
disjoint-set data structure.
Recommended learning material: Section 2.6 & 6.3, The Hitchhiker's Guide to Programming Contests (You can find it at
Utilities.)
There are 2 popular minimum spanning tree algorithms: Prim and Kruscal.
Prim's algorithm resembles Dijkstra's algorithm a lot, taking O(N^2) time or O(MlogN) (O(MlogM)) time with the help of some data structure. (So be sure you can distinguish between Prim and Dijkstra so as not to implement a wrong one when writing a program!)
Kruscal's algorithm requires a data structure to support
disjoint set union (DSU) operations. Upon sorting the edges, it can run in O(M*alpha(N)) time, where alpha is the inverse Ackermann function, an extremely slow-growing function. Note that the disjoint-set data structure is of independent interest as it can be used in many scenarios.
Training:
https://vjudge.net/contest/212260.
Week 6 - Bipartite Matching & Flow
This week, let's learn
bipartite matching,
maximum flow and
minimum cost maximum flow.
Recommended learning material: Section 2.7 - 2.10, The Hitchhiker's Guide to Programming Contests (You can find it at
Utilities.)
The bipartite matching problem can be solved by
Hungarian algorithm, which obtains a maximum matching by keeping finding
alternating paths.
There are many prevailing algorithms to solve the maximum flow problem, most of which depending on keeping finding
augmenting paths until the sink is not reachable from the source in the
residual graph. The
max-flow min-cut theorem widens the application of flow algorithms, as it turns out that many problems can be modelled as finding the minimum cut of a graph. In some problems, construction of the graph can be very tricky. When edges of a graph are associated with different costs per unit flow, the problem becomes a minimum cost maximum flow problem. This model enables us to solve more tasks, while the algorithm should also be modified compared to max-flow algorithms.
It should be noted that bipartite matching can be reduced to (solved by) max flow. However, to implement Hungarian algorithm is easier than to implement flow algorithms, making it usually unnecessary to solve bipartite matching via max flow.
It is worth mentioning that besides the max-flow min-cut theorem, many theoretical results in combinatorics (in particular, in graph theory) will be useful in programming contests. For example,
Kőnig's theorem.
Training:
https://vjudge.net/contest/212973.
Week 7 - More about Dynamic Programming
This week, let's learn more about DP.
(No recommended learning material. Please find detailed discussions online if you have trouble solving the problems.)
There are many types of DP, including
interval DP,
DP on trees,
digit DP,
subset DP, and many others. Complicated as they may seem, advanced DP problems are solved in the same framework: (a) defining states, (b) finding the transition function and (c) resolving base cases. You may find the states of some DP problems particularly complicated yet interesting.
Training
https://vjudge.net/contest/213525.
Week 8 - KMP & Trie
This week, let's start to learn algorithm about strings: Knuth-Morris-Pratt (
KMP) algorithm and
trie.
Recommended learning material:
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
Section 6.4, The Hitchhiker's Guide to Programming Contests (You can find it at
Utilities.)
https://en.wikipedia.org/wiki/Trie.
KMP algorithm searches for occurrences of a pattern string in a given text in linear time. The key point is an array denoting longest prefix-suffix at each position (the array b[] in the link above; also called
next,
fail,
lps, etc. in other tutorials), which is smartly utilized when mismatching occurs. Trie (also called
prefix tree) is a tree structure that collects and processes a set of words.
Training:
https://vjudge.net/contest/214504.
Week 9 - AC Automaton
This week, let's learn Aho-Corasick algorithm.
Recommended learning material:
https://web.stanford.edu/class/cs166/lectures/02/Small02.pdf
https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
Aho-Corasick algorithm, which locates a set of pattern strings in a given text simultaneously, looks like a combination of KMP algorithm and trie. To construct an
Aho-Corasick automaton (AC automaton), you need to construct a trie first, and then specify what to do when mismatching happens.
Training:
https://vjudge.net/contest/215638.
Week 10 - Suffix Array
This week, let's learn
suffix array.
Recommended learning material:
http://web.stanford.edu/class/cs97si/suffix-array.pdf.
Suffix array is another powerful tool for string problems. The idea and implementation of it are really, really tricky. Technically speaking we use fast algorithms to sort all the suffixes of a (long) given string and compute longest common prefixes between suffixes.
Training:
https://vjudge.net/contest/216861
Week 11 - Segment Tree & Binary Indexed Tree
This week, let's learn segment tree and binary indexed tree (BIT).
Recommended learning material:
https://en.wikipedia.org/wiki/Fenwick_tree
https://en.wikipedia.org/wiki/Fenwick_tree
https://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/
https://www.iarcs.org.in/inoi/online-study-material/topics/range-queries.php
Segment trees are considerably widely used in programming contests. A segment tree is a data structure that supports fast operations on a sequence of elements. The operations often appear to be simple (for example, to report the maximum element in a subinterval), whose naïve implementation usually costs linear time. They can be improved by segment trees to (poly)logarithmic time, while making some constant-time operations (for example, to modify an entry in the sequence) also cost (poly)logarithmic time as a trade-off.
For some problems requiring
single point updates and interval queries, binary indexed trees, or
Fenwick trees, can be utilized instead of segment trees, as the implementation of a binary indexed tree is usually shorter than that of a segment tree. For problems requiring
interval updates and single point queries, sometimes a binary indexed tree will also work, but in a trickier way. However, for problems involving
interval updates and interval queries, usually a segment tree equipped with
lazy propagation is a must.
There is also a 2D version of binary indexed trees (and of segment trees, if it is not extremely complicated for you). Segment trees and binary indexed trees are really versatile and ambitious students are strongly encouraged to search for more related problems to solve in order to discover more applications of these data structures.
Note that usually every BIT problem can be solved by segment trees. So if you have trouble applying BIT smartly, you can try to solve some of the BIT problems in the training problem set using segment trees, in a relatively straightforward way.
Training:
https://vjudge.net/contest/218152.
Week 12 - Mathematics
This week, let's learn
mathematics!
(No recommended learning material. Please find detailed discussions online if you have trouble solving the problems.)
A number of topics ranging from the most basic things to very difficult ones are covered in this week's training, including:
-
Greatest common divisor (GCD):
Euclidean algorithm
-
Binomial coefficient
-
Fast exponentiation (for numbers / matrices)
-
Extended Euclidean algorithm
-
Modular multiplicative inverse (solved by
Fermat's little theorem and fast exponentiation, or occasionally, extended Euclidean algorithm)
-
Gaussian elimination
-
Burnside's lemma /
Pólya enumeration theorem (advanced)
-
Euler's totient function (
Euler's phi function) (advanced)
-
Chinese remainder theorem (advanced)
-
Lucas's theorem (advanced)
To master the techniques involved, you need different levels of knowledge in number theory, linear algebra and abstract algebra.
Training:
https://vjudge.net/contest/219295.
Week 13 - Computational Geometry
This week, let's learn computational geometry.
Recommended learning material:
https://en.wikipedia.org/wiki/Graham_scan.
Like last week's discrete math problems (most of which are about number theory), geometry problems can also be either basic or challenging. In general, some geometric objects are given and you need to perform some tasks by analytic geometric techniques. Sub-topics in computational geometry may include
- Properties of
cross product and
dot product (you will need to manipulate vectors (the mathematical object, not the container in C++ or Java) very often)
-
Intersection of objects (2 lines, 2 line segments, or a line and a line segment, a line and a circle, etc.)
-
Distance between objects (2 points, a point and a segment, etc.)
-
Area of objects (e.g. polygons)
-
Convex hull
In particular, the convex hull of N points in a 2D plane can be found by
Graham scan in O(NlogN) time.
To achieve high precision and high speed, you may want to avoid floating-point computation as much as possible and use integers instead. This principle applies in not only geometry problems but also every part of programming.
Many excellent contestants prepare robust templates that deal with different fundamental geometry tasks (e.g. a function that returns the intersection of two given lines, then a function that returns the intersection of two given line segments, then a function that returns the intersections of two given circles).
The problems are usually set in a 2D world, while there are occasionally some problems dealing with 3D objects. Needless to say, 3D problems are (generally) more difficult than 2D problems.
Training:
https://vjudge.net/contest/220819.
Week 14 - Sparse Table & More on Graph Theory
This week, let's learn
sparse table and some more topics in graph theory.
1. Sparse Table
This is a general technique similar to segment trees that can reduce the cost of some tasks from O(N) to O(logN) (and sometimes, to O(1)). The most popular applications of sparse tables might be
range minimum/maximum queries (RMQ) and
lowest common ancestor (LCA) on trees. It is worth mentioning that LCA queries can actually be reduced to RMQs.
Recommended Learning Material:
Sparse Table, RMQ;
Sparse Table, RMQ and LCA (Section "RMQ - Sparse Table (ST) algorithm", "LCA - Another easy solution in <O(N logN, O(logN)>", and "LCA - Reduction from LCA to RMQ").
2. Connectivity-related problems
We are often interested in
strongly connected components (SCC) in directed graphs, and
cut edges (also called
bridges) and
cut vertices (also called
articulation points) in undirected graphs. A series of DFS-based algorithms due to
Tarjan can be used to find them in a given graph in linear time.
Kosaraju's algorithm is another way to find SCCs. To find SCCs, you can use either Tarjan's algorithm or Kosaraju's algorithm.
Recommended Learning Material:
Strongly Connected Component,
Strongly Connected Component,
Cut Edge,
Cut Vertex.
3. Application of shortest path algorithms and max flow algorithms
There are some fascinating applications of graph algorithms. Some problems seem to have nothing to do with shortest paths or flows, but turn out to be solvable by these classical techniques by smart modeling. If you haven't heard of the following problems before, you can think about how problem F, G, H and I in this week's training can be solved by graph algorithms :)
Recommended Learning Material:
System of Difference Constraints,
Minimum Path Cover,
Maximum Weight Closure,
Densest Subgraph.
Training:
https://vjudge.net/contest/222496.
Week 15 - Heavy-Light Decomposition & Centroid Decomposition
This week, let's learn something challenging:
heavy-light decomposition (HLD) and
centroid decomposition.
(These topics are so advanced that you do not have to learn them unless you are aiming at a gold medal in Asia Regional Contests or a ticket for World Finals.)
Recommended learning material:
https://www.geeksforgeeks.org/heavy-light-decomposition-set-1-introduction/
https://www.geeksforgeeks.org/heavy-light-decomposition-set-2-implementation/
https://www.geeksforgeeks.org/centroid-decomposition-of-tree/
Heavy-light decomposition is a technique to make segment trees (or sometimes, binary indexed trees) work on trees, not only on chains (segments). The decomposition lists all the vertices in a given tree onto a line such that every simple path in the tree can be represented as the union of O(logN) intervals.
Centroid decomposition is another divide-and-conquer technique on trees.
Centroids of subtrees are recursively found so that after removing the centroid (a vertex), the largest remaining connected component is as small as possible. It can be shown that the depth of the recursion is O(logN). Hence to apply centroid decomposition you also need to know how to find the centroid of a tree; this is also included in this week's training as an independent problem.
Training:
https://vjudge.net/contest/224050.
