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. Because the longest increasing subsequence is a very classic question withe O(NlogN) solution, the key point to solve this question is to covert its original form to the classic question. We would like to extend it with two mirror universe.

1 2 3 4 5 6 7 8 9 10 |
+--------+--------+--------+ | | | | | | | | |Original| mirror | mirror | | | #1 | #2 | | Points | | | | | | | | | | | | | | | +--------+--------+--------+ |

The original question is convert into: find the longest increasing subsequence in the new extended multiverse. Here is an example of extended multiverse:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Original universe: +------+ |X | | X | | X | | X | | X | +------+ Extended multiverse: +------+------+------+ |X | X|X | | X | X | X | | X | X | X | | X | X | X | | X | X | X | +------+------+------+ |

For each point P, it has three instances: the instance in the original world as P0, one in the mirror world as P1, and the last in the double-mirror world as P2. We process P2 firstly, then P1, and finally P0, so that to avoid the self-link sequence. In other words, we do not want that P2 is connected from P0 or P1, because they are essentially the same point.

The relationship between the original qualified subsequence (change direction at most two times) and the new longest increasing subsequence is 1:N mapping. Actually every subsequence in the original question has multiple equivalent subsequence in the new multiverse. Oppositely, every subsequence in the new multiverse has one equivalent in the original world.

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) |