Aug 23, 2023

# CS311: Competitive Programming II - Fall 2023

## Course Information

### Instructor

• Name: Zhongtang Luo
• E-mail: luo401@purdue.edu
• Office Hours: Wednesday 2:00 - 3:00 PM at HAAS 271 or by appointment

### Teaching Assistant

• Name: Otavio Sartorelli de Toledo Piza
• E-mail: osartore@purdue.edu
• Office Hours: Tuesday 10:30 AM - 12:00 PM, Thursday 10:30 AM - 12:00 PM at HAAS G072
• Name: Egor Gagushin
• E-mail: egagushi@purdue.edu
• Office Hours: Monday 11:00 AM - 12:30 PM, Wednesday 2:00 - 3:30 PM at HAAS G072

## 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 Supplementary Youtube video: https://www.youtube.com/watch?v=uSFzHCZ4E-8 Remember the way to add/modify an element with lowbit 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