Solution to Slalom-Skiing by codility

22 Oct

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.

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.

6 Replies to “Solution to Slalom-Skiing by codility

  1. 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 🙂

  2. my solution with C++

    https://app.codility.com/demo/results/trainingYA679V-MNC/

Leave a Reply

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

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!