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 | 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 | 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) |
Looks like this guy http://massivealgorithms.blogspot.com/2016/12/solution-to-slalom-skiing-by-codility.html is trying to copy you, but he can’t get the styling right.
hah, they did not use the copy-paste in the correct way 🙂
https://app.codility.com/programmers/lessons/90-tasks_from_indeed_prime_2015_challenge/slalom_skiing/
In the picture on that site it is claimed a max of 8 gates can be hit. but the answer is infact 9.
travelling Right 0, 1, 3, 4
Turn left 5, 6
turn right 7, 10, 12
Did you catch that in your solution or am I going insane?
In addition:
What if you have a starting array that looks like mirror#1 ie. its is over all decreasing?
In that case you want the original in the middle with mirrors either side so you stand the best chance of passing as many gates.
I’m really having a problem trying to figure out an accurate test for this challenge 🙂
Just double checked, both the solution and the picture show answer 8.
It says in the description: You want to ski to the left at the beginning.
my solution with C++
https://app.codility.com/demo/results/trainingYA679V-MNC/