# Codility Falling Discs

#### Posted on November 3, 2013

##### Last updated on November 6, 2013

In this article I will provide a solution to the Falling Discs sample Codility problem. The problem description is copyrighted, so have a look at the link for the description.

The simple solution is to just simulate the disc falling in until it stops. Since the well is size $$N$$, and we have $$M$$ rings, this is $$O(MN)$$.

To get the algorithm down to $$O(N)$$, we notice that a ring $$r$$ will fall through to some position $$p$$ in the well if and only if all the well ring diameters above it are greater than or equal to the size of $$r$$, for otherwise $$r$$ would have gotten stuck at a position before $$x$$. This means that to figure out where a ring will travel down to some position $$x$$ in the well, we only need to know the smallest well ring size above $$x$$. We can get this by precomputing the smallest diameters for every position in the well. This problem is actually similar in spirit to Rainfall at a skyline.

A Java solution that scores 100/100 hence might be as follows:

Markdown SHA1: b4ee8d9e6fe0b47cd0112e58558580bd91d48930