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.