title: Codility Chromium challenge: count ascending sequences that alternate left and right
body: <p>I have struggled a lot with this Codility coding challenge: <a href="https://app.codility.com/programmers/challenges/chromium2017/" rel="nofollow noreferrer">https://app.codility.com/programmers/challenges/chromium2017/</a></p>
  
  <p>(The basic problem is: given a list of integers, count the number of ascending sequences possible where if the start of the sequence is at index, <code>i</code>, no two neighbouring elements of the sequence (excluding the first two) are on the same side of <code>i</code>. e.g., given [6, 2, 3, 4], starting at 2, we could go [2], [2, 3], [2, 4], [2, 6], [2, 3, 6] or [2, 4, 6].)</p>
  
  <p>As of yet I am only capable of thinking of a solution with time complexity O(N^2) while O(N*log(N)) is required. All though somebody has posted a solution on GitHub, I don't have a clue what's going on:</p>
  
  <p><a href="https://github.com/kalwar/Codility/blob/master/chromimum2017_solution.c" rel="nofollow noreferrer">https://github.com/kalwar/Codility/blob/master/chromimum2017_solution.c</a></p>
  
  <p>It seems like he's doing affine transformations back and forth, but I lack the insight into why this works and why it can be achieved with O(N*Log(N)) time complexity. I was hoping somebody could shed a light.</p>
  
  <p>I posted my own solution (in Java) below:</p>
  
  <pre><code>final class Chromium {
  
      final long MODULUS = 1000000007L;
  
      static class Nest implements Comparable&lt;Nest&gt; {
  
          Nest(int index, int height) {
              this.index = index;
              this.height = height;
          }
  
          int index;
          int height;
  
          public int compareTo(Nest nest2) {
              return Integer.compare(height, nest2.height);
          }
      }
  
      /**
       * Calculates the possibilities based on the fact that it is a multiplication of the runs of consecutive nests
       * left and right of the nest in focus.
       */
      private long getPossibleWays(Nest[] orderedNests, int startIndex) {
  
          Nest startNest = orderedNests[startIndex];
  
          long ways = 0;
          long oppositeNumberOfWays = 0;
  
          boolean previousLeft = false;
          boolean first = true;
          int runLength = 0;
  
          for (int i = orderedNests.length - 1; i &gt; startIndex; --i) {
  
              Nest n = orderedNests[i];
              boolean left = n.index &lt; startNest.index;
  
              if (left != previousLeft &amp;&amp; !first) {
                  ways += (runLength * (oppositeNumberOfWays + 1)) % MODULUS;
                  long w = oppositeNumberOfWays;
                  oppositeNumberOfWays = ways;
                  ways = w;
  
                  runLength = 1;
              } else {
                  runLength++;
              }
  
              first = false;
              previousLeft = left;
          }
          ways += (runLength * (oppositeNumberOfWays + 1)) % MODULUS;
          return 1 + ways + oppositeNumberOfWays;
      }
  
      public int solution(int[] H) {
          Nest[] nests = new Nest[H.length];
          for (int i = 0; i &lt; H.length; ++i) {
              nests[i] = new Nest(i, H[i]);
          }
  
          // Sort the nests by height
          Arrays.sort(nests);
  
          long possibleWays = 0;
  
          for (int i = 0; i &lt; nests.length; ++i) {
              possibleWays += getPossibleWays(nests, i);
              possibleWays = possibleWays % MODULUS;
          }
  
          return (int) possibleWays;
      }
  }
  </code></pre>