← All solutions

Solved by 128 teams.

First solved after 35 minutes.

Shortest judge solution: 496 bytes.

With some experimentation, one can quickly observe the pattern that all heights in the range 2n − 1 to n² can be achieved, except for n² − 2. Let’s prove that n² − 2 cannot be achieved. Every cup contributes either 0cm, 1cm or its height to the total height of the stack. What’s more, the 3cm cup cannot contribute a height of 1cm, because only the 1cm cup can fit inside and that doesn’t reach the top of the 3cm cup, so it is impossible to build a stack that sits on the base of the 3cm cup. So starting from the solution for n² (stacking the cups from smallest to largest), the only change that reduces the height by up to 2cm is to put the 1cm cup inside a larger cup (reducing the height by 1cm).

Now lets consider how to construct any other solution. We can proceed inductively: assume we know how to use n − 1 cups to construct stacks with heights from 2n − 3 to n² − 2n + 1, excluding n² − 2n − 1. We can then add the nth cup either to the bottom of the stack (increasing the height by 1, with a minimum of 2n − 1) or to the top (increasing the height by 2n − 1). The first case gives us all heights from 2n − 1 to n² − 2n − 1; the second gives all heights from 4n − 4 to n² except n² − 2. So provided that n² − 2n ≥ 4n − 4, we will have complete coverage except for n² − 2. This holds for n ≥ 6. For n ≤ 5 we can use brute force.