Skip to content

T-414-ÁFLV: A Competitive Programming Course (2016 edition)

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.
Warmup problems

We posted this optional set of problems as a warmup for those who were eager to get started.

Problems

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

CC BY 4.0 This work is licensed under a Creative Commons Attribution 4.0 International License.

Published inCompetitive Programming

8 Comments

  1. 16 16

    oh! so excited!!!!!!!!!!!!!

  2. Bhishma Bhishma

    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.

  3. Bhishma Bhishma

    How to implement the move operation in the problem Almost Union-Find

  4. Norbert Madarasz Norbert Madarasz

    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.

  5. Kitihounel Kitihounel

    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)

Leave a Reply

Your email address will not be published. Required fields are marked *