Apr 10, 2025

CS 41100, Competitive Programming III (Spring 2025)

Course Information

• Course Number and Title: CS 41100, Competitive Programming III
• CRN: 69765-CP3
• Meeting Time & Location: Tuesday and Thursday 5:30 pm–6:15 pm, LWSN B134
• Course Credit Hours: 2
• Course Web Page: https://cs.purdue.edu/homes/luo401/teaching/cs411-spring2025/index.html
• Prerequisites: Undergraduate Level CS 31100 Minimum Grade of C

Contact Information

Instructor

• Name: Zhongtang Luo
  • E-mail: luo401@purdue.edu
  • Office Hours: Monday 2:00 pm–3:00 pm at DSAI B022 or by appointment

Teaching Assistant

• Name: Jimmy Dinh
  • E-mail: dinh16@purdue.edu
  • Office Hours: Monday 3:30 pm–5:00 pm at DSAI B047, Friday 11:30 am–1:20 pm at LWSN Commons
• Name: Leo Lee
  • E-mail: lee4247@purdue.edu
  • Office Hours: Monday 3:30 pm–5:00 pm at DSAI B047, Friday 11:30 am–1:20 pm at LWSN Commons
• Name: Egor Gagushin
  • E-mail: egagushi@purdue.edu
  • Office Hours: Thursday 3:30 pm–5:30 pm at DSAI B022
• Name: Thomas Marlowe (Unavailable)
  • E-mail: marlowe@purdue.edu
  • Office Hours: Monday 1:30 pm–3:00 pm, Friday 3:00 pm–5:00 pm at DSAI B022

Course Sign-up

Please follow the procedure and fill out this form here, so we can keep track of your progress: https://forms.gle/JRppvD7SsaVCQ6M18.

Resources

• Syllabus

• Topic 0: Introduction, Implementation
  [Slides] [Handout] [Individual Contest]
  • Upsolve Deadline: Mon Jan 20, 2024 23:59 pm
  • Review the syllabus.
  • Review computational geometry from CP2.
  • Review the basic concepts and get familiar with the reference codebase.
    • If you have never been in touch with geometry before, this blog is a good start.
    • You will need a reference codebase to perform efficiently in the contest. I have one for my use here.
    • Try to run through this problem list to understand how to use the reference: https://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=CGL
    • If you want to see how I write geometry code: https://zhtluo.com/cp/rant-on-incorrect-ecna-2023-c-computational-geometry.html.
    • Extra reading on theory: Handbook of geometry for competitive programmers.
  • Review convex hull (if you have time).
    • Dig out the relevant code from the reference codebase and understand how to use it.
    • Practice Problem: https://codeforces.com/gym/104114/problem/B.
    • Extra reading on theory: Graham's scan (Wikipedia).
  • Get ready for some implementation tasks.
    • During my college years we had an activity called 'ICPC Ranking Speedrun'. We would code this problem titled 'ICPC Ranking' and see who got accepted the fastest. You may try it during your spare time to see how fast you can get.
  • A few of my write-ups on how to improve:
    • The Reason You are Bad at Codeforces — You are Not Russian Enough
    • All You Need is Randomly Guessing — How to Improve at Codeforces
  • A few examples on constant optimization:
    • Constant Optimization on Binary Exponentiation and Matrix Multiplication
    • Constant Optimization and Cheesing through NAQ
  • MIT's course on guessing: https://ocw.mit.edu/courses/18-098-street-fighting-mathematics-january-iap-2008/pages/readings/

• Topic 1: Geometry: Review, Half-plane Intersection, Adaptive Simpson
  [Slides] [Handout] [Team Contest]
  • Upsolve Deadline: Mon Jan 27, 2024 23:59 pm
  • Upsolve Alice and Bomb from Topic 0 if you are still not confident in basic geometry skills.
  • Half Plane Intersection: https://cp-algorithms.com/geometry/halfplane-intersection.html. I would recommend not to understand the theory behind it, but simply find a good template and solve some problems (sample problems at the end of the link) with the template.
  • Adaptive Simpson: https://en.wikipedia.org/wiki/Adaptive_Simpson%27s_method. Not particularly important to understand the theory either, but you may find it helpful to review calc 1/2 concepts (i.e. integration).
  • Delaunay Triangulation and Voroni Diagram: https://codeforces.com/blog/entry/85638. Read this if you want to figure out what the official solution for tricky problems in the problem set is.
  • Combinatorics: Codeforces have a reasonable set of combinatorics problems: https://codeforces.com/problemset/page/1?tags=combinatorics. In particular, you can try this problem: https://codeforces.com/problemset/problem/1764/D. It is fine if you cannot think of a solution. Instead, read the tutorial and make sure that you can understand it and are comfortable implementing it.

