Aug 23, 2023

CS311: 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
  • How to think about a problem:
    • Observations (drawing connections from problem to some technique we know)
    • Techniques (concrete technique for a fixed problem)
  • How to code a problem:
    • The concise code problem: how to write the most concise code?
  • How to debug:
    • Static: rubber-ducking
    • Dynamic: log, breakpoints, fuzzing
Topic 1: Scan Line: Discretization, Monotonic Stack/Queue Slides Handout Homework Hints
Homework Deadline: 2023-09-07 23:59 EDT
  • Prefix Sum / Differential
    • Treating interval as +a at the start and -a at the end
  • Data Structures with Scan Line
    • Set, map, monotonic queue/stack
    • 'Usefulness' and 'potential' of elements
  • Classic problems
    • Interval Cover: greedy, sort by left, then always take the most right interval
    • Largest Rectangle in Histogram: monotonic queue, keep track of useful left bounds of rectangle
Topic 2: Range Query: RMQ and Fenwick Tree Slides Handout Homework Hints
Homework Deadline: 2023-09-14 23:59 EDT
  • Range Query: a combination of
    • Find out what \( a[i] \) is (point query)
    • Find out what \( \max(a[l..r]), \min(a[l..r]), \sum(a[l..r]), \ldots \) is (range query)
    • Set \( a[i] \) to something (point modification)
    • Set \( a[l..r] \) to \( x \) / Add \( x \) to \( a[l..r] \) / \( \ldots \) (range modification)
  • Analyze the problem, find out the operations necessary before deciding what technique to use!
  • RMQ: capable of querying \( \max(a[l..r]) \) only.
    • Array of size \( N \times \log N \), with each row denoting length \( 2^0, 2^1, \ldots, 2^{\log N} \)
    • Populate the array with doubling technique, i.e. use data of length \( 2^i \) to compute \( 2^{i+1} \)
    • Assemble a query of range \( a[l..l+len] \) with log many sub-ranges
    • Assemble a query of range \( a[l..l+len] \) with two intersecting sub-ranges if range intersection is permissible (the case of RMQ)
  • Other Applications of Doubling
    • Fast Power
    • LCA
    • Other ad hoc data (e.g. Surveillance from ICPC 2014)
  • Fenwick Tree: capable of querying \( \sum(a[l..r]) \) and modifying a single element
Topic 3: Range Query: Segment Tree and Lazy Update Slides Handout Homework Hints
Homework Deadline: 2023-09-21 23:59 EDT
  • Segment Tree
    • Intuition: Square Root Decomposition
  • Summary of Range Query Data Structure
    • Array
    • Prefix Sum
    • RMQ & Sparse Table
    • Fenwick Tree
    • Segment Tree
  • Pick the appropiate data structure for the problem!
Topic 4: Geometry: Basics, Convex Hull, Convex Optimization Slides Handout Homework Hints
Homework Deadline: 2023-09-28 23:59 EDT
  • Template: https://github.com/zhtluo/LMR
  • Computational Geometry Basics
    • Precision Problem and EPS
    • Everything is a vector!
    • Dot and Det product
  • Geometry and DP Optimization
    • Slope Trick / Convex Optimization / Decision Monotonicity