Guide to Competitive Programming

Competitive programming combines two topics: the design of algorithms and the
implementation of algorithms. Design of Algorithms The core of competitive programming is about inventing efficient algorithms that solve well-defined computational problems.

The design of algorithms requires problem solving and mathematical skills. Often a solution to a problem is a combination of well-known methods and new insights. Mathematics plays an important role in competitive programming.

Actually, there are no clear boundaries between algorithm design and mathematics. This book has been written so that not much background in mathematics is needed. The appendix of the book reviews some mathematical concepts that are used throughout the book,

Implementation of Algorithms In competitive programming, the solutions to problems are evaluated by testing an implemented algorithm using a set of test cases. Thus, after coming up with an algorithm that solves the problem, the next step is to correctly implement it, which requires good programming skills.

Competitive programming greatly differs from traditional software engineering: programs are short (usually at most some hundreds of lines), they should be written quickly, and it is not needed to maintain them after the contest.

At the moment, the most popular programming languages used in contests are C++, Python, and Java. For example, in Google Code Jam 2017, among the best 3,000 participants, 79% used C++, 16% used Python, and 8% used Java. Many people regard C++ as the best choice for a competitive programmer.

The benefits of using C++ are that it is a very efficient language and its standard library contains a large collection of data structures and algorithms.

All example programs in this book are written in C++, and the standard library’s data structures and algorithms are often used. The programs follow the C++11 standard, which can be used in most contests nowadays. If you cannot program in C++ yet, now is a good time to start learning.