• Topic 2: Combinatorics: Review, Linear Recurrence
  [Slides] [Handout] [Individual Contest]
  • Upsolve Deadline: Mon Feb 3, 2024 23:59 pm
  • There is much theory online. Feel free to read through them if interested, but in my opinion, the important point in CP is still to come up with a formula fast rather than know a bunch of formulae.
    • Binomial Coefficients: https://cp-algorithms.com/combinatorics/binomial-coefficients.html
    • Catalan Numbers: https://cp-algorithms.com/combinatorics/catalan-numbers.html
    • Stirling Numbers: https://codeforces.com/blog/entry/117906
  • Binary Exponentiation (and some of its application): https://cp-algorithms.com/algebra/binary-exp.html
  • Next week is going to be difficult. It will be helpful to review these concepts first.
    • RMQ and Sparse Table: https://cp-algorithms.com/data_structures/sparse-table.html
    • Fenwick Tree: https://cp-algorithms.com/data_structures/fenwick.html
    • Easier Segment Tree: https://codeforces.com/contest/1919/problem/F1

• Topic 3: Range Query: Review, Segment Tree Hard
  [Slides] [Handout] [Team Contest]
  • Upsolve Deadline: Mon Feb 10, 2024 23:59 pm
  • Some range-update segment tree I wrote: here.
  • Application of segment trees: https://cp-algorithms.com/data_structures/segment_tree.html.
  • DP is relatively easy to review. Go over the CP1 classes if you need a refresher.
  • Also, try to upsolve this problem from our first class if you need some practice: https://codeforces.com/gym/104757/problem/B.

• Topic 4: Monotonicity: DP Review, Optimization
  [Slides] [Handout] [Individual Contest]
  • Upsolve Deadline: Mon Feb 17, 2024 23:59 pm
  • CP algorithm link on optimization: https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html
  • Kuroni's blog on convex hull: https://codeforces.com/blog/entry/77298
  • Extra reading on convex hull: https://jeffreyxiao.me/blog/convex-hull-trick

• Topic 5: Tree: Review, LCA, HLD
  [Slides] [Handout] [Team Contest]
  • Upsolve Deadline: Mon Feb 24, 2024 23:59 pm
  • In CP1 and CP2, we have learned the basic ways we can handle a tree (DFS, DP, etc.).
  • In CP3, we introduce two techniques that help transform problems on a tree to problems on an array: DFS order and HLD.
  • LCA: https://cp-algorithms.com/graph/lca_binary_lifting.html
  • HLD: https://cp-algorithms.com/graph/hld.html
  • HLD sample code by me, kinda sloppy

• Topic 6: Game Theory: SG Function, Search
  [Slides] [Handout] [Individual Contest]
  • Upsolve Deadline: Mon Mar 3, 2024 23:59 pm
  • Learning Objectives: the students will be able to...
    • Describe the game tree of a strategy game.
    • Identify losing states and winning states of a strategy game.
    • Conduct an exhaustive search using the reverse-topological order to determine losing states and winning states.
    • Describe the Sprague-Grundy theorem.
    • Compute the Sprague-Grundy number of a Nim game.
    • Analyze the Sprague-Grundy number of a state in an impartial game.
  • SG theorem: https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem

• Topic 7: Network Flow: Min-Cut, Min-Cost
  [Slides] [Handout] [Team Contest]
  • Upsolve Deadline: Mon Mar 10, 2024 23:59 pm
  • Learning Objectives: the students will be able to...
    • Describe the max-flow network flow problem and the min-cost network flow problem.
    • Describe the max-flow min-cut theorem.
    • Apply well-established algorithms (ISAP, Dinic, EK, ZKW, etc.) to solve a network flow problem.
    • Model programming problems (e.g. a matching problem) with network flow.
  • Extra read: https://zhtluo.com/cp/a-compilation-of-network-flow-graphs.html.

• Topic 8: Fast Fourier Transform
  [Slides] [Handout] [Individual Contest]
  • Upsolve Deadline: Mon Mar 24, 2024 23:59 pm
  • Learning Objectives: The students will be able to...
    • Describe the input and the output of the fast Fourier transform and the number theoretic transform algorithm.
    • Use the idea of generating functions to format problems into polynomial multiplications.
    • Apply the fast Fourier transform algorithm and the number theoretic transform algorithm to solve problems.
  • Theory: https://cp-algorithms.com/algebra/fft.html

• Topic 9: String: KMP, AC Automata
  [Slides] [Handout] [Team Contest]
  • Upsolve Deadline: Mon Mar 31, 2024 23:59 pm
  • Learning Objectives: The students will be able to...
    • Describe the concept of an automata.
    • Discuss how string processing fits into the concept of an automata, with examples such as Trie, KMP, and AC automata.
    • Leverage an automata to solve problems involving strings.
  • Check out ECNA 2023 H if you want more automata problems (you might want to read up on the pumping lemma first).

• Topic 10: Offline: CDQ, Mo's Algorithm
  [Slides] [Handout] [Individual Contest]
  • Upsolve Deadline: Mon Apr 7, 2024 23:59 pm

• Topic 11: Final Contest
  [Slides] [Handout] [Team Contest]
  • Upsolve Deadline: Mon Apr 14, 2024 23:59 pm