SRM 528 Colorful Cookie

We are given an array cookies of N (≤50) elements, where cookies[i] is the number of cookies of color i. For each i, have to choose a multiple of P1, say P1x_i and a multiple of P2, say P2y_i cookies of color i. This must be done in such a way so that each of the x_i 'orders' are paired off with some y_j order and i≠j.

In order for a choice of x_i's and y_i's to be a valid pairing, it is necessary and sufficient that for each i, x_i≤∑_j≠iy_j and y_i≤∑_j≠ix_j and ∑x_i=∑y_i. A straightforward application of Hall's Marriage Theorem yields this condition. Both these equations rearrange to x_i+y_i≤S for all i, where S=∑x_i=∑y_i.

For a valid choice of x_i's and y_i's, the number of cookies that we can eat is ∑(P1x_i+P2y_i)=(P1+P2)*S. That is, we have to maximize S.

Let us reformulate the problem more precisely. We have to choose (x_i,y_i)'s such that ∑x_i=∑y_i=S(say). And for each i, P1x_i+P2y_i≤cookies[i] and x_i+y_i<=S. We have to maximize S.

Observe that if some S is attainable, so is S−1. To see this, delete pick a matched pair of orders between x_i and y_j and decrement both. You can check that all conditions remain satisfied. (We are just taking a perfect bipartite matching and deleting a matched edge along with its endpoints.) Because of this monotonicity property we can binary search for the maximal attainable value of S. So now our problem reduces to: Given S, find out if a configuration with value S is attainable.

Let us try to solve this subproblem with dynamic programming. The first state that comes to mind is f(i,X,Y) = true iff there is some choice of x₀..x_i and y₀..y_i with x_j+y_j≤S and ∑x_j = X and ∑y_j = Y. This is correct, but since S can be upto 1000 (since each cookies[i]≤2000 and P1,P2 >= 50 we have x_i + y_i ≤ 2000/50 = 40. And 2S = ∑(x_i+y_i) ≤ 40.N ≤ 40×50 = 2000, so S≤1000. So this approach has a good chance of getting a TLE.

We can come up with a better approach, by shifting the recurrence parameters around. Define the function g(i,Y) = maximum value of X=∑_j=0ⁱx_j possible with Y=∑_j=0ⁱy_j and x_j+y_j≤S. Suppose when computing g(i,Y) we fix y_i, then we should take the highest value of x_i as allowed by the constraints, which is max((cookies[i]−P2*y_i)/P1,S−y_i). y_i can range from 0 to cookies[i]/P2 which is at most 40. The number of operations would be around N×1000×40≤2×106. And we do the entire procedure log(1000) times. This should fit well within the time limit.