Tag Archives: k-server

My 1st Problem for HackerRank // Bangalore Bank

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

Problem statement

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.

Solution

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 dp[n][a][b] is the optimal cost for handling a prefix of length n of the input sequence in such a way that your fingers end up on keys a and b. From the problem statement we know that dp[0][a][b] equals 0 for all a and b. Lets define the recurrence relation:

dp[n][a][b] = \min_{x \in \{0, 1, \ldots, 9\}}(dp[n - 1][a][x], dp[n - 1][x][b])

Clearly the answer is \min_{a,b} dp[n][a][b]

Time complexity of this solution is O(n \cdot 10^3) 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.