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

×

MOREFB - Editorial

PROBLEM LINK:

Practice
Contest

Author: Amit Pandey
Tester: Mahbubul Hasan and Sunny Aggarwal
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Minako Kojima

DIFFICULTY:

Medium-Hard

PREREQUISITES:

FFT, Divide and conquer

PROBLEM:

Given a set $S$ with $N$ elements and a number $K$, find $\sum_{s \subset S \land |s| = k} Fibo(sum(s))$

SHORT EXPLANATION

Since this is modulo a prime for which square root of 5 exists, we can calculate the $n^th$ fibonacci number modulo P as: $a(b^n - c^n) mod P$ for the correct values of a, b and c. Then finding the answer boils down to finding the coefficient of $x^{(N - K)}$ in the equation $(x + b^{a_1}) * (x + b^{a_2}) * .. * (x + b^{a_N})$. The multiplication can be done using FFT.

EXPLANATION:

Note that $mod = 99991$ is a prime number. There is a closed form for finding the $n^{th}$ fibonacci number:

$F_n = \frac{\sqrt{5}}{5}((\frac{1 + \sqrt{5}}{2})^{n} - (\frac{1 - \sqrt{5}}{2})^{n})$

Now since we are taking everything modulo $mod$, we can calculate each of the term modulo $mod$. So we will get an equation of the form:

$F_n = a(b^n - c^n)$

Where a, b and c are the corresponding values from the above equation modulo $mod$.

Now let us use this information to calculate the coefficient of b.

For example, if $S = {1, 2}$ and $K = 1$, then the answer is $F_1 + F_2$ = $a((b^1 + b^2) - (c^1 + c^2))$. Let us call the part with $b$ $g(b)$. We will discuss how to calculate g(b), calculating for the c part is similar.

Let us see the multiplication of $(x + b^1)(x + b^2)$. It comes out to be $x^2 + (b^1 + b^2) x + b^3$. Note that the coefficient of $x$ is the answer we require. Also, if $K$ were 2, then the answer would have been $F_3$ whose g(b) would be the coefficient of $x^0$. Seeing this pattern we can generalize the idea.

The g(b) for any $K$ is the coefficient of $x^{N - K}$ in the polynomial $(x + b^{a_1}) * (x + b^{a_2}) * .. * (x + b^{a_N})$.

So, how do we calculate this value? A naive implementation of the multiplication will TLE as it will take $O(N^2)$. However we can use FFT (the tutorial is in Russian you may have to translate it first) or Karatsuba's algorithm to speed up the multiplication.

Time Complexity:

O(N logN logN)

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution
Tester's solution

This question is marked "community wiki".

asked 15 Jun '15, 01:28

balajiganapath's gravatar image

6★balajiganapath ♦♦
75542742
accept rate: 77%

edited 07 Jul '16, 02:43

likecs's gravatar image

6★likecs
3.7k2279


19

Why can't the editorial be more clear, for those who are very new to such topics, finds many difficulty in learning them as we cannot understand anything by seeing someone's code. The main idea of editorials is for those who are willing to learn which is not sustained here(seems the editorial can be understandable by those who have already a idea about the topic.)

link

answered 15 Jun '15, 16:20

raghu_317's gravatar image

5★raghu_317
19815
accept rate: 0%

1

You may see the editorials of following problem for more details about FFT : https://www.hackerrank.com/challenges/emma-and-sum-of-products/editorial

