Codingame Solution: Highest truncated pyramid

Solution

We got a number \(n\) of bricks to build a pyramid. The top rows are getting cut off to manage a number that wouldn't form a full pyramid. So how can we get the parameters of such a building? We basically need to start at row \(s\) and continue until row \(t\). That means, that our \(n\) is built by

\[n = \sum\limits_{i=s}^t i = \sum\limits_{i=1}^t i - \sum\limits_{i=1}^{s-1} i\]

Which can be simplified, using the triangular number sequence:

\[n = \frac{1}{2}t(t+1)-\frac{1}{2}(s-1)s = \frac{1}{2} (t^2 - s^2 + t + s)\]

So, how can we parametrize this diophantine equation? The easiest approach would be to brute-force a solution:

function search(n) {

  for (var s = 1; s <= n; s++) {

    for (var t = 1; t <= n; t++) {

      if (2 * n === (t * t - s * s + t + s)) {
        return [s, t];
      }
    }
  }
  return null;
}

With this algorithm, we can already pass all test cases like this:

[s, t] = search(n);

for (; s <= t; s++) {
    print("*".repeat(s));
}

But a lot of CPU cycles are wasted. Let's try to reduce the search space a bit. Since it doesn't make sense to increase \(t\) any further than \(2n\), we can use the inner condition as breakup condition:

\[t^2-s^2+t+s \leq 2n\Leftrightarrow t^2+t\leq 2n+s^2-s\Leftrightarrow t \leq \frac{1}{2}\left(\sqrt{8 n + 4 s (s - 1) + 1}-1\right)\]

Another optimization that can be made is based on the fact that powers of two can't be formed as a triangle. That means a power of two always needs to be represented as one row of length \(n\). Checking if \(n\) is a power of two can be done by a binary and against \(n-1\). If the result is zero, the number must have been a power of two. The search space can be brought down further. As the longest row appears with \(n\) being a power of two, all other pyramids must have at least two rows. That means we can half the search space of \(s\). After these optimizations, the search function can be implemented like this:

function search(n) {

  if ((n & (n - 1)) === 0)
    return [n, n];

  var x = n / 2;

  for (var s = 1; s <= x; s++) {

    var y = 2 * n + s * s - s;

    for (var t = 1; t * (t + 1) <= y; t++) {

      if (2 * n === (t*t - s*s + t + s)) {
        return [s, t];
      }
    }
  }
  return null;
}

If you're curious, the upper bound is still \(O(\frac{1}{2}n^2) = O(n^2)\). So back to the drawing board. Let's think a bit different. We know that the pyramid consists of \(n\) blocks. With these blocks we want to form \(k\) layers. So, back up from layer \(t\) this means:

\[n = t + (t-1) + (t-2) + ... + (t-k) = kt - \frac{k(k-1)}{2}\]

The first layer is simply \(s=1+t-k\). So what we do now is start with \(k\) at a large value and successively search for an integer \(t\) by solving the equation for \(t\):

\[t = \frac{n + \frac{k(k-1)}{2}}{k} = \frac{2n+k(k-1)}{2k}\]

With that equation, we can check for an integer solution and calculate \(t\). All we need is a proper starting value for \(k\), which we choose to be \(\lceil\sqrt{n}\rceil\). Finally, we can implement the parameter search in \(O(\sqrt{n})\):

function search(n) {

  if ((n & (n - 1)) === 0)
    return [n, n];

  var k = Math.ceil(Math.sqrt(n));

  while (k > 0) {
    var p = 2 * n + k * (k - 1);
    var q = 2 * k;
    if (p % q === 0)
        return [1 + p / q - k, p / q];
    k--;
  }
  return null;
}