Problem Solving [Hal Burch, 2004]

In easier times, Farmer John's cows had no problems. These days, though, they have problems, lots of problems; they have P (1 <= P <= 300) problems, to be exact. They have quit providing milk and have taken regular jobs like all other good citizens. In fact, on a normal month they make M (1 <= M <= 1000) money. Their problems, however, are so complex they must hire consultants to solve them. Consultants are not free, but they are competent: consultants can solve any problem in a single month. Each consultant demands two payments: one in advance (1 <= payment <= M) to be paid at the start of the month problem-solving is commenced and one more payment at the start of the month after the problem is solved (1 <= payment <= M). Thus, each month the cows can spend the money earned during the previous month to pay for consultants. Cows are spendthrifts: they can never save any money from month-to-month; money not used is wasted on cow candy. Since the problems to be solved depend on each other, they must be solved mostly in order. For example, problem 3 must be solved before problem 4 or during the same month as problem 4. Determine the number of months it takes to solve all of the cows' problems and pay for the solutions. PROBLEM NAME: psolve INPUT FORMAT: * Line 1: Two space-separated integers: M and P. * Lines 2..P+1: Line i+1 describes problem i with two space-separated integers: B_i and A_i. B_i is the payment to the consult BEFORE the problem is solved; A_i is the payment to the consult AFTER the problem is solved. SAMPLE INPUT (file psolve.in): 100 5 40 20 60 20 30 50 30 50 40 40 INPUT DETAILS: The cows make 100 money each month. They have 5 problems to solve, which cost 40, 60, 30, 30, and 40 in advance to solve and then 20, 20, 50, 50, and 40 at the beginning of the month after the problems are solved. OUTPUT FORMAT: * Line 1: The number of months it takes to solve and pay for all the cows' problems. SAMPLE OUTPUT (file psolve.out): 6 OUTPUT DETAILS: +------+-------+--------+---------+---------+--------+ | | Avail | Probs | Before | After | Candy | |Month | Money | Solved | Payment | Payment | Money | +------+-------+--------+---------+---------+--------+ | 1 | 0 | -none- | 0 | 0 | 0 | | 2 | 100 | 1, 2 | 40+60 | 0 | 0 | | 3 | 100 | 3, 4 | 30+30 | 20+20 | 0 | | 4 | 100 | -none- | 0 | 50+50 | 0 | | 5 | 100 | 5 | 40 | 0 | 60 | | 6 | 100 | -none- | 0 | 40 | 60 | +------+-------+--------+---------+---------+--------+
ქართული თარგმანი არ არის დამატებული

problem solving

There are two ways that this problem can be solved in time, both based on dynamic programming. The first runs in O(P^3) time, independent of M. Let dp[X][Y] be the minimum number of months necessary to solve the first Y problems, with problems X through Y solved in the last month. To compute this, we need consider which problems were solved in the previous months in which we solved problems. Say we previously solved problems W through X-1; if sum[W..X-1] A[i] + sum[X..Y] B[i] > M, then we cannot do this in consecutive months and have to leave a month between to accumulate more money, otherwise we can do them consecutively. Iterating over all values of W for which problems W to X-1 do not themselves consume more than M money at the start or end of the month, we take the one that gives us the earlier possible start for X..Y. The other solution runs in O(P^2M) time. The states used for dynamic programming are the last solved problem and the amount of money left over after making the end payment for that problem. This is really the same information stored by the previous algorithm, since an (X, Y) pair says which problem was solved last (Y) and how much money is left after paying for it (M - sum[X..Y] A[i]). The implementation is conceptually a bit simpler; details are left to the reader. There is a way to reduce the runtime by a factor of P pointed out by a number of contestants. The method to reduce it for the O(P^3) solution is described here. The state transfer function of the dynamic programming function above is essentially dp[x][y]->dp[y+1][z] where sum[x...y]b[i]+sum[y+1..z]b[i] does not exceed m. Then if we fix y, decrease z, the range of possible x candidates to be considered can only increase as sum[y+1...z]b[i] is decreasing. Therefore, it suffices to track the optimum in the range as its being extended in linear time, bringing the total runtime to O(P^2) Note: this was meant to be an easy problem due to the well known nature of this type of DP state transition functions and the inclusion of schul on the contest. Therefore, the O(P^3) solution was deemed to be sufficient to get full points and the O(P^2) solution was overlooked Code by Relja Petrovic, who was one of the contestants who pointed this out: #include <cstdio> #define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++) FILE *fin,*fout; int m , p , vp[303] , vk[303] , dp[303] , cp[303]; int main(){ fin = fopen("psolve.in","r"); fscanf(fin,"%d %d",&m,&p); ffor(i,1,p+1) fscanf(fin,"%d %d",vp+i,vk+i); dp[0]=1; cp[0] = vp[0] = vk[0] = 0; int f,k,j,s; ffor(i,1,p+1){ dp[i]=1000000000; f=vp[i],k=vk[i]; for(j=i-1; j>=0 && f<=m && k<=m;--j){ s = dp[j]+2-(cp[j]<=m-f); if (s<dp[i] || (s==dp[i] && cp[i]>k)) dp[i]=s , cp[i]=k; f += vp[j]; k += vk[j]; } } fout = fopen("psolve.out","w"); fprintf(fout,"%d\n",dp[p]+1); fclose(fout);fclose(fin); return 0; }

Code by Relja Petrovic, who was one of the contestants who pointed this out

#include <cstdio>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)

FILE *fin,*fout;
int m , p , vp[303] , vk[303] , dp[303] , cp[303];

int main(){

	fin = fopen("psolve.in","r");
	fscanf(fin,"%d %d",&m,&p);

	ffor(i,1,p+1)
		fscanf(fin,"%d %d",vp+i,vk+i);
	
	dp[0]=1;
	cp[0] = vp[0] = vk[0] = 0;

	int f,k,j,s;
	ffor(i,1,p+1){
		dp[i]=1000000000;
		f=vp[i],k=vk[i];
		for(j=i-1; j>=0 && f<=m && k<=m;--j){
			s = dp[j]+2-(cp[j]<=m-f);
			if (s<dp[i] || (s==dp[i] && cp[i]>k))
				dp[i]=s , cp[i]=k;
			f += vp[j];
			k += vk[j];
		}
	}
	fout = fopen("psolve.out","w");
	fprintf(fout,"%d\n",dp[p]+1);

	fclose(fout);fclose(fin);

	return 0;
}