Guide to Competitive Programming

Integers The most used integer type in competitive programming is int, which is a 32-bit type1 with a value range of −231 . . . 231 − 1 (about −2 · 109 . . . 2 · 109). If the type int is not enough, the 64-bit type long long can be used. It has a value range of −263 . . . 263 − 1 (about −9 · 1018 . . . 9 · 1018).

The following code defines a long long variable: long long x = 123456789123456789LL;
The suffix LL means that the type of the number is long long. A common mistake when using the type long long is that the type int is still used somewhere in the code. For example, the following code contains a subtle error:

int a = 123456789;
long long b = a*a;
cout << b << “\n”; // -1757895751

Even though the variable bis of type long long, both numbers in the expression a*a are of type int, and the result is also of type int. Because of this, the variable b will have a wrong result. The problem can be solved by changing the type of a to long long or by changing the expression to (long long)a*a.

Usually contest problems are set so that the type long long is enough. Still, it is good to know that the g++ compiler also provides a 128-bit type __int128_t with a value range of −2127 . . . 2127 − 1 (about −1038 . . . 1038). However, this type is not available in all contest systems.

Modular Arithmetic Sometimes, the answer to a problem is a very large number, but it is enough to output it “modulo m”, i.e., the remainder when the answer is divided by m (e.g., “modulo 109 + 7”). The idea is that even if the actual answer is very large, it suffices to use the types int and long long.

We denote by x mod m the remainder when x is divided by m. For example, 17 mod 5 = 2, because 17 = 3 · 5 + 2. An important property of remainders is that the following formulas hold:

(a + b) mod m = (a mod m + b mod m) mod m
(a − b) mod m = (a mod m − b mod m) mod m
(a · b) mod m = (a mod m · b mod m) mod m

Thus, we can take the remainder after every operation, and the numbers will never become too large.

1In fact, the C++ standard does not exactly specify the sizes of the number types, and the bounds depend on the compiler and platform. The sizes given in this section are those you will very likely see when using modern systems.

For example, the following code calculates n!, the factorial of n, modulo m:

long long x = 1;
for (int i = 1; i <= n; i++) {
x = (x*i)%m;
}
cout << x << “\n”;

Usually wewant the remainder to always be between 0 . . .m−1. However, in C++ and other languages, the remainder of a negative number is either zero or negative.

An easy way to make sure there are no negative remainders is to first calculate the remainder as usual and then add m if the result is negative:

x = x%m;
if (x < 0) x += m;

However, this is only needed when there are subtractions in the code, and the remainder may become negative.

Floating Point Numbers In most competitive programming problems, it suffices to use integers, but sometimes floating point numbers are needed. The most useful floating point types in C++ are the 64-bit double and, as an extension in the g++ compiler, the 80-bit long double. In most cases, double is enough, but long double is more accurate.

The required precision of the answer is usually given in the problem statement. An easyway to output the answer is to use the printf function and give the number of decimal places in the formatting string. For example, the following code prints the value of x with 9 decimal places:

printf(“%.9f\n”, x);

A difficulty when using floating point numbers is that some numbers cannot be represented accurately as floating point numbers, and there will be rounding errors.

For example, in the following code, the value of x is slightly smaller than 1, while the correct value would be

double x = 0.3*3+0.1;

printf(“%.20f\n”, x); // 0.99999999999999988898

It is risky to compare floating point numbers with the == operator, because it is possible that the values should be equal but they are not because of precision errors.

A better way to compare floating point numbers is to assume that two numbers are equal if the difference between them is less than ε, where ε is a small number.

For example, in the following code ε = 10−9:

if (abs(a-b) < 1e-9) {
// a and b are equal
}

Note that while floating point numbers are inaccurate, integers up to a certain limit can still be represented accurately. For example, using double, it is possible to accurately represent all integers whose absolute value is at most 253.