I held a course about Competitive Programming at Reykjavik University on the fall semester of 2014. It was three-week long with a fresh lecture and problem set each day. There were almost 90 students registered and it turned out to be a big success, although some students complained about heavy workload. For me it was a very rewarding experience.
Below you may find the lecture slides (including LaTeX sources), the problem sets, and other supporting material. All problems are available on the Open Kattis online judge.
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.
- Eight Queens (1 point)
- Toilet Seat (1 point)
- T9 Spelling (1 point)
- Rock-Paper-Scissors Tournament (2 points)
- Chess (2 points)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
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 5 points to get full score.
- Hay Points (1 point)
- CD (1 point)
- I Can Guess the Data Structure (1 point)
- Phone List (2 points)
- Cookie Selection (2 points)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
Reviews the Union-Find disjoint sets data structure, and covers range queries and Segment Trees.
Material
Problems
Solve some of the following problems on Kattis. You need 3 points to get full score.
- Virtual Friends (1 point)
- Counting Subsequences (1 point)
- Kastenlauf (1 point)
- Almost Union-Find (1 point)
- Worst Weather Ever (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
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)
- Natjecanje (1 point)
- Arctic Network (1 point)
- Sylvester Construction (1 point)
- Welcome to Code Jam (Easy) (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
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.
- Virus Replication (1 point)
- Planting Trees (1 point)
- Watering Grass (1 point)
- Bank Queue (1 point)
- Moving Pianos (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
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.
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.
- Exact Change (1 point)
- Radio Commercials (1 point)
- Pebble Solitaire (1 point)
- Spiderman’s workout (1 point)
- Restaurant Orders (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
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 3 points to get full score.
- Ones (1 point)
- Sierpinski circumference (1 point)
- Bachet’s Game (1 point)
- Falling Mugs (1 point)
- Snapper Chain (Hard) (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
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 3 points to get full score.
- Coast Length (1 point)
- Reactivity Series (1 point)
- Flip Five (1 point)
- Dominos (1 point)
- Dominoes 2 (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
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.
- Freckles (1 point)
- Breaking Bad (1 point)
- Get Shorty (1 point)
- Fire Station (1 point)
- Shopping Malls (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
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.
- Gopher II (1 point)
- Paintball (1 point)
- Maximum Flow (1 point)
- Minimum Cut (1 point)
- Minimum Cost Maximum Flow (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
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.
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.
- Kemija (1 point)
- Peragrams (1 point)
- Power Strings (1 point)
- Clock Pictures (1 point)
- Dvaput (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
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.
- Logo (1 point)
- Jabuke (1 point)
- Wrapping (1 point)
- Pesky Mosquitoes (1 point)
- White Water Rafting (1 point)
Bonus problems
If you want a challenge, you can try solving the following bonus problems.
At the end of the course there was a four-hour individual final exam. It was as follows.
Part 1 (30%)
Solve one of the following problems.
Part 2 (20%)
Solve one of the following problems.
Part 3 (20%)
Solve one of the following problems.
Part 4 (20%)
Solve one of the following problems.
Part 5 (20%)
Solve one of the following problems.
Part 6 (20%) (Bonus)
Solve one of the following problems.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Great work. Thanks!
Great Job Guys!. It’s really useful for beginners like me :).
[…] 10. Another Course to refer- T-414-ÁFLV: A Competitive Programming Course […]
[…] Another Course to refer algo: A Competitive Programming Course […]
Awesome course .
[…] material e bem estruturado. Vários exemplos de exercícios para resolver em cada […]
Hi,
Great job, there is just a typo in the lecture on Data structures and lib (lecture 2). Slide 32, you added an edge connecting a vetrex to itself. “adj[2].push_back(2);” . Tiny problem, but worth fixing.
-MATH
p.s. this is a 10 minute email account.
Great materials you got there , Thanks
Great collection sir!!!
In your Data Structures lesson specifically Disjoint Sets, you don’t implement union by rank you only apply path compression, this is not optimal. Both are fairly straightforward heuristics and by using them you can achieve optimal efficiency.
Regards
This observation also happens in the 2016 course.
Thank you so much for the materials! I have no one to guide me and these materials really helped me a lot.
Thanks 🙂
Hi,
Thanks for the resources.
[…] A Competitive Programming Course by Bjarki Ágúst Guðmundsson […]