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:

public static int fallingDiscs(int[] A, int[] B) {
   int[] mins = new int[A.length];
   mins[A.length-1] = A[0];
   for(int i = 1; i < A.length; i++){
       mins[A.length-i-1] = Math.min(mins[A.length-i],A[i]);   
   }
   
   int ctr = 0;
   int minPtr = 0;
   
   for(int i = 0; i < B.length; i++){
       while(mins[minPtr] < B[i]){
           minPtr++;
           if(minPtr >= A.length) return ctr;
       }
       ctr++;
       minPtr++;
       if(minPtr >= A.length) break;
   }
   
   return ctr;
}
Markdown SHA1: b4ee8d9e6fe0b47cd0112e58558580bd91d48930