程序員的核心技能培訓

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.