Codility Chromium challenge: count ascending sequences that alternate left and right

Question

I have struggled a lot with this Codility coding challenge: https://app.codility.com/programmers/challenges/chromium2017/

(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, i, no two neighbouring elements of the sequence (excluding the first two) are on the same side of i. 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].)

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:

https://github.com/kalwar/Codility/blob/master/chromimum2017_solution.c

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.

I posted my own solution (in Java) below:

final class Chromium {

    final long MODULUS = 1000000007L;

    static class Nest implements Comparable<Nest> {

        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 > startIndex; --i) {

            Nest n = orderedNests[i];
            boolean left = n.index < startNest.index;

            if (left != previousLeft && !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 < 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 < nests.length; ++i) {
            possibleWays += getPossibleWays(nests, i);
            possibleWays = possibleWays % MODULUS;
        }

        return (int) possibleWays;
    }
}

Answer 1

I think I understand A. Jordan's solution now by reading up on data structures and in particular Segment Trees with lazy updates.

However, there are a lot of insights about the problem to be made first:

Preparation:

• It is convenient to sort the nests by height. After this is done the height itself is not relevant, only the position within the array of nests. (i.e. all heights would be normalized as increasing integers 0,1,2,3,4...). This means that once the nests are sorted we can forget about their actual height.
• Keep track of the index of the nest within the original array, because that is needed to determine the relative left/right position of other nests relative to it. In the image above the index is shown in red and the height is shown in black.

Now the general strategy to determine the total number of valid ways will be:

• Calculate the number of ways any Nest(k) (0 <= k < N, k is the positional index from left to right) can be reached as final destination and sum all those ways (which will be the final answer). Call the number of ways Nest(k) can be reached as final destination W(k)

As any nest can only be reached from lower nests, if we traverse the nests in ascending order (i.e. ordered by height) we should be able to calculate W(k) based on all values previously calculated. This is the standard dynamic programming approach.

Now think about the valid ways a Nest(k) can be reached as end point:

• Start at Nest(k) and remain there which gives 1 possibility
• Start from any previously calculated way through a lower Nest(i) where i > k and the start nest for that way had an index j where k < j <= i.
• Start from any previously calculated way through a lower Nest(i) where i < k and the start nest for that way had an index j where i <= j < k.

This may be visualized as for any valid way the start nest has to be in between the final destination and the nest from which that destination was reached.

For example, take Nest(1) in the picture with height = 6. It can be reached from every way through Nest(4) which has height = 5 for which the index of the start nest lay in between the final Nest(1) and Nest(4) inclusive. Note that the range is inclusive because it can also be directly reached from Nest(4). It cannot however be reached from the way that started at Nest(0) and went to Nest(4), because then the last two jumps would be at the same side of the start nest, which is not allowed.

Now call the number of ways from a particular start nest Nest(i) that end to its right R(i) and the number of ways that end to its left L(i) and assume we have calculated all these possible ways for lower nests.

Then:

1. W(k) = 1 + sum([R(j) for j in k+1...N-1]) + sum([L(j) for j in 0...k-1])

This calculation has time complexity of O(N) (for each k) so needs optimization, but we come to that later. First we need to understand how to keep track of R(j) and L(j).

This again can be done with a dynamic programming approach:

Say we know the current number of ways from Nest(i) which end to its right R(i). Every time we encounter a new nest to the left of Nest(i) the number of ways which end to the left L(i) gets incremented by its current R(i). This is because every way which ended to the right gets a new option to go one step further to the new nest to the left. The reverse is of course also true: R(i) = L(i) if a nest to the right is encountered.

So we can extract two more calculations:

2. for i in 0...k-1: R(i) += L(i)
3. for i in k+1...N-1: L(i) += R(i)

Initially the number of ways of both L(i) and R(i) should be set to 1 to allow for the direct option to go from the start nest to the destination nest.

For every nest that is positioned to the left, increase the right number of ways as explained above and the same for every nest that is positioned to the right.

However again this requires O(N) operations.

For reference, a very simple python program which performs the calculations above (which gives the correct results, but is slow O(N^2)) is listed below:

def solution(H):
    MOD = 1000000007
    N = len(H)
    nests = [(height, index) for index, height in enumerate(H)]
    nests.sort()
    dp_left = [0] * N
    dp_right = [0] * N
    total = 0

    for nest in nests:
        index = nest[1]

        # Add 1 way for the current nest
        total += 1

        # Add all possible ways reaching this nest from the left
        for i in range(index):
            total += dp_left[i]
            total %= MOD

        # Add all possible ways reaching this nest from the right
        for i in range(index + 1, N):
            total += dp_right[i]
            total %= MOD

        # Initialize left and right ways to 1 for the current nest
        dp_right[index] = 1
        dp_left[index] = 1

        # Update the right possible ways for nests to the left
        for i in range(index):
            dp_right[i] += dp_left[i]
            dp_right[i] %= MOD

        # Update the left possible ways for nests to the right
        for i in range(index + 1, N):
            dp_left[i] += dp_right[i]
            dp_left[i] %= MOD

    return total % MOD

Now to reach O(N Log(N)) time complexity we would have to find a way to improve the time complexity of calculations 1, 2 and 3 from O(N) to O(log(N)).

Now here is where the concept of Lazy Segment Trees comes into play which can do exactly that.

Basically both updates and queries can be converted to O(log(N)) operations as explained.

Now to implement this there are still some technical details to be solved. In particular for doing the lazy updates because the updates to apply are not a constant value for every nest, but depends on the index of the nest to update. See this question for reference.

Here is a link to my solution, based on A. Jordan's solution rewritten in Swift with a lot of code cleanup and simplifications.