Can anyone please explain step by step the approach to solve problem MOREFEB from June Long 2015.
The editorial was not so useful as it did not provide a detailed discussion.
Please note that I do not know about FFT and what is coefficient of x N-K thing mentioned in the editorial?
If possible, please mention the dp approach too which fetched 40 points.
Please help me out
Forget about FFT. Try to understand how to compute answer with recursive function g(l,r). This function returns vector of answers for all K in [0…r-l+1] on subarray S[l…r]. You can compute this function with divide-and-conquer method. To merge results from g(l,mid) and g(mid+1,r ) need just to multiply these vectors as polynomials, this part you need to understand. So, FFT needed only for fast multiplication to achieve better complexity.
see my solution
I am not able to understand the divide and conquer approach.
Please elaborate a little.
Recursive approach for 40 points
Use the identity fib(x1+x2) = fib(x1) * fib(x2+1) + fib(x1-1) * fib(x2)
Can be derived using matrix exponentiation!
For choosing k items from n if you choose any ith index you need to choose another k-1 items after i !
For substate i+1 to n for k-1 items you will be needing two things :-
1. fib(sum(s)) where s is subset of segment [i+1 to n] with cardinality k-1
2. fib(sum(s)+1) where s is again the same subset
If you already have answers for the range i+1 to n for k-1 items then using above identity you can get the result for k items when ith item is choosen at first place !
You may see the editorials of following problem for more details about FFT : https://www.hackerrank.com/challenges/emma-and-sum-of-products/editorial
I also tried to solve using DP, but managed to score 40 points only. I tried lots of optimisations but nothing helped. As you know fibonacci mod** is a periodic sequence and for **mod = 99991**, the **period = 33330**. So if the keys in set are in range 10<sup>9</sup> we can reduce it to **key 33330 and fibonacci numbers can be computed upto 33330th term easily using simple recurrence fib[n] = fib[n - 1] + fib[n - 2], without matrix exponentiation because of large values of keys in the set. Then simple recurrence can give the required sum.
Consider the Fibonacci Matrix F(n)
Consider the Solution Matrix Z[n][k]
So, the recurrence is, Z[k][n] = F[k] * Z[k - 1][n - 1] + Z[k][n - 1]
Now note that we don’t need 2x2 matrix for multiplication, as F[1][0] = F[0][1] and F[1][1] = F[0][0] + F[0][1], So lets see the multiplication R = F x Z
R[0][0] = F[0][0] * Z[0][0] + F[0][1] * Z[1][0]
= F[0][0] * Z[0][0] + F[0][1] * Z[0][1] (Because Z[1][0] = Z[1][0])
R[0][1] = F[0][0] * Z[0][1] + F[0][1] * Z[1][1]
= F[0][0] * Z[0][1] + F[0][1] * (Z[0][0] + Z[0][1]) (Because Z[1][1] = Z[0][0] + Z[0][1])
R[1][0] = R[0][1]
R[1][1] = R[0][0] + R[0][1]
Now the next thing is that 1 <= k <= n, so basically we need Z[105][105] sized 2x2 Matrix. But as we can reduce matrix computation as explained above, we need Z[105][105][2] and this is not possible, because the array size is too large. But if we see the recurrence we just need the result of (k - 1) cardinality subsets for computing the result for k cardinality subsets, So we can just do the computation using Z[105][2][2] and when n is odd, then Z[][0][] gives the previous step result, and when n is even Z[][1][] gives the previous level result.
This is how I computed the values.
z[0][0][0] = 1;
z[0][1][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
z[j][i & 1][0] = f[i][0] * z[j - 1][(i + 1) & 1][0] + f[i][1] * z[j - 1][(i + 1) & 1][1];
z[j][i & 1][1] = f[i][0] * z[j - 1][(i + 1) & 1][1] + f[i][1] * (z[j - 1][(i + 1) & 1][0] + z[j - 1][(i + 1) & 1][1]);
z[j][i & 1][0] += z[j][(i + 1) & 1][0];
z[j][i & 1][1] += z[j][(i + 1) & 1][1];
z[j][i & 1][0] %= mod;
z[j][i & 1][1] %= mod;
}
}
And Z[k][n & 1][1] is the result.
^could you explain your recurrence?
Thanks for your explaining your approach. It was helpful.
thanks. answers like these should be added to the editorial. 