11. Mathematics

This chapter deals with mathematical topics that are recurrent in competitive programming. We will both discuss theoretical results and learn how to use them in practice in algorithms. Section 11.1 discusses number-theoretical topics. We will learn algorithms for finding prime factors of numbers, techniques related to modular arithmetic, and efficient methods for solving integer equations. Section 11.2 explores ways to approach combinatorial problems: how to efficiently count all valid combinations of objects. The topics of this section include binomial coefficients, Catalan numbers, and inclusion-exclusion. Section 11.3 shows how to use matrices in algorithm programming. For example, we will learn how to make a dynamic programming algorithm more efficient by exploiting an efficient way to calculate matrix powers. Section 11.4 first discusses basic techniques for calculating probabilities of events and the concept of Markov chains. After this, we will see examples of algorithms that are based on randomness. Section 11.5 focuses on game theory. First we will learn to optimally play a simple stick game using nim theory, and after this, we will generalize the strategy to a wide range of other games.