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

×

MOREFEB discussion

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

megatron_64's gravatar image

4★megatron_64
224248
accept rate: 33%


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 !

link

answered 15 Jun '15, 21:53

adkroxx's gravatar image

6★adkroxx
306719
accept rate: 7%

Thanks for your explaining your approach. It was helpful.

(18 Jun '15, 12:16) megatron_644★

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

link

answered 18 Jun '15, 00:40

avmnusng's gravatar image

5★avmnusng
1473
accept rate: 9%

edited 18 Jun '15, 09:15

^could you explain your recurrence?

(18 Jun '15, 07:08) ironmandhruv4★

@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) ironmandhruv4★

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

link

answered 15 Jun '15, 19:50

demidenko's gravatar image

2★demidenko
161
accept rate: 0%

edited 15 Jun '15, 19:52

I am not able to understand the divide and conquer approach. Please elaborate a little.

(15 Jun '15, 21:25) megatron_644★

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) amitpandeykgp4★
link

answered 17 Jun '15, 17:52

bbackspace's gravatar image

4★bbackspace
9614
accept rate: 6%

edited 17 Jun '15, 18:12

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:

×164
×156
×1

question asked: 15 Jun '15, 18:59

question was seen: 2,784 times

last updated: 18 Jun '15, 14:11