×

# MOREFEB discussion

 0 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 asked 15 Jun '15, 18:59 224●2●4●8 accept rate: 33%

 6 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 ! answered 15 Jun '15, 21:53 6★adkroxx 306●7●19 accept rate: 7% Thanks for your explaining your approach. It was helpful. (18 Jun '15, 12:16)
 1 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 109 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) $$\left[\begin{array}{cc}F(i - 1) & F(i) \\ F(i) & F(i + 1)\end{array}\right]$$ Consider the Solution Matrix Z[n][k] $$\left[\begin{array}{cc}S(i - 1) & S(i) \\ S(i) & S(i + 1)\end{array}\right]$$ 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. http://www.codechef.com/viewsolution/7206298 answered 18 Jun '15, 00:40 5★avmnusng 147●3 accept rate: 9% ^could you explain your recurrence? (18 Jun '15, 07:08) @ironmandhruv updated the answer. (18 Jun '15, 09:16) avmnusng5★ thanks. answers like these should be added to the editorial. :) (18 Jun '15, 14:11)
 0 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 answered 15 Jun '15, 19:50 16●1 accept rate: 0% I am not able to understand the divide and conquer approach. Please elaborate a little. (15 Jun '15, 21:25) You may see the editorials of following problem for more details about FFT : https://www.hackerrank.com/challenges/emma-and-sum-of-products/editorial (17 Jun '15, 07:54)
 0 DP solution explained here: http://discuss.codechef.com/questions/71544/morefb-editorial/71836 answered 17 Jun '15, 17:52 96●1●4 accept rate: 6%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×164
×156
×1

question asked: 15 Jun '15, 18:59

question was seen: 2,784 times

last updated: 18 Jun '15, 14:11