Training

• 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 ", 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.
  

• Time: 1:30 pm - 2:30 pm, 2 March.
  Venue: CB 313.
  Slides: briefing.pdf