Deranged Exams: An ICPC Problem

October 15, 2015

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


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$:

{% math %} \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} {% endmath %}

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)$$


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:

 1import java.util.*;
 4public class Test {
 5  // Basic iterative factorial; just multiply all
 6  // the numbers less than or equal to n.
 7  // returns 1 if n < 1 (which is important for n=0)
 8  private static long fact(int n) {
 9    long retval = 1; 
10    while(n > 0) 
11      retval *= n--;
12    return retval;
13  }
15  // Naive binomial coefficient computation 
16  // Generally, you need to watch overflow.  But,
17  // we can ignore that here because fact(17) < 2^63-1
18  private static long binom(int n, int k) {
19    return fact(n)/(fact(k)*fact(n-k));
20  }
22  public static void main(String[] args) { 
23    //While not recommended in general, we can use 
24    // a scanner because we're not reading a lot of input.
25    Scanner cin = new Scanner(;
27    // Precompute the derangement numbers
28    long[] d = new long[18]; // we might need values of D_n up to n=17
29    d[0] = 1;
30    for (int i = 1, j=-1; i < d.length; i++, j*=-1)
31      d[i] = i*d[i-1] + j;
32    //Process the input
33    int P = cin.nextInt();
34    for (int caseNum = 0; caseNum < P; caseNum++) {
35      cin.nextInt();
36      int n = cin.nextInt();
37      int k = cin.nextInt();
39      //S(n, k) = sum(binom(n-k, r)*d[n-r], r=0..n-k)
40      long ans = 0;
41      for (int r = 0; r <= n-k; r++)
42         ans += binom(n-k, r)*d[n-r];
44      System.out.printf("%d %d\n", caseNum+1, ans);
45    }
46  }

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$.)