MOREFB - Editorial

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

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

Editorial is not clear. Please explain the FFT part.

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

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

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

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

2 Likes

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

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

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

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.

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

Yes, it happens after Pisano period.

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

1 Like

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

1 Like

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

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

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

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

Explained in this answer:
http://discuss.codechef.com/questions/71544/morefb-editorial/71836

great explanation!
should be added to the editorial!

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