(16 Jun '15, 12:12) amitpandeykgp4★

I propose an alternate solution:

We can prove by induction that the matrix:

[1 1]
[1 0]

raised to the n-th power gives

[F_n+1 F_n  ]
[F_n   F_n-1]

Let's call the matrix M, for short.

We should easily figure out that F_(a+b) is the top-right (or bottom-left) element of M^a * M^b

Then how can we use this to out advantage?

Well, if we dive deeper into this statement, we can argue that F_sum(V), over any V, is the top-right cell of the matrix product(M^V[i]).

Also, from M^a + M^b we can translate easily to F_a + F_b (we just take the element I recalled);


Let's summarize:

  • M^a + M^b <-> F_a + F_b
  • M^a * M^b <-> F_(a+b)

then SUM of F_(SUM of elements) can be translated to SUM of PRODUCT of corresponding matrices.

Let's continue.

If we take all subsequences of cardinality K, then FIBOSUM(k) is the sum of all PRODUCT(M^v[i]), for each v subsequence of V of cardinality K. If we further analyze this, by the rule of Viete, it turns out to be the (N-K)th term of the polynom P(X) = PRODUCT(X + M^V[i]), for i = 1,n. Basically, we have to find out the (matrix) coefficients of the polynom P(X), which can be done with divide et impera and FFT or Karatsuba (gave me TLE).

Why would this be better? Well, it's not. For this case at least. However, it does work in any case, no matter how the modulo is chosen.

link

answered 15 Jun '15, 18:20

retrograd's gravatar image

6★retrograd
1503
accept rate: 12%

edited 15 Jun '15, 18:38

Please could any one explain this editorial more. I really want to learn this problem.

link

answered 15 Jun '15, 15:32

apptica's gravatar image

5★apptica
939210
accept rate: 17%

I just wanted to point out that for the given constraints a simpler algorithm for polynomial multiplication, namely Karatuba, suffices (which has a runtime of $O(N^{\log_2(3)})$). This is cause the implementation of FFT is fairly involved and calls for maintaining complex values, whereas Karatsuba only requires integers and in essence is a simple divide-and-conquer algorithm.

Also for those curious, the closed form for $F_n$ mod 99991 ends up being:

$F_n = \frac{a^n - b^n}{a - b}$, $a = 55048$, $b = 44944$.

This is because the characteristic polynomial for $F_n$, i.e. $x^2 - x - 1$, has integer roots mod 99991 (since $\sqrt(5) = 10104 \in Z_{99991}$)

link

answered 15 Jun '15, 15:33

Amlesh's gravatar image

4★Amlesh
2393
accept rate: 0%

edited 15 Jun '15, 15:41

Hey, how did you calculate $a$ and $b$? I don't know what concept is used here. Please give me a link , if you have so I can read in detail.

(15 Jun '15, 23:17) filmwalams5★

@filmwalams you might have to read up on solving linear recurrences. Here's a good link for the Fibonacci sequence specifically: http://gozips.uakron.edu/~crm23/fibonacci/fibonacci.htm. The idea is that the characteristic polynomial factors nicely mod 99991:

$(x - 55048)(x - 44944) = x^2 - 99992x + 2474077312 = x^2 - x - 1 ($mod$ 99991)$.

(16 Jun '15, 01:42) Amlesh4★

The prime modulo 99991 is not suitable for use with NTT(Number Theoretic Transform), so we will have to resort to using FFT with complex doubles. To avoid rounding errors, after each polynomial multiplication, round the coefficients to the nearest integers. If using double still results in rounding errors, as it did in my case, replacing it with long double will eliminate the problem. This was my first time at solving an FFT problem and it feels nice to have learnt something new!

Solution link: http://www.codechef.com/viewsolution/7224276

link

answered 15 Jun '15, 15:50

bbackspace's gravatar image

4★bbackspace
9614
accept rate: 6%

Here is the DP approach that I used to solve this for 40 pts.

We notice that we need to evaluate sums of the form f(a + b) + f(b + c) + f(a + c). So we'll go to Wolfram's Fibonacci Numbers page to find a formula that might help us solve this problem. Scrolling down the page (and admiring the beauty of Fibonacci numbers), we stumble across this cute formula:

$F_{m+n} = \frac{1}{2}(F_mL_n + L_mF_n)$ where $L_n$ is the $n^{th}$ Lucas number (the Lucas series have the same recurrence as Fibonacci but different initial values). But how do we deal with the $L_n$ terms? Simple, another formula at the Lucas number page says,

$L_{m+n} = \frac{1}{2}(5F_mF_n + L_mL_n)$

The $n^{th}$ Lucas number can be found in the same way as Fibonacci numbers in $O(\log n)$ time with matrix exponentiation. So we now have found a way to build the $FIBOSUM(s)$ values as we consider more and more elements in $S$. Let's define $FS(n, k)$ as $FIBOSUM(S[1..n])$ for subsets of $k$ cardinality. We also define $LS(n, k)$ similarly with the Fibonacci function replaced by the Lucas function.

We will form the recurrence in the lines of $\binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1}$ which is formed by considering the two cases of A) not taking the $n^{th}$ element and B) taking it.

The recurrence for $FS(n, k)$ is a sum of two components, first being $FS(n - 1, k)$ where we do not take the $n^{th}$ element. The second is the sum,

$\displaystyle\sum_{i=1}^{t} F_{S[n]+m_i}$ if $FS(n - 1, k - 1) = \displaystyle\sum_{i=1}^{t} F_{m_i}$

which is equivalent to,

$\frac{1}{2}(F_{S[n]}(\displaystyle\sum_{i=1}^{t} L_{m_i})+L_{S[n]}(\displaystyle\sum_{i=1}^{t} F_{m_i})) = \frac{1}{2}(F_{S[n]}LS(n - 1, k - 1)+L_{S[n]}FS(n - 1, k - 1))$

The final recurrence becomes,

$FS(n, k) = FS(n - 1, k) + \frac{1}{2}(F_{S[n]}LS(n - 1, k - 1)+L_{S[n]}FS(n - 1, k - 1))$

$LS(n, k) = LS(n - 1, k) + \frac{1}{2}(5F_{S[n]}FS(n - 1, k - 1)+L_{S[n]}LS(n - 1, k - 1))$

