T-414-ÁFLV: A Competitive Programming Course (2016 edition)
— Competitive Programming — 8 min read
We will be holding our course about Competitive Programming for the second time during the three weeks from April 25th to May 13th. The format will be similar as before, but hopefully with a fresh set of problems.
Note: The course material is now accessible on GitHub. Contributions are welcome.
Table of contents
- Warmup problems
- Lecture 1: Introduction
- Lecture 2: Data structures and libraries
- Lecture 3: Data structures
- Lecture 4: Problem solving paradigms
- Lecture 5: Greedy algorithms
- Problem session 1
- Lecture 6: Dynamic programming
- Lecture 7: Unweighted graphs
- Lecture 8: Graphs
- Lecture 9: Mathematics
- Problem session 2
- Lecture 10: Network flow
- Lecture 11: Strings
- Lecture 12: Geometry
- Final exam
Warmup problems
We posted this optional set of problems as a warmup for those who were eager to get started.
Problems
- A Different Problem
- Bus Numbers
- Cold-puter Science
- Hello World!
- In or Out
- Natrij
- Path Tracing
- Server
Lecture 1: Introduction
Covers some basic things about the course, and then introduces competitive programming.
Material
Problems
Solve some of the following problems on Kattis. You need 5 points to get full score.
- Flexible Spaces (1 point)
- Secret Message (1 point)
- Permutation encryption (2 points)
- Collatz Conjecture (2 points)
- Cross (3 points)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 2: Data structures and libraries
Reviews the most basic data types and data structures. Covers how to represent big integers, sets and graphs, and how to augment binary search trees.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Deduplicating files (1 point)
- Working at the Restaurant (1 point)
- Adding words (1 point)
- All Just A Dream (1 point)
- Movie collection (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 3: Data structures
Reviews the Union-Find disjoint sets data structure, and covers range queries, Square Root Decomposition and Segment Trees.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Counting Subsequences (Hard) (1 point)
- Virtual Friends (1 point)
- Kastenlauf (1 point)
- Frosh Week (1 point)
- Almost Union-Find (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 4: Problem solving paradigms
Introduces problem solving paradigms, and covers complete search, backtracking, and divide & conquer. Covers binary search, and binary exponentiation.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Lifting Walls (1 point)
- Fruit Baskets (1 point)
- Distributing Ballot Boxes (1 point)
- Building Fences (1 point)
- Sylvester Construction (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 5: Greedy algorithms
Introduces greedy algorithms, and covers coin changing, interval scheduling, and scheduling to minimize lateness.
Material
- Lecture slides: PDF
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Minimum Scalar Product (1 point)
- A Vicious Pikeman (Easy) (1 point)
- Bank Queue (1 point)
- Watering Grass (1 point)
- Magic Checkerboard (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Problem session 1
Teams of up to three students had to solve the following problems. They had three hours, and were only allowed to use a single computer.
Lecture 6: Dynamic programming
Introduces dynamic programming and goes over some examples.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Muzicari (1 point)
- What Does It Mean? (1 point)
- Narrow Art Gallery (1 point)
- Peg Solitaire (1 point)
- Restaurant Orders (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 7: Unweighted graphs
Reviews basic graph theory. Covers depth-first search, breadth-first search, and applications.
Material
Problems
Solve some of the following problems on Kattis. You need 4 points to get full score.
- Coast Length (1 point)
- Build Dependencies (1 point)
- Button Bashing (1 point)
- Reversing Roads (2 points)
- Torn To Pieces (2 points)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 8: Graphs
Covers minimum spanning trees, shortest paths, some graph theory, and some special types of graphs.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Breaking Bad (1 point)
- Minimum Spanning Tree (1 point)
- Block Crusher (1 point)
- Get Shorty (1 point)
- VivoParc (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 9: Mathematics
Covers some basic topics in mathematics, including number theory, combinatorics and game theory.
Material
Problems
Solve some of the following problems on Kattis. You need 4 points to get full score.
- Growling Gears (1 point)
- How Many Digits? (1 point)
- Three Powers (1 point)
- Bachet’s Game (2 points)
- Perfect Pth Powers (2 points)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Problem session 2
Teams of up to three students had to solve the following problems. They had three hours, and were only allowed to use a single computer.
Lecture 10: Network flow
Covers maximum flow, minimum cut, bipartite matching, and other applications.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Maximum Flow (1 point)
- Paintball (1 point)
- Minimum Cut (1 point)
- Elementary Math (1 point)
- Minimum Cost Maximum Flow (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 11: Strings
Covers string matching, KMP, tries, suffix arrays, and applications.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Bing It On (1 point)
- Power Strings (1 point)
- Burrows-Wheeler (1 point)
- Dvaput (1 point)
- Repeated Substrings (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Lecture 12: Geometry
Covers basic geometry, convex hulls, area of polygons, point in polygon, and closest pair of points.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Vacuumba (1 point)
- Jabuke (1 point)
- Board Wrapping (1 point)
- Polygon Area (1 point)
- White Water Rafting (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Final exam
At the end of the course there was a four-hour individual final exam. It was as follows.
Part 1 (35%)
Solve one of the following problems.
Part 2 (15%)
Solve one of the following problems.
Part 3 (15%)
Solve one of the following problems.
Part 4 (15%)
Solve one of the following problems.
Part 5 (15%)
Solve one of the following problems.
Part 6 (15%)
Solve one of the following problems.