UVa 607 - Scheduling Lectures

Problem Statement:
UVa 607 - Scheduling Lectures

Solution:
I think I've spent more time than I should on this problem.. But indeed there are tricky parts and non-obvious parts that make the assessment of the complexity of the solution difficult to intuitively comprehend.

Let D[i][k] be the minimum dissatisfaction index (DI) incurred if we have the i-th lecture ending at k-th topic. This translates to a very simple dynamic programming relationship: D[i][k] = min { D[i-1][j] + cost(j, k) } for all j that satisfy the constraints. The cost(j, k) function is the DI function given in the problem statement. With this approach, we have an \( O(LN^2) \) run time complexity, a very bad one.



As it turns out, there is a simple way to cut of much of the search space by doing the following: perform a forward pass to compute the minimum number of lectures needed by the time we reach k-th topic for each k, and lastly perform a backward pass to compute the maximum number of lectures admissible for each k-th topic. It surely decreases the search space significantly, but I am not entirely sure how to express the run time complexity accurately. But I am guessing that the addition of lower and upper limit does press the linear term N to a constant term.

Overall an interesting innocent looking problem.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int INF = 500000000;
int N, L, C;
int dp[1005][1005];
int low[1005];
int hi[1005];
int sum[1005];
int t[1005];

int getDi(int val) {
    if (val == 0) return val;
    if (val <= 10) return -C;
    return (val - 10) * (val - 10);
}

void solve(){
    sum[0] = 0;
    for(int i=1;i<=N;++i){
        sum[i] = sum[i-1] + t[i];
    }
    int trail = 0;
    int cnt = 1;
    for(int i=1;i<=N;++i){
        trail += t[i];
        if(trail > L) {
            trail = t[i];
            cnt++;
        }
        low[i] = cnt;
    }
    trail = 0;
    for(int i=N;i>=1;--i){
        trail += t[i];
        if(trail > L) {
            trail = t[i];
            cnt--;
        }
        hi[i] = cnt;
    }

    for(int i=0;i<1005;++i){
        for(int j=0;j<1005;++j){
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;
    low[0] = hi[0] = 0;
    for(int k=1;k<=N;++k){
        for(int i=low[k];i<=hi[k];++i){
            for(int j=k-1;j>=0;--j){
                int val = L - (sum[k] - sum[j]);
                if (val >= 0) {
                    dp[i][k] = min(dp[i][k], dp[i-1][j] + getDi(val));
                } else {
                    break;
                }
            }
        }
    }
    printf("Minimum number of lectures: %d\n", low[N]);
    printf("Total dissatisfaction index: %d\n", dp[low[N]][N]);
}

int main(){
    int tc = 1;
    while(scanf("%d",&N),N!=0){
        if(tc != 1)printf("\n");
        scanf("%d%d",&L,&C);
        for(int i=1;i<=N;++i) scanf("%d",&t[i]);
        printf("Case %d:\n", tc++);
        solve();
    
    }
}