You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 16 May '16, 00:31

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 17 May '16, 22:42


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(c)+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 code.

link

answered 16 May '16, 21:01

sumeetshirgure's gravatar image

6★sumeetshirgure
611
accept rate: 0%

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 :-(

link

answered 16 May '16, 20:03

rashomon's gravatar image

4★rashomon
813
accept rate: 22%

edited 16 May '16, 20:06

I also got stuck in the same place :(

(17 May '16, 15:22) anupam_datta4★

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.

link

answered 16 May '16, 15:45

sdssudhu's gravatar image

6★sdssudhu
1.1k310
accept rate: 15%

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 :)

link

answered 16 May '16, 16:22

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

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?

link

answered 16 May '16, 16:47

rishivikram's gravatar image

5★rishivikram
492110
accept rate: 14%

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

link

answered 18 May '16, 11:33

teja_734's gravatar image

3★teja_734
1
accept rate: 0%

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

link

answered 18 May '16, 14:57

rajan_parmar's gravatar image

5★rajan_parmar
396
accept rate: 0%

@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 .

link

answered 18 May '16, 15:10

rajan_parmar's gravatar image

5★rajan_parmar
396
accept rate: 0%

edited 18 May '16, 15:12

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×2,170
×1,672
×348
×141
×70

question asked: 16 May '16, 00:31

question was seen: 5,657 times

last updated: 18 May '16, 15:12