CHEFMATH - Editorial

PROBLEM LINK:

Contest
Practice

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:

F(x,k,n) = F(x,k,n-1) + F(x-f(n-1),k-1,n)

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

F(x,k,n) = F(x,k,n-1) + F(x-f(n-1),k-1,n).

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)

AUTHORā€™S AND TESTERā€™S SOLUTIONS:

Setter
Tester

5 Likes

I solved this by using the property that if a number has to be achieved in k additions then it must have atleast one value greater than or equal to n/k. So i used recursion to assume all values of f greater than n/k are added and the remaining sum is found by having n=n-f and k=k-1.

Actually the answer never exceeded {10}^{9} + 7. Here is a simple recursive implementation without memoization which works quite fast. Solution Link

Basically in recursive solutions, you can either do memoization or cut down the needless length of recursive tree heights. In my solution, I cut down the height of recursive tree height by these 2 simple checks:

  1. Recurse in backward i.e. subtracting larger cfib numbers first (equivalently processing in decreasing order fashion).
  2. Also, since I was passing a cfib number as limit in the recursive call (limit indicates upto what numbers I can place further), if I could place a cfib number x times, the base condition used helped me cut the height by x times.

For further doubts, you can ask in comment section below :slight_smile:

The DP solution was quite obvious. However one thing surprised me the most. Due to large N in the third subtask, I had to use a map for the memoization. It timed out in the last test file of the last subtask. I had to change my approach completely to get AC(using zeckendorf representation). I saw one of my friends solution and he had a similar solution to my DP one but without memoization, it surprisingly passed for full 100 points. I want to ask, why was memoization slow in this case? Is it due to O(logN) insertions in map?

Can this be solved using the Zeckendorf representation of X? Find the Zeckendorf representation greedily, and let its length be len. If len > k, then ans = 0, since you canā€™t ā€œcombineā€ any two numbers in the representation to get a single Fibonacci number. Else, you have to ā€˜breakā€™ a Fibonacci number in the representation into smaller parts, such that the number of parts = k, and count the number of ways. This is where I got stuck :frowning:

1 Like

There is also a non-recursive solution :

  • First, find the Zeckendorf representation of X, (if its length is greater than k,ans=0)
  • From a linear combination of length k, we can make another combination of length k by using the fact (well, conjecture ), that f(a)+f(b)=fĀ©+f(d) is non-trivially true iff a=b+3=c+1=d+1. We can simply maintain a set of linear combinations, and ā€˜expandā€™ them exhaustively.
  • From a set of linear combinations of length k, we can ā€˜generateā€™ a set of linear combinations of length k+1 by splitting any f(a) -> f(a-1)+f(a-2), and further expanding the resulting set.(This works for small values of k)

Here is my


[1].


  [1]: https://www.codechef.com/viewsolution/10035947
3 Likes

I also got stuck in the same place :frowning:

why is this condition required F(x,k,n)=0 if kf(nāˆ’1)<x ?
And why is F(0,0,n)=1 ?

I had never expected solution wouldā€™t exceed 1e9+7 . Just one condition which reduce the unnecessary recursion enough for AC.

if(f[index] *k > x) return ;

TLE solution

AC Solution

@teja_734

k * f[n-1] < x

is actually the key .

Suppose sequence is 1,2,3,5,8,13 ā€¦

And you recursively comes at state n = 3 , k = 3 and x = 10 .

Now you can form maximum number using k = 3 and n = 3 is f[n-1] + f[n-1] + f[n-1] = 3+3+3 = 9 . But x is 10 . There is no way you can get X = 10 using k=3 and n=3 as you are left with only 1,2 and 3 i.e. f[0] , f[1] and f[2] . Hence no need to do further recursion .