ZigZagEscape (Chromium 2017 Challenge)

This page displays a solution to Codility’s Chromium 2017 Challenge. The problem’s given name is ZigZagEscape.

The following solution attains 90% score under Codility’s test, it is therefore NOT a golden award solution.


def solution(H):
    N = len(H)
    stack = []
    array1 = [0]*N
    stack.append((0, H[0]))
    array1[0] = (0, 1000000010) 
    for idx, elem in enumerate(H):
        while stack[-1][1] < elem:
            stack.pop()
            if stack == []:
                stack.append((idx, elem))
                array1[idx] = (idx, 1000000010)
                break
        if stack[-1][1] > elem:
                array1[idx] = stack[-1]
                stack.append((idx, elem))
    stack = [(N-1, H[-1])]
    for idx, elem in enumerate(reversed(H)):
        while stack[-1][1] < elem:
            stack.pop()
            if stack == []:
                stack.append((N-idx-1, elem))
                break
        if stack[-1][1] > elem:
            if array1[N-idx-1][1] > stack[-1][1]:
                array1[N-idx-1] = stack[-1]
            stack.append((N-idx-1, elem))
    array2 = []
    for x in xrange(N):
        array2.append(((H[x], x), array1[x][0]))
    array2.sort(reverse = True)
    POS = [0]*N
    for k in xrange(N):
        POS[k] = (array2[k][0][1], k)
    POS.sort()
    F = []
    for i in xrange(N):
        F.append((array2[i][0][1], POS[array2[i][1]][1]))
    dp = [((0,0), 0)]
    total = N
    for i in xrange(1, N):
        sum_l = dp[F[i][1]][0][0]
        sum_r = dp[F[i][1]][0][1]
        current = F[i][0]
        for j in xrange(dp[F[i][1]][1], i):
            if F[j][0] < current:
                sum_l += sum_r +1
            else:
                sum_r += sum_l +1
        dp.append(((sum_l, sum_r), i))    
        total += sum_l + sum_r
        total %= 1000000007
    return total

The time complexity of the above solution is O(N*sqrt(N)).

A link to the test result is available here.

You may have also noticed that only golden awards were granted for this challenge.

When a solution undergoes the Codility test, several single tests are carried out. For this challenge, the fine distinction between a O(N*sqrt(N)) solution and a O(N*log(N)) solution was made by a test placed in the “correctness” block instead of the “performance’ block. This way, only O(N*log(N)) solutions were considered to produce correct results and no single silver award was granted for this challenge.

Leave a Reply

Your email address will not be published.