Dec 10, 2023

CS 41100 - CP3 Competitive Programming III (Spring 2024)

Course Information

Course Number and Title: CS 41100 - CP3 Competitive Programming III
CRN: 69765-CP3
Meeting Time & Location: Tuesday and Thursday 6:00 pm--7:15 pm, LWSN B134
Course Credit Hours: 2
Course Web Page: https://cs.purdue.edu/homes/luo401/teaching/cs411-spring2024/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 4:00 pm--5:00 pm, Friday 3:00 pm--5:00 pm at HAAS 271 or by appointment

Teaching Assistant

Name: Egor Gagushin
E-mail: egagushi@purdue.edu
Office Hours: Monday 4:00 pm--5:00 pm at HAAS 271, Wednesday 2:30 pm--4:00 pm at HAAS 143

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	Notes	Individual Contest
Upsolve deadline: Mon Jan 15, 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 Practice Problem. Think about it. Implement if you are unsure. 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. Think about it. Implement if you are unsure. 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 fastest. You may try it during your spare time to see how fast you can get.
Topic 1: Geometry: Review, Half-plane Intersection, Adaptive Simpson	Slides	Notes	Team Contest
Upsolve deadline: Mon Jan 22, 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 concepts (i.e. integration) before the class. 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	Notes	Individual Contest
Upsolve deadline: Mon Jan 29, 2024 23:59 pm Attend the CP2 lecture for the next two weeks if you need review on combinatorics fundementals. 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 5, 2024 23:59 pm Some range-update segtree 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 unsure: https://codeforces.com/gym/104757/problem/B.
Topic 4: Monotonicity: DP Review, Optimization	Slides	Handout	Individual Contest
Upsolve deadline: Mon Feb 12, 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. Alien's trick --- advanced optimization trick: http://www.serbanology.com/vault/The%20Trick%20From%20Aliens.
Topic 5: Tree: Review, LCA, HLD	Slides	Handout	Team Contest
Upsolve deadline: Mon Feb 19, 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 thet 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.
Topic 6: Student Topic 1	Slides	Handout	Individual Contest
Upsolve deadline: Mon Feb 26, 2024 23:59 pm
Topic 7: Network Flow	Slides	Handout	Team Contest
Upsolve deadline: Mon Mar 4, 2024 23:59 pm
Topic 8: Student Topic 2	Slides	Handout	Individual Contest
Upsolve deadline: Mon Mar 18, 2024 23:59 pm
Topic 9: KMP, Automata	Slides	Handout	Team Contest
Upsolve deadline: Mon Mar 25, 2024 23:59 pm KMP: https://cp-algorithms.com/string/prefix-function.html AC Automata: https://cp-algorithms.com/string/aho_corasick.html
Topic 10: Offline: CDQ, Mo's Algorithm	Slides	Handout	Individual Contest
Upsolve deadline: Mon Apr 1, 2024 23:59 pm
Topic 11: Final Contest	Slides	Handout	Team Contest
Upsolve deadline: Mon Apr 8, 2024 23:59 pm