Solution to Slalom-Skiing by codility

22 Oct


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.

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

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.

Leave a Reply

Your email address will not be published. Required fields are marked *