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(); } }