International Collegiate Programming Contest

Mathematics

This session focuses on mathematics for programming contests. If you are not familiar with the relevant concepts and algorithms, or you need a refresher, you can use the resources below.

Problem Set (#5)

1. Stripe
2. Twin Primes
3. Marbles
4. God! Save me
5. Contemplation! Algebra
6. Beautiful Numbers

Note: All problems expect I/O to be done using standard input and standard output. The solution to problems must be written in a single file. If you are programming in Java the application class should be called "Main" and should be in the default package.

Resources

Mathmatics

Many ICPC problems are rooted in mathematical formulas and observations. It is common for each regional problem set to include one or two problems that are number theoretic in nature, involve counting, or involve probability theory. Most highly-skilled competitive programmers have a strong mathematical background that can aid in such problems. For those of you majoring in Computer Science that want to make ICPC a top priority, consider adding a minor in Mathematics or even a double major. Recommended courses include combinatorics, elementary number theory, and a probability theory course.

Combinatorics

Many ICPC problems ask you to count the number of objects in some set. Solving these types of problems often involves finding a recurrence that can be evaluated efficiently, or deriving some closed combinatorial formula.

Often, formulas involve binomial coefficients. It is important to be familiar with binomial coefficients and the common problems that they can solve. To evaluate n choose k, we recommend using the recursive dynamic programming solution that uses this identity. This approach has the advantage that it is easy to evaluate modulo some number n. Furthermore, it avoids overflow as any intermediate values are less than the final value.

Probability Theory

Often ICPC problems ask for the probability of an event or the expected number of times an event occurs. Often this involves exploring a state space and using dynamic programming, or finding some closed-form formula.

For a refresher on basic probability, check out the wikipedia page here.

For a refresher on expected value, check out the wikipedia page here.

Number Theory

Many ICPC problems involve number theory. For an overview of basic number theory in programming competitions, take a look at this topcoder tutorial.

The most important number theoretic functions for ICPC are listed below. Greatest common divisor, the chinese remainder theorem, and a few other functions not discussed can be found in our library code here: https://github.com/atmorgan/ICPC2014/blob/master/Algebra.cc.

• Greatest common divisor (gcd). The largest integer that divides two integers a and b is called the gcd of a and b. The gcd of a and b can be found efficiently with the Euclidean algorithm.
• Sieve of Eratosthenes. Determining if a single number n is prime can be done easily in O(sqrt(n)) time by trial division. But what if we need to find all prime numbers less than some number k? Rather than testing each number for primality, taking time O(k sqrt(k)), we can sieve for prime numbers in time O(n log log n) time, which is much faster. Many variants of the Sieve of Eratosthenes exist to find primes in a range [a, b] or even primes in an arithmetic progression.
• Chinese Remainder Theorem. The chinese remainder theorem finds a number x that is congruent to a_1 mod b_1, a_2 mod b_2, ..., a_n mod b_n. The chinese remainder theorem gives a way to find x efficiently with the Extended Euclidean algorithm as a subroutine.

A type of more challenging common number theory problem is when some type of number is defined, typically based on its decimal or binary representation, and the problem then asks for the ith such number or a count of such numbers in a range.

In general, number theory problems often have more than one mathematical law that can be exploited to be evaluated efficiently. This can lead to problems with many different solutions.

Fast Linear Recurrence Evaluation

Often, an ICPC problem will involve a linear recurrence. For these types of problems, you may be asked to compute the nth term, where n is some gigantic number. Luckily, we can create a matrix to represent one step of the transformation, then do fast matrix exponentiation to compute the nth term in O(k^3 log n) time, where your matrix is of size k x k. A tutorial on solving linear recurrence for programming contests can be found here. Though library code shouldn't be necessary, we have an implementation of fast recurrence evaluation here.