## Solution to Slalom-Skiing by codility

Question: https://codility.com/programmers/lessons/90-tasks_from_indeed_prime_2015_challenge/slalom_skiing/ Question Name: Slalom-Skiing or SlalomSkiing This is a wonderful variant of longest increasing subsequence.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | def LongestIncreasingSubsequence(seq): ''' The classic dynamic programming solution for longest increasing subsequence. More details could be found: https://en.wikipedia.org/wiki/Longest_increasing_subsequence http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/ http://stackoverflow.com/questions/3992697/longest-increasing-subsequence ''' # smallest_end_value[i] = j means, for all i-length increasing # subsequence, the minmum value of their last elements is j. smallest_end_value = [None] * (len(seq) + 1) # The first element (with index 0) is a filler and never used. smallest_end_value[0] = -1 # The length of the longest increasing subsequence. lic_length = 0 for i in range(len(seq)): # Binary search: we want the index j such that: # smallest_end_value[j-1] < seq[i] # AND # ( smallest_end_value[j] > seq[i] # OR # smallest_end_value[j] == None # ) # Here, the result "lower" is the index j. lower = 0 upper = lic_length while lower <= upper: mid = (upper + lower) // 2 if seq[i] < smallest_end_value[mid]: upper = mid - 1 elif seq[i] > smallest_end_value[mid]: lower = mid + 1 else: raise "Should never happen: " + \ "the elements of A are all distinct" if smallest_end_value[lower] == None: smallest_end_value[lower] = seq[i] lic_length += 1 else: smallest_end_value[lower] = \ min(smallest_end_value[lower], seq[i]) return lic_length def solution(A): # We are solving this question by creating two mirrors. bound = max(A) + 1 multiverse = [] for point in A: # The point in the double-mirror universe. multiverse.append(bound * 2 + point) # The point in the mirror universe. multiverse.append(bound * 2 - point) # The point in the original universe. multiverse.append(point) return LongestIncreasingSubsequence(multiverse) |