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.
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: CodeChef: Practical coding for everyone
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 : Emma and sum of products | HackerRank
1 Like
You may see the editorials of following problem for more details about FFT : Emma and sum of products | HackerRank
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 
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.
great explanation!
should be added to the editorial!
Thanks! Note that this solution is O(nk) and thus only gets 40 pts