I'm really happy because this is my first problem which I set for HackerRank. The problem was a part of Functional Programming Contest - September'14
The original problem statement is available here and I really encourage you to check it there. The short story is that you have to insert n numbers on a standard computer keyboard (without a numpad) using only two fingers in an optimal time. The time of pressing a single key is 1 and the time needed to move a finger from on key to another equals the distance between these two keys. In addition, initially you can place the fingers anywhere you want.
First of all, lets notice that we can ignore time needed for pressing keys during computation and add it while printing the result, since if we have to just press n keys, we have to spend n seconds for it.
It's tempting to assume that it's optimal to initially place fingers on the first two keys in the sequence or to assume that the optimal solution can always move the closest finger to handle the next key. Neither of these is correct. In order to proof that the first one is wrong, lets consider the following input: 1, 2, 9. If you place fingers initially on 1 and 2 the overall cost (remember we don't count time needed for pressing keys here) equals 9 - 2 = 7, but if you place fingers initially on 1 and 9 it leads to overall cost 1. To show that the second assumption is wrong, lets assume that you're in the middle of the sequence and fingers are on keys 1 and 9. The remaining portion of the sequence is the following: 1 2 1 2 ... 1 2 repeated as many time as needed. If you always move the closest finger to handle the next key you will keep moving a finger from 1 to 2 back and forth, but a better solution is to move a finger from 9 to 2 and that's your overall cost for handling all the incoming input.
So what's the correct approach? Actually this problem is an offline version of one of the most famous problems in online algorithms called k-server problem. While an online version is really hard to solve, in order to real with an offline version a simple dynamic solution suffices.
Lets notice that fingers are indistinguishable, so it doesn't mather which one is left or right. Lets define is the optimal cost for handling a prefix of length of the input sequence in such a way that your fingers end up on keys and . From the problem statement we know that equals 0 for all and . Lets define the recurrence relation:
Clearly the answer is
Time complexity of this solution is and the correctness follows immediately from dp definition and the recurrence relation. In order to achieve that complexity in a functional programming approach a good idea is to memoize dp function.