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.
We posted this optional set of problems as a warmup for those who were eager to get started.
Problems
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.
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.
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.
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.
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.
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.
- 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.
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.
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.
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.
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 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.
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.
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.
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.
This work is licensed under a Creative Commons Attribution 4.0 International License.
oh! so excited!!!!!!!!!!!!!
Is there a discussion forum available , where we can ask queries ?
My students and I are using Piazza, but I don’t think it would be appropriate to invite non-students to join that particular forum. I guess we could use the Codeforces post or this page, at least temporarily. If someone wants to create something externally, that might be cool as well.
How to implement the move operation in the problem Almost Union-Find
Hello
Is there going to be a subsequent session?
Unfortunately I missed this one…
Cheers,
Norbert
We haven’t made any plans yet. But this course is intended to be used for self-study, so you should be able to study from home, whenever you see fit, at your own pace.
Hi. Very nice and useful course. My friends and me use it to prepare our ICPC national and regional contests.
A little contribution. In the introduction chapter when you present how to represent sets with integers, you use this to get the complement of a subset : ~x & ((1 << n) – 1)
I think one can simple use: x ^ ((1 << n) – 1)
Thanks! That is indeed a little bit cleaner, at least conceptually.
Hello
What’s your idea about putting some hints for those that couldn’t solve problems?