performance - How to position lilypads for leapfrogs?

Question

I've recently been practicing up on my problem solving skills in preparation for a high school programming competition and have encountered an interesting problem, Awesome Frog

The inaugural International Olympiad in Frogleaping is being held in Australia in 2013 and you are determined to win. While you want nothing to do with such slimy, jumpy creatures, you plan to enter a frog-like robot that you know will be faster than all the other organic entrants.

The IOF takes place in a large pond in which there is a sequence of lily pads arranged in a long line. The rules of the race are simple: your frog will be placed on the first lily pad, then it must jump to the second lily pad, then the third and so forth until it reaches the last lily pad in the course. Note that you can not `skip' lily pads--every lily pad must be jumped on exactly once. The first frog to reach the last lily pad will win the race. Since your robotic frog has super-frog speed, you are confident in your victory.

However, your frog has one minor incorrectable flaw--it is only able to jump one fixed distance. Specifically, it can only jump exactly K metres forward from its current location, even if this lands the frog in the water (where it will promptly short-circuit).

Since the initial lily pad positions may make it impossible for your frog to reach the last lily pad, you plan to create a distraction and move the lily pads so that they are spaced exactly K metres apart, enabling your frog to jump from the first to the last without falling in the water. Shifting a lily pad by one metre will take you one second, and the longer you spend stealthily moving lily pads, the more likely that the IOF judges will notice and disqualify you from the competition.

Given the initial distances between the lily pads in the course, you must write a program to compute the minimum time you will have to spend shifting lily pads such that all pairs of consecutive lily pads are exactly K metres apart. You can assume that the pond is sufficiently long so that the first lily pad can be moved any distance back, and the last lily pad can be moved any distance forward.

Example input and output at http://orac.amt.edu.au/cgi-bin/train/problem.pl?set=aio12sen&problemid=632

---

I've thought about this long and hard and I still cant think of any way to complete it given the time constraints or even disregarding that. Any reccomendations on how to approach this or any suggestions on algorithms/concepts to research would greatly be appreciated. Thanks in advance for the help.

Any code would be appreciated, preferably in c/c++, python, Java or c#. Thanks

Answer 1

In general, you can think about solving a problem in terms of modelling and design/implementation.

1. Restate the problem in your own words. In a science or math context, you would use mathematical notation where possible to make the definition precise and concise.
2. Define the operations possible. This is akin to the typical computer science approach where you define the operations possible on an abstract data type, or the events that can come into and out of your system.
3. Based on 1 and 2, design an algorithm.
4. Test and go back to step 3 if necessary, or even to steps 1 or 2 if you have found errors in your problem statement or operations -- or ways to restate the problem and define operations to make things easier to implement.

Modelling corresponds to stages 1 and 2, and design/implementation corresponds to stages 3 and 4.

As this is a practice problem for a high school competition and you have asked for how to approach it, I will attempt 1 and 2, and give some hints for 3. I'll leave 4 soley up to you: I find it hard to complete stages 1 and 2 without errors, so while there may well be some mistakes I hope what follows is still useful in indicating how you could proceed.

1 Problem statement

You have n circles, and you can jump forward by distance x (whose values are defined in your input file)

• Let the n circles be identified by the numbers 0 to (n-1)

• Let d[i], 1 ≤ i ≤ n-1, be the distance between circle (i-1) and circle i. (Whose initial values are defined in your input file)

The objective is to achieve: for all i, d[i] = x, using the minimum number of circle moves, where each move moves a circle a distance of 1 to the left or right.

2 Operations possible

For first and last circles

• Move first circle, circle 0 to left by y spaces: d[1] = d[1] + y

• Move first circle, circle 0 to right by y spaces: d[1] = d[1] - y

• Move last circle, circle n-1 to left by y spaces: d[n-1] = d[n-1] - y

• Move last circle, circle n-1 to right by y spaces: d[n-1] = d[n-1] + y

For any intermediate circles i, 1 ≤ i ≤ n - 1

• Move circle i to left by y spaces: d[i] = d[i] - y and d[i+1] = d[i+1] + y

• Move circle i to right by y spaces: d[i] = d[i] + y and d[i+1] = d[i+1] - y

To summarise

• for the first and last distances, you can add / subtract any number y
• for distances in the middle, you can add / subtract any number y but you have to balance this out by subtracting / adding y from an adjacent distance

3 Design an algorithm

There are many different approaches to designing an algorithm, but one of the best is to start with simple examples, translate them into your model, solve the model, and then see if you can generalize. This is the approach I would take here: once I'd solved simple examples, I'd throw nastier, edge cases at my algorithm until I was sure I had the problem licked.

Other approaches, which I have taken from the book Cracking the Coding Interview, include

• Reuse the wheel. See if you can find a similar problem. Either transform your problem into another problem and use the other problem's solution, or modify your problem sufficiently to see how it might be solved.

• Simplify the problem then gradually build your problem back up again. Make an assumption to make your problem easier. Solve with that assumption, then remove the assumption and modify your simple solution to incorporate the reintroduced feature. Keep going until you solve your original problem. An example could be to solve your problem with the constraint that the sum of the distances starts out as (n-1) * x and you are not allowed to move the first or last circles.

• Base case and build. Solve for just one distance, then for two distances, then for three distances. This may lead to an obvious pattern, or to a recursive solution where you can write your problem for N distances in terms of the problem for N-1 distances.

• Data structure and algorithms brainstorm a.k.a British Museum Algorithm. Think of all the computer science data structures and algorithms that might be relevant and see whether any work. A bottom-up approach!

Good luck!

Answer 2

Your choice where to position the first lilypad entirely determines the positions of the other lilypads (because they must all be distance K apart). For a given choice, the cheapest strategy is obvious—keep the lilypads in their original order (because any strategy in which two lilypads are transposed can be improved by not transposing them).

The problem is to minimise f(i) where i is the ending position of the first lilypad and the function f is the cost of moving all the N lilypads to be K apart starting from there.

Computing f for a given i is computationally fast - it's just arithmetic (we deduce the ending positions of each lily from the 'no transpositions' observation and sum the differences from the starting positions).

We could minimise f by brute-force search over all i, but this will probably be too slow (surely too slow, for this is an algorithms competition). So we need to search the space more intelligently. Binary search? No not quite, because that requires us to know what value we are looking for, and for f to be monotone.

What does f looks like? Think about this.

The function f is convex (U-shaped). Why? This follows from our 'no transpositions' observation. For any choice of i, some lilies will need to be dragged right, others left. If more lilies need to be dragged right than left, then we can improve f by moving the starting lily i (and the rest) one step to the right (f will decrease by the difference). Finally, observe the number of lilies that need to be moved right is a decreasing function of i, which is to say f'' >= 0. We have proved f to be convex.

Now we look-up or invent (fun) a fast binary-search-like algorithm to minimise general convex functions, and apply it. Or, easier, we can use bog-standard binary search to solve f'(i) = 0, where f' is the difference between the number of lilies that need to be dragged in each direction.

---

Remember, solve a problem on paper before you write any code. Programming is a distraction from thinking about the problem.

def solve(startings, K):
    N = len(startings)

    def ends(start):
        stop = start + N*K 
        endings = range(start, stop, K)
        assert len(endings) == N
        return endings

    def f(start):
        endings = ends(start)
        return sum(abs(x-y) for (x,y) in zip(startings, endings))

    def f_prime(start):
        endings = ends(start)
        cost = sum(cmp(x,y) for (x,y) in zip(startings, endings))
        return cost

    lower = min(startings) - N*K
    upper = max(startings) + N*K
    g = lambda x: -1 * f_prime(x)

    stationary_point = binary_search(g, lower, upper)
    i_best = min(stationary_point, stationary_point + 1, key = f)
    return f(i_best)

def binary_search(f, lower, upper):
    """Find the greatest integer n, lower <= n <= upper, such that f(n) <= 0. Assumes f is increasing."""
    assert upper >= lower
    assert f(upper) >= f(lower), "f must be increasing"
    assert f(upper) >= 0 >= f(lower), "f must have a root in range"

    while upper > lower+1:
        mid = (upper + lower) // 2
        if f(mid) <= 0:
            lower = mid
        else:
            upper = mid

    return upper if f(upper) <= 0 else lower

# unit tests
assert binary_search(lambda x: x - 4, 0, 6) == 4
assert binary_search(lambda x: x**2 - 5, 0, 10) == 2
assert binary_search(lambda x: x, 0, 6) == 0    
assert binary_search(lambda x: x-6, 0, 6) == 6

if __name__ == "__main__":
    import fileinput
    f = fileinput.input()
    N, K = [int(x) for x in f.readline().split()]
    gaps = [int(f.readline()) for i in range(N-1)]

    startings = [0]
    for gap in gaps:
        startings.append(startings[-1] + gap)
    assert len(startings) == N

    print solve(startings, K)

Answer 3

You input array (with one 0 prepended to it) should be converted to an array of the same size N with elements denoting the relative distance that each lily pad has to be moved if first lily pad is not to be moved at all. So, from array 0 8 3 6 4 we have 0 -2 1 1 3. From this array you should make another array of size 2*X whose elements denotes how many elements in original array have the value with element's index. This array has negative indexes (-X+1, X-1), but in programming you can use offset and just use regular array (0, 2X-1).

In our case this new array is '0 0 0 1 0 1 2 0 1 0 0`.

Now all you have to do is shift this array in one or the other directions until the sum of absolute indexes multiplied with values becomes minimal. Current sum is 1*|-2|+1*0+2*1+1*3=7. Because sum involving negative indexes is smaller than the sum involving positive you have to shift the array toward negative (to the left). Algorithm should maintain both left and the right sum, as well the sum of values that participate in those sums, as well the index of the "current zero value". In our case algorithm begins with left_sum=2, left_count=1, right_sum=5, right_count=3, and current_zero_index=0. The result of the algorithm is total_sum, which is initially left_sum + right_sum. Each time you shift to the right you correct these five values:

new_left_sum = left_sum + left_count + array[current_zero_index]
new_left_count = left_count + array[current_zero_index]
new_right_sum = right_sum - right_count
new_right_count = right_count - array[current_zero_index]
current_zero_index = current_zero_index + 1

After this if new_left_sum + new_right_sum is larger than some total_sum then current total_sum is the solution. Otherwise total_sum becomes this sum, and you repeat the process.

Shifting to the left is similar (but not exactly the same).