International Collegiate Programming Contest

Discrete Mathematics and Network Flow

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

Problem Set (#7)

1. Farey Sequences
2. Internet Bandwidth
3. Binomial Showdown
4. The Dog Task
5. Dice Throwing (HINT: Make use of the rational struct in library code: https://github.com/atmorgan/ICPC2014/blob/master/Rational.cc)
6. Prime Distance
7. Glenbow Museum
8. Warehouse

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 pretty 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.

Network Flow

NOTE: Network Flow is an advanced graph theory topic that only occasionally presents itself in ICPC. For beginner competitive programmers, it is recommended to skip this section. Further note, this content was largely drawn from here. For a more in-depth breakdown of network flow, please read the source programming session.

A digraph with weighted edges can be interpreted as a network, with the edges representing directed connections between the nodes, and the weights representing the capacities of those connections. The capacities of an edge and its reverse may be different; a non-existent reverse is considered as existing with zero capacity. The classic example is of a network of water pipes: each vertex is a joint which connects some pipes, and each pipe has a maximum rate of flow that can pass through it. (Ordinary pipes, of course, are undirected and have the same capacity in each direction.) One has a special vertex, the source, which generates flow (say, a water pump) and another special vertex, the sink, which consumes it. Other vertices neither produce nor consume flow, so the net incoming minus outgoing flow at any other vertex should be zero. One can ask various questions about the flows possible on such a network, but the most common is the maximum flow problem: What is the largest amount of flow that can be passed through the network from the source to the sink, and how can it be realized?

There are a wide variety of generic problems that network flow can solve. Mastering these can help expand your ability to recognize a problem as requiring network flow. The following resources have a nice sampling of some of these problems:

• University of Washington Lecture Slides
• Algorithm Design, by Jon Kleinberg and Éva Tardos.
  (This is the textbook used in CS 577 here at UW–Madison.)
• Lecture notes from a Princeton course taught from the Kleinberg-Tardos book are available here

Solutions

• Ford–Fulkerson

  Ford–Fulkerson finds a maximum flow by consecutively finding augmenting paths from the source vertex to the sink. These paths are any path such that additional flow can be pushed by adding or redirecting flow along any edge. When chosen via a depth-first search and edge capacities are integers, Ford-Fulkerson runs in O(f*(V+E)) time, where f is the value of the maximum flow.

• Edmonds–Karp

  Edmonds–Karp uses the same idea as Ford–Fulkerson, but it can be shown that by using a breadth-first search instead of a depth-first search, an alternate complexity of O(|V||E|^2) can be achieved. Implementation here.

• Dinic

  Dinic is an improvement to Edmonds–Karp that achieves a complexity of O(|V|^2|E|). In practice, dinic is exceptionally quick, and should be used as the algorithm of choice if Edmonds–Karp will not be fast enough. Implementation here.

Min-Cost Max-Flow

Min-Cost Max-Flow takes a graph as input where each edge has both a capacity and a weight. The goal is then to find a maximum flow from s to t such that the sum of the weights of edges used is minimal. Many interesting problems can be modeled in the min-cost max-flow problem framework. There are two common ways to solve the min-cost max-flow problem: negative cycle cancellation, and a modification of the Ford–Fulkerson algorithm.

The negative cycle cancellation technique finds cycles along which positive flow can be pushed and which have negative total cost. To model the source–sink behavior, an infinite-capacity edge is added from the sink to the source. When all of the negative cycles have been cancelled, the resulting flow is a maximum flow with minimum cost. This simple technique is fairly easy to implement, and works well when the network can be guaranteed to have few negative cycles.

The more common solution to min-cost max-flow is to use the Ford–Fulkerson algorithm, and select augmenting paths by choosing paths with positive capacity and minimum total cost. More details of this approach are given in this Top Coder tutorial.

An implementation of both algorithms is given here.

Matching

• Unweighted Bipartite Matching

  The general unweighted bipartite matching problem takes as input a bipartite graph representing two sets of objects to be matched, with an edge between objects that can potentially be paired. The maximum bipartite matching question asks how many pairs can be made such that each object from either set is involved in at most one pair. The basic max-flow algorithm solves this problem, however there are specialized versions that can solve it faster. Here is an implementation that achieves O(|V||E|) time complexity, with simpler code than the full max-flow algorithm.

• Weighted Bipartite Matching

  Weighted bipartite matching asks the same matching problem except in a weighted graph. The general solution can be reduced to min-cost max-flow, but the Hungarian Algorithm solves the problem more efficiently and with less code. The algorithm runs in O(|V|^3) time. Implementation here.