Competitive Programmer's Handbook

Preface

The purpose of this book is to give you a thorough introduction to competitive
programming. It is assumed that you already know the basics of programming,
but previous background on competitive programming is not needed.
The book is especially intended for students who want to learn algorithms
and possibly participate in the International Olympiad in Informatics (IOI) or in
the International Collegiate Programming Contest (ICPC). Of course, the book is
also suitable for anybody else interested in competitive programming.
It takes a long time to become a good competitive programmer, but it is also
an opportunity to learn a lot. You can be sure that you will get a good general
understanding of algorithms if you spend time reading the book, solving problems
and taking part in contests.

Introduction

Competitive programming combines two topics: (1) the design of algorithms and
(2) the implementation of algorithms.
The design of algorithms consists of problem solving and mathematical
thinking. Skills for analyzing problems and solving them creatively are needed.
An algorithm for solving a problem has to be both correct and efficient, and the
core of the problem is often about inventing an efficient algorithm.
Theoretical knowledge of algorithms is very important to competitive pro-
grammers. Typically, a solution to a problem is a combination of well-known
techniques and new insights. The techniques that appear in competitive pro-
gramming also form the basis for the scientific research of algorithms.
The implementation of algorithms requires good programming skills. In
competitive programming, the solutions are graded by testing an implemented
algorithm using a set of test cases. Thus, it is not enough that the idea of the
algorithm is correct, but the implementation also has to be correct.
A good coding style in contests is straightforward and concise. Programs
should be written quickly, because there is not much time available. Unlike in
traditional software engineering, the programs are short (usually at most some
hundreds of lines) and it is not needed to maintain them after the contest.