PROBLEM LINK:
Author: Devendra Agarwal
Tester: Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
Dynamic programming
PROBLEM:
There are N ingredients, each having a taste score between 1 to 10. A dish is made out of the 2^N possible combinations of ingredients (including the empty set).
Planet A will pay for a dish the sum of the taste scores of ingredients in the dish, minus the sum of the taste scores of ingredients not in the dish.
Planet B will pay for a dish the sum of the taste scores of ingredients not in the dish, minus the sum of the taste scores of ingredients in the dish.
Each dish can be given only to one planet. What is the maximum amount of money that can be made? Give your answer modulo 10^7.
QUICK EXPLANATION:
For -10N \le t \le 10N and 0 \le i \le N, let F(i,t) be the number (modulo 10^7) of dishes S such that A(S) = t, considering only the first i ingredients. The answer can be calculated as:
F(i,t) can be computed with dynamic programming using the following recurrence:
where we define F(i,t) = 0 when |t| > 10N. For the base case, we have F(0,t) = 0 for t \not= 0, but F(0,t) = 1 for t = 0. By filling the table F(i,t) in increasing order of i, we will have access to the F(N,t) values, and then the answer can be computed.
EXPLANATION:
Let’s represent an ingredient as an integer from 1 to N, and a dish as a subset of the set of ingredients, [N] := \{1, 2, \ldots, N\}. Also, let’s write the taste score of ingredient i as t_i.
For a given dish S (which is a subset of [N]), let A(S) and B(S) be its value to planet A and planet B, respectively.
Note that the value of a dish can be negative. However, due to the way the planets calculate the value of a dish, it’s easy to see that A(S) = -B(S). Thus, if a dish has value to 2411 to one planet, then it has value -2411 to another planet. So to make the most money, there’s only one obvious choice of planet to give each dish to (unless its value is 0), and the amount of money we can get from a particular dish is just |A(S)| (or equivalently |B(S)|). So the answer is just the sum of |A(S)| for all dishes S.
Dynamic programming
Obviously, calculating this sum naïvely will not pass, because there are up to 2^N dishes. We need to find a better way. We can do so by exploiting the fact that 1 \le t_i \le 10, so the maximum |A(S)| among all dishes is 10N \le 10000.
For -10N \le t \le 10N and 0 \le i \le N, let F(i,t) be the number (modulo 10^7) of dishes S such that A(S) = t, considering only the first i ingredients. Such a function is useful to us because it gives us the number of dishes for each possible sum, so that the answer can be calculated as:
Now, it’s time to find a recurrence for F(i,t) (so that we can solve the problem with dynamic programming). Consider the i th ingredient. Its taste score is t_i. Also, let S be some dish from the first i-1 ingredients. There are two options: either to include the i th ingredient or not. If we include it, the value of the dish becomes A(S) + t_i, otherwise, it becomes A(S) - t_i. In the former case, we want A(S) + t_i to equal t, which means A(S) = t - t_i. In the latter case, we have A(S) = t + t_i. Thus, we now have the following recurrence:
where we define F(i,t) = 0 when |t| > 10N. For the base case, we have F(0,t) = 0 for t \not= 0, but F(0,t) = 1 for t = 0 (representing the empty dish having the value 0). This gives us a recurrence for computing F(i,t). By constructing a table for F(i,t) and computing its entries in increasing i order, we can now have access to the F(N,t) values and compute the answer. Don’t forget to reduce your values modulo 10^7!
The running time of this approach is O(sN), where s = t_1 + \ldots + t_N. Alternatively, it is O(t_{\max}N^2), where t_{\max} is the maximum t_i.
Improvements
There are a couple of improvements that can be done over the above approach.
Let’s start with a simple one. The above approach requires a table of size N\times 10N, or up to 10^7 entries. We can reduce this to just 2\times 10N by keeping only two rows of the table at a time, because we only need the previous row to calculate the next row. This gives us a significant improvement in memory usage.
We can even reduce this by using only one row. But to do so, we must offset each row. Let’s define a new function G(i,t) = F(i,t - (t_1 + t_2 + \ldots + t_i)). For a fixed i, row i of G is just row i of F offset (t_1 + \ldots + t_i) units to the right. It’s straightforward to compute a table entry for G given an entry for F, and vice versa, but in switching to G, we ensure that the indices of G are nonnegative, and we have the following equally-nice recurrence:
with base case G(0,t) = [t = 0]. (Iverson bracket notation).
Using this recurrence, we can compute each row of G from the previous row in place (i.e. without requiring separate storage for the previous and current rows), by computing the $G(i,t)$s in decreasing order of t.
We can still halve the memory usage! Notice that the only entries of G(i,t) that are nonzero are those where t is even. So we can define a new function, H(i,t), as G(i,t/2), and we have the following recurrence:
with base case H(0,t) = [t = 0]. Each row of H is only half the size of the corresponding row in G!
Connections with polynomials
We can state the F(i,t) values in terms of polynomials. Consider the “polynomial” F_i(x) = \sum_{t=-\infty}^{\infty} F(i,t) x^t. (We quote “polynomial” because it’s not really a polynomial; the exponent of x can be negative. Instead, this is called a Laurent polynomial.) Based on the recurrence for F(i,t), we can express F_i(x) in terms of F_{i-1}(x) as follows: (In the following, the sum is assumed to range across all integers t)
(The fourth step is just replacement of indices)
And for the base case, we have F_0(x) = 1. In fact, by unrolling this recursion, we can get:
Thus, F(N,t) is just the coefficient of x^t in \prod_{i=1}^N \left(x^{t_i} + x^{-t_i}\right).
The transition we did to using G(i,t) and H(i,t) can also be realized in terms of polynomials. Define G_i(x) and H_i(x) similarly as F_i(x). Then we have G_i(x) = x^{t_1+\ldots+t_i}F_i(x) and G_i(x) = H_i(x^2), and:
And G_i(x) and H_i(x) are actual polynomials, instead of just Laurent polynomials.
Finally, all these talk about polynomials isn’t just for theoretical interest; they can be converted into an algorithm too. Note that we can extract the H(N,t) values (and thus the answer) by computing the coefficients of H_N(x), so all we have to do is compute the following polynomial product:
But such a polynomial product can be computed quickly with FFT with binary splitting! In more detail:
- Define H_{a,b}(x) = \prod_{i=a+1}^b \left(x^{t_i} + 1\right). (In other words, H_{a,b}(x) = H_b(x) / H_a(x).)
- For a < c < b, we have H_{a,b}(x) = H_{a,c}(x) H_{c,b}(x).
- If b - a = 1, then H_{a,b}(x) is just x^{t_b} + 1.
- To compute H_{a,b}(x) for b - a \ge 2, let c = \left\lfloor \frac{a+b}{2} \right\rfloor, and compute H_{a,c}(x) and H_{c,b}(x) recursively. Then compute H_{a,b}(x) as the polynomial product of H_{a,c}(x) and H_{c,b}(x), which can be done quickly with FFT-based multiplication.
This gives us an O(Nt_{\max} \log (Nt_{\max}) \log N)-time algorithm!
Time Complexity:
O(sN) where s is the sum of all taste scores