Competition Programming and Problem Solving

15-295 Spring 2021

In this course you will learn the techniques and skills needed to solve algorithmic programming contests problems such as those that appear on the ICPC, Codeforces, and Topcoder. Most of your time will be spent writing programs on your own to solve problems.

But the skills you will pick up from the course are far more valuable than just enabling you to win contests. Many of the algorithms and techniques are classic ones that every computer scientist should know. You will also learn to think about algorithms in a deeper way, because many of the problems require you have to devise a new algorithm, not just apply a classic one. You will also become highly fluent in a programming language of your choice. These skills will be of great value in your other classes, in your job interviews, and in your future work.

Basic Information
Weekly Problems
Rules and Academic Integrity
Grading
Logistics
Training Resources
Learning Material
Diversity, Equity and Inclusion

Basic Information

The regular weekly contests are on Wednesdays from 7pm to 9:30pm. There may be additional lecture videos posted, or live ones at 6:30pm on Wednesday. The lectures will cover introductory content aimed at beginners of competitive programming. Although attendance to the lectures is optional, it is strongly encouraged for beginners. During the contests, the instructor will be available for help in a zoom session.

Instructor: Danny Sleator <sleator@cs.cmu.edu>, Phone: 412-268-7563
Administrative Assistant: Tony Mareino <amareino@andrew.cmu.edu>
Slack workspace (Join Required)
Codeforces 15-295 Group (Join Required)
Name List (Fill in your Row, Required)
Grade Spreadsheet
Lectures via Zoom: Wednesdays (Sporadic) from 6:30pm to 7:00pm
Class Meetings: Wednesdays from 7:00-9:30pm
     (Follow this link to see the URLs for these zoom sessions)

For more information on how to join these groups, etc, see the Logistics section below.

Weekly Contests

Week #14 - End of Semester Party

This was a prize contest. The \(n^\mbox{th}\) place winner (for \(n=1, 2, \ldots\)) got $\((128/2^n)\).
Contest Link: Here
Solutions: For Viewing

Week #13 - Number Theory

Our last topic of the semester is number theory. We will focus a lot on prime numbers, and factoring, which show up in competitions fairly often. These kinds of techniques are often combined with counting problems, since sometimes you need to use clever number theory to come up with ways to count certain objects efficiently and without double counting.

Tutorial: Number Theory tutorial
Contest Link: Here
Solutions: For Editing   For Viewing

Week #12 - Geometry

Geometry! Love it or hate it! Geometry problems are often some of the most difficult problems that appear in programming competitions because they can be full of corner cases, precision, and rounding issues. This week, we will practice the fundamental techniques behind solving geometry problems.

Tutorial: Geometry tutorial
Lecture: Comp. Geo. I: Convex Hull, 15451 Spring 2020 Notes
Lecture: Comp. Geo. II, Sweep Line, 15451 Spring 2020 Notes
Practice Problems: Link
Contest Link: Here
Solutions: For viewing

Week #11 - Strings

This week we will practice string problems. Key algorithms for this topic are Rabin-Rabin fingerprinting, the KMP algorithm, the Z-algorithm, and suffix arrays. See the links below for more info.

Karp-Rabin Fingerprinting and Pattern Matching: Tutorial   Recitation Notes
The KMP Algorithm
The Z Algorithm
Computing The Suffix Array and LCP Array

Contest Link: Here
Solutions: For Editing   For Viewing

Week #10 -- Games and Nimbers

Lecture: Video
Resources: Impartial Games (i.e. Nim-like games), Sums of Games
Contest Link: Here
Solutions: For Editing For Viewing

Week #9 -- Applications of Maximum Flow

This week, we will explore even more graph algorithms. In particular, we will be looking at applications of maximum network flow. One key difference compared to prior weeks is that we will not actually focus on the algorithms for maximum flow (you should learn these in your algorithms courses), but rather on the applications. It is therefore crucial that you have a working implementation of a maximum flow algorithm ready to go before this week's contest begins. A maximum flow code is an important component of any competitive programmer's code library. If you have not learned a maximum flow algorithm before and can not implement one yourself, you are allowed to use a prewritten implementation by someone else. I will provide you with a sample C++ implementation that you are welcome to use. The first of the practice problems this week will help you check your implementation, as it simply asks you to compute a maximum flow in a graph, and not solve any particular application. It is strongly recommended that you do this to avoid getting wrong answers during the contest due to a bug in your flow code.

Lecture: Video   Slides  
Practice Contest: enter
Sample code: (Please try to write your own. will release only in emergency)
Lecture Notes: Basic Algorithms   Advanced Algorithms   Min-Cost-Flows
Contest Link: Here
Solutions: For Viewing

Week #8 -- Combinatorial Enumeration (aka Counting Stuff)

This week we will learn how to count things!

Tutorial: Counting tutorial
Practice Problems: Link
Contest Link: Here
Solutions: For Editing   For Viewing

Week #7 -- No Theme

Contest Link: Here
Solutions: For Editing For Viewing

Week #6 -- Shortest Paths in Graphs

This week, we will continue the theme of graph algorithms and talk about shortest path problems in graphs. The fundamental algorithms that you will need to learn to solve these kinds of problems are breadth-first search (mentioned last time) and Dijkstra's algorithm. Other algorithms, such as Bellman-Ford and Floyd-Warshall are also very useful.

Lecture: Video   Slides
Resources: Lecture notes on Bellman-Ford and Floyd-Warshall
Contest Link: Here
Solutions: For Viewing For Editing

Week #5: Graph Traversal

This week we will talk about graph algorithms. This is a topic that will probably span multiple weeks as we cover things like shortest paths, minimum spanning trees, and network flows. For this week, we will focus on the fundamentals, and cover things like how to represent graphs and how to implement graph traversal algorithms (breadth first search and depth first search).