$FS(1, 1) = F_{S[ 1 ]}$

$LS(1, 1) = L_{S[ 1 ]}$

Following is the pseudocode,

FS[1][1] = fib(a[1]);
LS[1][1] = luc(a[1]);
LS[1][0] = 2; //luc(0) = 2
for i = 2 to N
{
    LS[i][0] = 2; //luc(0) = 2
    for j = 1 to K
    {
        FS[i][j] = (FS[i-1][j-1] * luc(a[i]) + LS[i-1][j-1] * fib(a[i])) / 2 + FS[i-1][j];
        LS[i][j] = (5 * FS[i-1][j-1] * fib(a[i]) + LS[i-1][j-1] * luc(a[i])) / 2 + LS[i-1][j];
    }
}

Note that all operations in the pseudocode above are under mod 99991.

Solution link

link

answered 17 Jun '15, 17:47

bbackspace's gravatar image

4★bbackspace
9614
accept rate: 6%

edited 17 Jun '15, 19:25

great explanation! should be added to the editorial!

(17 Jun '15, 19:13) ironmandhruv4★

Thanks! Note that this solution is $O(nk)$ and thus only gets 40 pts

(17 Jun '15, 19:17) bbackspace4★

Interesting thing to know about Fibonacci numbers is that when we take mod with 99991 the Fibonacci cycle repeats itself after length of 33330 which can be verified here http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html#section6.1

link

answered 15 Jun '15, 16:22

ankurverma1994's gravatar image

4★ankurverma1994
405114
accept rate: 8%

Yes, it happens after Pisano period.

(16 Jun '15, 12:07) amitpandeykgp4★

Can it be of any use in this question?? Or do you know any question which uses this property

(16 Jun '15, 13:37) ankurverma19944★

We can implement the same strategy via matrix multiplication can't we ?

link

answered 15 Jun '15, 15:50

ranjanvittal's gravatar image

3★ranjanvittal
161
accept rate: 0%

Would be interesting to know if it can be solved for 100pts with matrix multiplication.

I solved 2 subtasks(40pts) with a DP solution and matrix exponentiation, if you're interested: http://www.codechef.com/viewsolution/7180786

(15 Jun '15, 15:56) bbackspace4★

@bbackspace, can you explain your approach a little bit, specially that lucas number part.

(15 Jun '15, 18:05) siddhartha44443★
(17 Jun '15, 18:09) bbackspace4★

Can anyone please explain the last part i.e. Also, if K were 2, then the answer would have been F3 whose g(b) would be the coefficient of x0

link

answered 15 Jun '15, 17:49

ronaldo_007's gravatar image

3★ronaldo_007
3112
accept rate: 20%

I waited two days for this editorial hoping to find a good FFT explanation relevant to this question, and examples.

link

answered 15 Jun '15, 18:46

vvneagleone's gravatar image

5★vvneagleone
903
accept rate: 0%

1

You may see the editorials of following problem for more details : https://www.hackerrank.com/challenges/emma-and-sum-of-products/editorial

(16 Jun '15, 12:09) amitpandeykgp4★

Why TL is so huge? Karatsuba version passed in 0.8 sec.

link

answered 15 Jun '15, 19:40

demidenko's gravatar image

2★demidenko
161
accept rate: 0%

I wrote Karatsuba with matrices as a coefficients, and my first implementation was running 4 minutes :)

Had to spend some time to improve it down to 3.5 seconds :)

I don't think it is bad to have such a huge TL, unless naive solutions can pass.

(16 Jun '15, 15:25) lebron7★

Editorial is not clear. Please explain the FFT part.

link

answered 15 Jun '15, 23:21

filmwalams's gravatar image

5★filmwalams
1.6k113141
accept rate: 7%

I learned fft from a very well written article, which is very friendly and not so hectic:

http://web.cecs.pdx.edu/~maier/cs584/Lectures/lect07b-11-MG.pdf

After understanding this, you can try reading some more papers and more easily feel for it. Google is our friend on this one!

link

answered 16 Jun '15, 00:11

retrograd's gravatar image

6★retrograd
1503
accept rate: 12%

When for S=1,2, it was coefficient in (x+b^a1)(x+b^a2)... then from where did the term (x-b^a1) come in generalization??? shouldn't it be (x+b^a1) or you should have explained that too... please reply soon

link

answered 17 Jun '15, 12:17

sanvens's gravatar image

1★sanvens
1
accept rate: 0%

How do you get the values of a,b and c?

link

answered 08 Apr '16, 19:51

durgaprasad726's gravatar image

1★durgaprasad726
11
accept rate: 0%

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,482
×2,557
×331
×156
×3

question asked: 15 Jun '15, 01:28

question was seen: 8,999 times

last updated: 07 Jul '16, 02:43