Programming Forums - View Single Post - SMAC #1 [05-08]

Sane · Jun 1st, 2008, 3:59 PM

Attached to this post is the test data for Hurtles (Senior).

This problem requires a solution in Dynamic Programming.

If we think recursively, there are n hurtles, each with an option of jump or not jump. Obviously, this makes $2^n$ different choices if we were to brute force this recursively.

For n=100, $2^{100}$ is too large of a number to brute force. Those who might attempt a well-coded brute force solution could get it to work for n<20, and be awarded up to 75 points.

(Toggle Plain Text)

int hurtle(int h, int left) {
    if(left < 0) return INFINITY;
    if(h == n) return 0;
    return min( hurtle(h+1, left - energy[h]), 
                hurtle(h+1, left) + times[h] );
}

So now, what do we do if we want a solution that will score full points?

First, let's see why exactly this is a bad solution. If you think back to the fibonacci sequence, and its recursive function, why is it bad?

(Toggle Plain Text)

int fib(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

This recursive function will usually fail for anything larger than around 30. And why? Because we are doing the same calculations over and over and over.

Say we call fib(8):

fib(8) calls fib(7) and fib(6)
fib(7) calls fib(6) and fib(5)
fib(6) calls fib(5) and fib(4)
fib(5) calls fib(4) and fib(3)
fib(4) calls fib(3) and fib(2)
fib(3) calls fib(2) and fib(1)
fib(2) calls fib(1) and fib(0)
fib(3) calls fib(2) and fib(1)
...
Continuing on for many more iterations...

Repeated calls are happening all over the place, and these redundant calculations cause it to take exponential time.

How do we solve the problem of repeated calculations (also known as repeated subproblems)? You simply solve them in order.

(Toggle Plain Text)

int fib(int n) {
    if(n>=200) return -1;
    int fibs[200];
    fibs[0] = 0;
    fibs[1] = 1;
    for(int i=2; i<=n; i++) 
        fibs[i] = fibs[i-1] + fibs[i-2];
    return fibs[n];
}

This new fibonacci function is dramatically improved from $O(k^n)$ to $O(n)$ time.

This is perhaps one of the simplest examples of Dynamic Programming. A recursive function can be converted into an iterative DP function if and only if its subproblems can be uniquely identified and solved in the correct order.

Let's identify the subproblem for Hurtles:

Let h be the hurdle such that all hurdles from h .. n remain unused.
Let e represent the joules of energy remaining.
Then Penalty(h, e) represents the minimum time penalty for this subproblem.

After a little bit of thought, we come to this formula:

(Toggle Plain Text)

Penalty(h, e) = min( 
    Penalty(h+1, e - energy[h]), 
    Penalty(h+1, e) + times[h] 
);

Now, the somewhat startling observation is, this is exactly the same as the recursive function developed earlier in this post! This is actually characteristic of any DP program that you may see in time.

Now, what about the order that we solve each subproblem in? That would be from right to left for each hurdle (since each subproblem relies on h+1). And from 0 .. max energy for each joule of energy (since each subproblem relies on less energy than currently held).

So where fibonacci numbers can be reduced to a DP problem that requires a 1-dimensional array, this problem can be reduced to a DP problem that requires a 2-dimensional array. We simply walk through each subproblem, and use our recursive formula to solve the problems in the correct order.

(Toggle Plain Text)

n is the number of hurdles
j is the maximum energy

for(h=n-1; h>=0; h--) {
    for(e=0; e<=j; e++) {
        if(e >= energy[h]) Penalty[h][e] = min(Penalty[h+1][e-energy[h]],
                                               Penalty[h+1][e]+times[h]); 
        else Penalty[h][e] = Penalty[h+1][e]+times[h];
    }
}

If you just squint your eyes a little bit, you'll see it still looks like our recursive function developed earlier. The only difference is it's much smarter about how much work it does. It only solves each subproblem once, and there's a maximum n*j subproblems. That makes this solution $O(nm)$ or 100*10,000 = 1,000,000, which is very fast for even the worst case.

Here is the official solution, written in C:

 C Syntax (Toggle Plain Text) 
#include <stdio.h>
#define MAXN 101
#define MAXJ 10001
#define min(a,b) ((a)<(b)?(a):(b))
 
int energy[MAXN];
int times[MAXN];
int n, j;
 
int best[MAXN][MAXJ] = {0}; // best[h][e] : The minimum time penalty given hurdles 'h .. n' and 'e' joules remaining
 
int main() {
    int h, e;
 
    freopen("hurtles.in", "rt", stdin);
    freopen("hurtles.out", "wt", stdout);
 
    scanf("%d %d", &n, &j);
    for(h=0; h<n; h++) scanf("%d %d", &energy[h], &times[h]);
 
    for(h=n-1; h>=0; h--) { // Solve hurdles right to left
        for(e=0; e<=j; e++) { // Solve energy from 0 .. max energy
            if(e >= energy[h]) best[h][e] = min(best[h+1][e-energy[h]], best[h+1][e]+times[h]); 
            else best[h][e] = best[h+1][e] + times[h];
        }
    }
 
    printf("%d\n", best[0][j]);
    return 0;
}
#include <stdio.h>
#define MAXN 101
#define MAXJ 10001
#define min(a,b) ((a)<(b)?(a):(b))

int energy[MAXN];
int times[MAXN];
int n, j;

int best[MAXN][MAXJ] = {0}; // best[h][e] : The minimum time penalty given hurdles 'h .. n' and 'e' joules remaining

int main() {
    int h, e;
    
    freopen("hurtles.in", "rt", stdin);
    freopen("hurtles.out", "wt", stdout);
    
    scanf("%d %d", &n, &j);
    for(h=0; h<n; h++) scanf("%d %d", &energy[h], &times[h]);

    for(h=n-1; h>=0; h--) { // Solve hurdles right to left
        for(e=0; e<=j; e++) { // Solve energy from 0 .. max energy
            if(e >= energy[h]) best[h][e] = min(best[h+1][e-energy[h]], best[h+1][e]+times[h]); 
            else best[h][e] = best[h+1][e] + times[h];
        }
    }
    
    printf("%d\n", best[0][j]);
    return 0;
}