Deranged Exams: An ICPC Problem

This past week, my ICPC team worked the 2013 Greater New York Regional problem packet. One of my favorite problems in this set was Problem E: Deranged Exams. The code required to solve this problem isn’t that complicated, but the math behind it is a little unusual. In this post, I aim to explain the math and provide a solution to this problem.

Problem Description

The full problem statement is archived online; in shortened form, we can consider the problem to be:

Given a “matching” test of $n$ questions (each question maps to exactly one answer, and no two questions have the same answer), how many possible ways are there to answer at least the first $k$ questions wrong?

It turns out that there’s a really nice solution to this problem using a topic from combinatorics called “derangements.” (Note that the problem title was a not-so-subtle hint towards the solution.)

Derangements

While the idea of a permutation should be familiar to most readers, the closely related topic of a derangement is rarely discussed in most undergraduate curriculum. So, it is reasonable to start with a definition:

A derangement is a permutation in which no element is in its original place. The number of derangements on $n$ elements is denoted $D_n$; this is also called the subfactorial of $n$, denoted $!n$.

The sequence $\langle D_n\rangle$ is A000166 in OEIS (a website with which, by the way, every competitive programmer should familiarize themselves).

It turns out that there is both a recursive and an explicit formula for $D_n$:

\begin{aligned} D_n &= (-1)^n \sum_k\binom{n}{k} (-1)^k k! \\ &= n\cdot D_{n-1} + (-1)^n;\;(D_0=1) \end{aligned}

This is significant because we can use the explicit formulation for computing single values of derangements, or we can use dynamic programming to rapidly compute $D_n$ for relatively small $n$.

Problem Approach

The key observation here is that, using the derangement formula, we may compute the number of ways to answer a given set of questions incorrectly, using only the answers corresponding to those questions. Instead of focusing on the first $k$ questions, which we must answer incorrectly, let us look to the remaining $n-k$ questions.

Consider the case when we answer $r$ questions correctly. There are $\binom{n-k}{r}$ ways of choosing which $r$ questions we answer correctly (since the first $k$ must be wrong).

The remaining $n-r$ questions must be answered incorrectly using only the answers to the same $n-r$ questions. Using our knowledge of derangements, there are $!(n-r)$ ways to assign those incorrect answers.

Finally, note that the number of correct answers, $r$ is bounded by $n-k$; summing over all possible values of $r$, we obtain:

$$S(n, k) = \sum_{r=0}^{n-k} \binom{n-k}{r}\cdot !(n-r)$$

Code

Equations are great, but implementation is required for ICPC. First, we must consider input/output size. The problem statement gives the following ranges for $n$ and $k$:

\begin{aligned} 1 \leq n \leq 17 \\ 0 \leq k \leq n \end{aligned}

We can expect that this will fit in a 64-bit integer, as $n! \leq 2^{63}-1$ for $n\leq 20$. Thus, we don’t even need to be careful in computing binomial coefficients due to intermediate overflow! I’ll let the code (and comments) speak for itself:

Further Reference

Derangements are discussed in Concrete Mathematics by Graham, Knuth, and Patashnik on pages 193-196. In those pages, the identities shown in this blog entry are derived. Also discussed is a closely related problem that may be called $r$-derangements.

In the $r$-derangement problem, we seek the number of arrangements in which exactly $r$ elements are in their original place. (The number of $0$-derangements, then, is just $D_n$.)