# T-414-ÁFLV: A Competitive Programming Course

— Competitive Programming — 8 min read

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.

**Note**: The course material is now accessible on
GitHub. Contributions are
welcome.

## Table of contents

- 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: Mathematics
- Lecture 8: Unweighted graphs
- Lecture 9: Graphs
- Lecture 10: Network flow
- Problem session 2
- Lecture 11: Strings
- Lecture 12: Geometry
- Final exam

## 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.

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

## 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 **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.

## Lecture 3: Data structures

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.

## 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)
- 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.

## 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.

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

## 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.

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

## Lecture 7: 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 **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.

## Lecture 8: 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 **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.

## Lecture 9: 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.

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

## 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.

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

## 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 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.

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

## 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.

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

## Final exam

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.