PROBLEM LINK:
Author: Andrii Omelianenko
Tester: Kevin Atienza
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Recursion, Dynamic programming, meet-in-the-middle
PROBLEM:
Let f(0) = 1, f(1) = 2 and f(i) = f(i - 1) + f(i - 2) for i > 1. How many ways are there to form the sum X using exactly K summands from the sequence f(0), f(1), f(2), \ldots? Note that summands may be used multiple times, but the summation order doesnāt matter.
QUICK EXPLANATION:
Let F(x,k,n) be the number of ways to form the sum x using exactly k summands from f(0), f(1), \ldots f(n-1). Then F can be calculated using the following recurrence:
with base case F(x,0,n) = [x = 0]. When implemented as a recursive function, and pruning using the fact that F(x,k,n) = 0 if kf(n-1) < x, this runs very quickly.
EXPLANATION:
Since order doesnāt matter, itās best to enumerate the summands in increasing order so we donāt count any sum more than once. We will keep this in mind throughout this editorial.
If X is small, then this problem can be solved straightforwardly using dynamic programming. Letās define F(x,k,n) to be the number of ways to form the sum x using exactly k summands from f(0), f(1), \ldots f(n-1). (We introduced the variable n so that we can perform the DP properly. Finding these hidden variables is usually the trick with DP problems.) The answer that we want is F(X,K,43) because f(42) is the largest f value that is \le 10^9 (the maximum possible value of X).
To find a recurrence for F(x,k,n), notice that there are two cases: whether f(n-1) is in the sum or not.
- If f(n-1) is not in the sum, then x is formed as a sum using exactly k summands from f(0), f(1), \ldots, f(n-2). There are F(x,k,n-1) ways to do that by definition.
- If f(n-1) is in the sum, then the remaining x - f(n-1) is formed using exactly k-1 summands from f(0), f(1), \ldots, f(n-1). (Notice that f(n-1) is still included because duplicate summands are allowed.) By definition, there are F(x-f(n-1),k-1,n) ways to do that.
Altogether, there are F(x,k,n-1) + F(x-f(n-1),k-1,n) ways to form x validly, and we have the recurrence
For base cases, if k = 0, then there are zero summands, so the sum can only be 0. Thus, F(0,0,n) = 1, and F(x,0,n) = 0 if x \not= 0. Also, there are other cases that make F(x,k,n) = 0, like the following:
- k > 0 and x = 0, because having at least one positive summand must result in a positive sum.
- k > 0 and n = 0, because thereās no possible choice of summands left.
- x < 0, because thereās no way to form a negative sum using a finite number of nonnegative summands.
If x is small, like in subtask 3, then this can be used to compute F(x,k,n) for x \le X, k \le K, and n \le 43, and therefore the answer. All we have to do is to create a 3D table to contain the F(x,k,n) values, and then fill it up in the right order. After doing so, we then have access to the correct value of F(X,K,43). The following pseudocode illustrates this:
def compute_answer(X,K):
F[0..X][0..K][0..43]
for x = 0..X:
for k = 0..K:
for n = 0..43:
if k == 0:
if x == 0:
F[x][k][n] = 1
else:
F[x][k][n] = 0
else if x == 0 or n == 0:
F[x][k][n] = 0
else:
F[x][k][n] = F[x][k][n-1]
if x >= f(n-1):
F[x][k][n] += F[x-f(n-1)][k-1][n]
return F[X][K][43]
The f(n) values can be precomputed beforehand, so they can be obtained via fast lookups.
The essence of DP is computing a table like this, and the trick is to know what to store and what the variables should be. Usually, the variables arenāt obvious, just like in our case where we added the variable n. Without it, the recursion doesnāt work.
This runs in O(XKN) time, where N is the number of distinct summands we are considering. (In our case, N = 43.) Unfortunately this only works for the third subtask, because for other subtasks, X is too large.
Instead, weāll describe a few solutions that work even for large X.
Solution 1
This solution uses the fact that there are only 43 f values that need to be considered, and that K is at most 10. For simplicity of explanation, letās assume that K = 10. (Other K s have similar approaches.) Also, it uses the fact that a sum of 10 summands can be decomposed into two sums, each containing 5 summands.
The idea is to first list all possible sums of 5 f values. How many are there? Using some counting techniques, we find that there are {47 \choose 5} = 1533939, which is quite reasonable. Now the remaining thing is to count how many ways are there to choose two sums from this list such that the sum is X. This is solvable with the following algorithm with two pointers:
- Sort all sums of 5 f values. Let this list be [s_1, s_2, \ldots, s_L] where L = 1533939.
- Initialize two pointers, i and j, with i initially pointing at the beginning of the list, and j at the end.
- For each i in increasing order, repeatedly decrement j to find the largest j such that s_i + s_j \le X. If s_i + s_j = X, then increment the answer by one.
Notice that this runs in O(L) because the pointer j never increases, so this passes the time limit for all subtasks. But there are two problems with this:
- We want the summands to be in increasing order. With the algorithm above, this is not necessarily the case. We can fix this by storing the minimum and maximum summand for each s_i, and then only incrementing the answer if the maximum summand for s_i is \le the minimum summand for s_j.
- The $s_i$s are not necessarily distinct. This means that we might need another inner loop to find all j s such that s_i + s_j = X.
Using these adjustments, we now have a solution that runs in reasonable time!
Solution 2
This solution uses the fact that the f values increase exponentially. Since K is small, it means that inevitably we will need to choose lots of f values that are near to X. Otherwise, we might not be able to achieve X, just because the remaining candidate summands arenāt large enough.
Specifically, the maximum sum we can get from f(0), \ldots, f(n-1) with k summands is k\cdot f(n-1), so if x is larger than that, then F(x,k,n) = 0 automatically. This reduces the amount of F(x,k,n) cases we need to check, and in fact itās significant enough: With this pruning, a normal recursive solution becomes very fast!
def F(x,k,n):
if k == 0:
if x == 0:
return 1
else:
return 0
else if x == 0 or n == 0:
return 0
else:
total = F(x,k,n-1)
if x >= f(n-1) and x <= k*f(n-1):
total += F(x-f(n-1),k-1,n)
return total
def compute_answer(X,K):
return F(X,K,43)
