Saint Petersburg State University - Competitive Programmer’s Core Skills

INSTRUCTORS

Instructors: Alexander S. Kulikov, Alexander Logunov and Kirill Simonov

During the course, you’ll learn everything needed to participate in real competitions — that’s the main goal. Along the way you’ll also gain useful skills for which competitive programmers are so highly valued by employers: ability to write efficient, reliable, and compact code, manage your time well when it’s limited, apply basic algorithmic ideas to real problems, etc.

We start from the very beginning by teaching you what competitions there are, what are their rules, what specifics problems have, how to read problem statements, how to organize your work, and what you should and shouldn’t do. So it’s fine if you’ve never taken part in programming competitions before.

We’ll focus on skills essential to competitive programming: inventing solutions and proving their correctness, estimating their running time, testing and debugging programs, how to benefit from structuring code. We’ll also cover basic algorithmic ideas: brute force search, dynamic programming, greedy algorithms, segment trees.

On competitions, there are a lot of specific pitfalls, perilous to beginners — but that’s not to worry, as we’ll go through the most common of them: integer overflow and issues with fractional numbers, troubles of particular programming languages, how to get unstuck in general. And, you’ll hone all these skills by solving practice problems, which are just like problems on real competitions

Syllabus

Programming Competitions

• We’ll begin with introduction to the world of competitive programming — the rules, specialties and helpful tips on taking part in competitions in general. In a separate lesson, we’ll learn how to test programs: what kinds of test cases there are, how to organize the search for a bugtest, and particularly a method of automating testing called stress-testing.

CORRECTNESS FIRST

• In this module, we’ll start with the most basic things you need to actually solve algorithmic problems. First, we’ll talk about structuring your code and intuition behind it — why it’s very important, how to manage dependencies between parts of different purpose, how intuitive rules are enforced through formal invariants and conditions. We’ll also identify a special class of solutions — brute force solutions — which are always correct, but often very slow. And we’ll learn how to estimate running time of our solutions by using a powerful concept of big-O notation.

COMMON STRUGGLES

• In competitive programming, there are a lot of things to stumble upon — if you don’t know them first! We’ll delve into how numbers are represented in computers, identify the most common issues with integer and floating point arithmetic, and learn to overcome them. We’ll also discuss how to get stuck less in general, especially when debugging solutions.

COMMON STRUGGLES 2

• We continue considering common struggles arising in competitive programming. We start by learning how to prove that a natural greedy algorithm is correct. We also discuss programming languages: what features are most helpful on competitions, and what are the advantages and pitfalls of several frequently used languages. Finally, we study an essential and easy-to-implement data structure: the segment tree.

Dynamic Programming

• Dynamic programming is a powerful algorithmic paradigm with lots of applications in areas like optimisation, scheduling, planning, bioinformatics, and others. For this reason, it is not surprising that it is the most popular type of problems in competitive programming. A common feature of such problems is that a solution is usually easy to implement. This does not however mean that it is also easy to find a solution! Therefore, it is important to practice solving such problems. And this is exactly what we are going to do in this module!

Dynamic Programming 2

• We continue applying dynamic programming technique to various problems.