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)

Factovisors

Stacking Curvy Blocks

Hamming Ellipses

Linear Recurrences

First Orchard

Primonimo
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.
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 highlyskilled 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 closedform 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.
