Aug 23, 2023

CS 31100 - CP2 Competitive Programming II (Fall 2023)

Course Information

Instructor

Teaching Assistant

Resources

Syllabus
Topic 0: Introduction, Simulation and Ad Hoc Slides Handout Homework Hints
Homework Deadline: 2023-08-31 23:59 EDT
  • Logistics
  • Observations serve as a means to comprehend a problem and simplify it into a more manageable form.
    • Intuition: Are we able to visualize the problem? Could we develop a straightforward brute-force solution?
    • Insight: Can we identify any unique or non-obvious properties within the problem?
    • Exploration: Is it possible to leverage these properties to reframe the problem into a different context?
    • Verification: Is the reframed problem recognizable? Can we solve it using techniques we're familiar with?
    • Enhanced observational skills facilitate more efficient connections between a problem and known techniques.
  • Techniques are specialized methods or codes used to solve well-defined problems.
    • Familiarity with a broader array of techniques provides more reference points for problem-solving.
  • Both observational acumen and technical skill are essential for effective problem-solving.
  • When it comes to coding, one often-neglected focus should be on optimal conciseness, aiming to write the most streamlined code possible for the problem at hand.
  • For debugging, we have a couple of options.
    • Static methods include techniques like rubber-duck debugging to help us think through the problem.
    • Dynamic methods, on the other hand, involve using logs, setting breakpoints, and applying fuzz testing to identify issues.
Topic 1: Scan Line: Discretization, Monotonic Stack/Queue Slides Handout Homework Hints
Homework Deadline: 2023-09-07 23:59 EDT
  • We can use the prefix sum/differential technique to solve easy range query problems.
  • One common technique is converting an interval into two events: \( +a \) at the start and \( -a \) at the end.
  • We can use various data structures together with the sweep line technique, such as set, map, monotonic queue/stack, etc.
  • It is helpful to consider the 'usefulness' and 'potential' of every element when constructing an algorithm.
  • Classic problems include interval cover and largest rectangle in histogram.
Topic 2: Range Query: RMQ and Fenwick Tree Slides Handout Homework Hints
Homework Deadline: 2023-09-14 23:59 EDT
  • Range query encompasses various operations on a list, such as:
    • Point Query: Retrieve the value of \( a[i] \).
    • Range Query: Calculate \( \max(a[l..r]), \min(a[l..r]), \sum(a[l..r]), \ldots \).
    • Point Modification: Update \( a[i] \) to a specific value.
    • Range Modification: Apply operations like setting \( a[l..r] \) to \( x \), adding \( x \) to \( a[l..r] \), etc.
  • We can use the sparse table to query \( \max(a[l..r]) \) in \( O(\log n) \).
  • We can use the Fenwick tree to query \( \sum(a[l..r]) \) and update a single point in \( O(\log n) \).
Topic 3: Range Query: Segment Tree and Lazy Update Slides Handout Homework Hints
Homework Deadline: 2023-09-21 23:59 EDT
  • Intuition of the segment tree comes from square root decomposition.
  • Segment tree is the swiss knife that is effective at all range query problems. Nevertheless, it suffers from implementation complexity and poor constant factor.
  • We have learnt a variety of range query data structures:
    • Array
    • Prefix Sum
    • Sparse Table
    • Fenwick Tree
    • Segment Tree
  • We should pick the appropiate data structure based on the problem.
Topic 4: Geometry: Basics, Convex Hull, Convex Optimization Slides Handout Homework Hints
Homework Deadline: 2023-09-28 23:59 EDT
  • Reference and template is important to solve a geometry problem. My reference is available at https://github.com/zhtluo/LMR.
  • We can handle the precision issues in geometry by setting an EPS.
  • Dot and det products are building blocks in geometry problems.
  • The slope trick, convex optimization and decision monotonicity are common techniques in optimizing a DP problem.
