## Friday, April 3, 2015

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

}
}