Lecture: Video   DFS code in C++   BFS code in C++
Resources: Lecture notes on DFS and Strong Components
Contest Link: Here
Solutions: here

Week #4: Dynamic programming

This week, we will practice the use of dynamic programming (DP) as a technique to solve programming competition problems. DP is quite possibly the most frequently occuring algorithmic technique used in competitions, with every ICPC contest always featuring at least one, if not several problems that require it. Mastering this technique is key to becoming a strong competitive programmer. DP revolves around two key concepts, optimal substructure, which means that a problem can be solved by breaking it into smaller versions of itself (much in the same way as divide and conquer), and memoization of overlapping subproblems, which means to cache the solutions to the smaller problems in case they need to be solved multiple times. Of all topics in competitive programming, it probably requires the most practice in order to master, so get started!

Resources: 451 Notes 1  451 Notes 2
Lecture Video: Here
Contest Link
Solutions: Here for editing Here for viewing

Week #3: Binary Search

This week, we will solve problems that use the binary search technique. You might think of binary search as an algorithm for finding an element in a sorted list, but it is actually a much more general technique than that, and can be used to solve a wide range of problems. Essentially, binary search allows you to solve problems where you must minimize or maximize some quantity subject to some contraint, as long as that constraint is monotone. A constraint is monotone if it is true/false for all values of x up to some value, and then becomes false/true after that value. Binary search allows us to efficiently find this partition point, and hence solve the corresponding optimization problem. The practice problems this week should help you to learn to apply this powerfull technique.

Lecture:  Video    binary search code    ternary search code
Contest Link
Solutions: Here for editing Here for viewing

Week #2: Built-in Algorithms and Data Structures

This week, we will focus on the most commonly used and fundamental algorithms and data structures in competitive programming. We will review and practice using arrays, binary search trees, hashtables, and priority queues. Knowing and understanding how to use these data structures in your favourite programming language is crucial to being able to quickly implement solutions to problems. We will mainly use C++ to demonstrate, but the ideas should be applicable to any language that supports these data structures.

The three practice problems should give you some practice using binary-search-tree-based data structures (set and map in C++, or TreeSet and TreeMap in Java) and priority queues (priority_queue in C++, or PriorityQueue in Java).

Lecture Video: Here
Practice Problems: Contest Link
Contest Link: Here
Solutions: Here for editing Here for viewing

Week #1: Introduction

This week has no particular algorithmic theme. Instead, we will go over the basics of competitive programming and do our first contest on Codeforces. Please make sure you have a Codeforces account ready to go and understand how to upload your solutions to the problems. You should do some practice problems to get the hang of writing and submitting solutions to the Codeforces system.

We have posted a practice contest to do just that. So go to this page and (1) join the group (right side) (2) register for the contest and (3) enter the contest. Then you will find several problems (in order of increasing difficulty) to solve.

Practice Problems: Link
Contest Link: Here
Solutions: Here for editing Here for viewing

Rules and Academic Integrity

You can make use of generic on-line resources while solving problems. These include things like language documentation, API documentation, algorithm descriptions, terminology, etc. You are allowed to use any code you have written, at any time in the past, for any purpose. However, you should not search for or make use of code written by others to solve the specific assigned problem. You are not allowed to copy somewhat standard pieces of code (e.g. a primality test). Write it yourself.

So to summarize, each student should write his or her own code. If you're stuck on a problem, you are welcome to discuss it with another student in the class, or the course staff. But you cannot copy another student's code.

The violations described above are regarded as an academic integrity violation, and -- depending on the severity -- will result in penalties and/or be reported to the appropriate university authorities.

Grading

This course is 5 units. Each week you will be given several problems to try to solve during class. You will be allowed (for half credit) to solve these problems during the week after the contest ends. You can also get credit for solving problems during rated contests on Codeforces. (This site run rated contests approximately every two weeks.)

To be more specific, you can earn points from the following sources:

Here is how your grade is determined:

score ≥ 25: A
score ≥ 15: B
score ≥ 10: C
score ≥   5: D

Logistics

Training Resources

There are many online resources available for you to train with if you intend to become a serious competitive programmer. You can find thousands of practice problems for you practice and improve your skills. Some good places to find practice problems include:

Learning Material

If you are a beginner looking for resources to learn the various topics that appear in typical contests, some good sources are:

Diversity, Equity, and Inclusion

We must treat every individual with respect. We are diverse in many ways, and this diversity is fundamental to building and maintaining an equitable and inclusive campus community. Diversity can refer to multiple ways that we identify ourselves, including but not limited to race, color, national origin, language, sex, disability, age, sexual orientation, gender identity, religion, creed, ancestry, belief, veteran status, or genetic information. Each of these diverse identities, along with many others not mentioned here, shape the perspectives our students, faculty, and staff bring to our campus. We, at CMU, will work to promote diversity, equity and inclusion not only because diversity fuels excellence and innovation, but because we want to pursue justice. We acknowledge our imperfections while we also fully commit to the work, inside and outside of our classrooms, of building and sustaining a campus community that increasingly embraces these core values.

Each of us is responsible for creating a safer, more inclusive environment.

Unfortunately, incidents of bias or discrimination do occur, whether intentional or unintentional. They contribute to creating an unwelcoming environment for individuals and groups at the university. Therefore, the university encourages anyone who experiences or observes unfair or hostile treatment on the basis of identity to speak out for justice and support, within the moment of the incident or after the incident has passed. Anyone can share these experiences using the following resources:

All reports will be documented and deliberated to determine if there should be any following actions. Regardless of incident type, the university will use all shared experiences to transform our campus climate to be more equitable and just.


Danny Sleator
Last modified: Thu Sep 22 23:56:21 2022