Topic 5: Number Theory: Prime Numbers, GCD, exGCD Slides Handout Homework Hints
Homework Deadline: 2023-10-06 23:59 EDT
  • We can find all prime numbers within \( n \) with the linear sieve.
  • We can compute \( x^a \) within \( O(\log a) \) with binary exponentiation.
  • Fermat's Little Theorem allows us to compute a modular inverse with binary exponentiation, assuming the modular is prime.
  • Extended GCD allows us to compute a modular inverse with any modular.
Topic 6: Combinatorics: Counting, Inclusion-Exclusion, Linear Recurrence Slides Handout Homework Hints
Homework Deadline: 2023-10-12 23:59 EDT
  • Basic building blocks for a counting problem include permutation \( P(n, m)=\frac{n!}{(n-m)!} \) and combination \( C(n, m)=\binom{n}{m}=\frac{n!}{(n-m)!m!} \).
  • The stars and bars trick is a common technique in building a solution.
  • we can use the inclusion-exclusion principle to transform a 'exactly \( k \) times' problem to a set of 'at most \( i \) times \( (0 \le i \le k) \)' problems.
  • We can find the \( n \)-th termn of a linear recurrence by constructing a matrix and use binary exponentiation to obtain a complexity of \( O(k^3\log n) \).
Topic 7: Tree: LCA, DP, DFS Order Slides Handout Homework Hints
Homework Deadline: 2023-10-12 23:59 EDT
  • We covered two types of problems: one that cares about subtrees and one that cares about paths on trees.
  • For the problems about subtrees, one approach is to consider the DFS order (in-order) of the tree: every subtree is an interval on the DFS order.
  • For the problems about paths, one approach is to take aprt the paths between \( (u, v) \) to \( (u, w) \) and \( (w, v) \), where \( w \) is the LCA of \( (u, v) \).
  • Two archetypes of dynamic programming on the tree are:
    • Finding the size of all subtrees, in which for every node \( x \) we care about all its subtrees.
    • Finding the height of all nodes, in which for every node \( x \) we care about the value on its parent.
  • Real problems require a combination of the above techniques and is often done by traversing the tree twice. During the first traversal we consider something about the subtree rooted at that node. During the second traversal we consider the impact of the parent on that node.
Topic 8: Graph: Matching, Network Flow Slides Handout Homework Hints
Homework Deadline: 2023-10-26 23:59 EDT
  • There are different algorithms to solve the network flow problem: Dinic, ISAP, Push-relabel, Primal Dual, etc.
    • It is less important to fully grasp the inner working of the algorithms of this topic (which hopefully we already did in CS 381).
    • Instead, try grabbing a template online or from my codebase (https://github.com/zhtluo/LMR/tree/master/src/graph/flow) and use it to solve the problems.
  • Network flow problems are hard to identify. Some signs are a relatively small \( n \) (100 to 1000) and being hard to solve otherwise.
  • Network flow problems have three catagories: max flow, min cut and min cost.
  • We can use a flow template to solve bipartite matching problems, but dedicated algorithms (Hopcroft-Karp, Hungarian, etc.) are usually faster by a constant factor.
Topic 9: String: Hash, KMP, AC Automata Slides Handout Homework Hints
Homework Deadline: 2023-11-02 23:59 EDT
  • Two approaches are available to solve string matching: rolling hash and automata.
  • Rolling hash is considered secure if implemented correctly.
  • Automata approaches such as KMP and AC automata are useful in dynamic programming.
  • Other approaches are also available: suffix array/automata, palindrome tree, etc. They are topics for CP3 and available to pursue at your own interest.
Topic 10: String: DP, Bitmasking, Plugging Slides Handout Homework Hints
Homework Deadline: 2023-11-09 23:59 EDT
  • Review: two common ways to construct a DP is to observe the transition and the substructure.
  • In a digit DP, we treat the number as a string and do DP on its prefix.
  • In a bitmask DP, we compress a state into a number.