CHEFWD - Editorial

gamabunta · September 11, 2012, 3:23pm

PROBLEM LINK:

DIFFICULTY

EASY

PREREQUISITES

Math, Repeated Squaring, Fibonacci Numbers

PROBLEM

Find the number of ways to go from 0 to N, taking steps of 1 or 2, and taking exactly 1 back-step on the way of -1 or -2.

QUICK EXPLANATION

Let us assume that Ciel takes k steps forward, then one back, and the rest forward.

The number of ways she can accomplish this is fib(k) * [ fib(N-k + 1) + fib(N-k + 2) ]; since she can take only 1 or 2 steps back.

We have to find a summation of the above sequence for all k between 1 and N-1 inclusive. We can see that this needs to us to find summation of the form
∑_{k = 0 to N}fib(k)*fib(N-k)

This is also known as the convolution of the fibonacci series onto itself. Once we know how to solve this convolution efficiently, we can solve the problem.

EXPLANATION

There are several ways F(N) = ∑_{k = 0 to N}fib(k)*fib(N-k) can be found.

Formulas regarding the same have been listed on Wikipedia as well as OEIS. Finding a couple of smaller values and searching on OEIS is a solution to many a problem that asks you to find the result for a sequence of numbers.

If you’re into math, then using the concept of fibonacci polynomials, one can derive several relations as outlined in this wonderful paper.

I. F(N) = F(N-1) + F(N-2) + fib(N)

You can use the above identity and build a 4x4 matrix as follows

                                                                    |1 1 0 0|
[F(N) F(N-1) fib(N) fib(N-1)] = [F(N-1) F(N-2) fib(N-1) fib(N-2)] * |1 0 0 0|
                                                                    |1 0 1 1|
                                                                    |1 0 1 0|

Now you can use matrix exponentiation to calculate F(N) till the desired N to solve the problem.

II. F(N) = 2F(N-1) + F(N-2) - 2F(N-3) - F(N-4)

Similar to (I) you can construct a 4x4 matrix and use matrix exponentiation.

4x4 matrix and its exponentiation leads to slightly larger constants and needs several micro optimizations to stay within the time limit. Thus, a better approach is to not need to do matrix exponentiation over 4x4 matrices at all, as outlined in (III) below.

III. 5F(N) = (n - 1)fib(N + 1) + (n + 1)*fib(N - 1)

This elegant result is derived in this paper. Note that they assume fib[0] as 0 and fib1 as 1.

Using the above result we can say that we need to find
∑_{k = 1 to (N-1)}fib(k+1) * [fib(N-k + 2) + fib(N-k + 3)]
or ∑_{k = 1 to (N-1)}fib(k+1) * fib(N-k + 4)

We can rewrite the above as
F(N+5) - fib(0)*fib(N+5) - fib(1)*fib(N+4) - fib(N+1)*fib(4) - fib(N+2)*fib(3) - fib(N+3)*fib(2) - fib(N+4)*fib(1) - fib(N+5)*fib(0)

= F(N+5) - 2*fib(N+4) - fib(N+3) - 2*fib(N+2) - 3*fib(N+1)

A fibonacci number can be calculated by doing matrix exponentiation of a 2x2 matrix, which is very fast. We cal find fib(N+1) and fib(N) through one exponentiation of the matrix representation of fibonacci numbers and calculate fib(N+2), fib(N+3), fib(N+4), fib(N+5) and fib(N+6) from them.

You may notice that calculating F(N) requires you to divide an integer by 5. Since we maintain modulo all along to avoid overflows, we must calculate the division modulo 1000000007 as well.

This can be accomplished by finding the modular multiplicative inverse of 5, modulo 1000000007.

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

Sumudu · September 11, 2012, 4:33pm

Note that to account for not being allowed to back-step initially, we can simply consider both cases of the first step (1 or 2 forward) explicitly.

A different way to get expressions for the answer is to say:

After taking our back-step, if we have a distance k left to go the number of ways to finish is just fib(k) (with fib(0) = 1, fib(1) = 1).

Then if F(k) is the number of ways to travel k with exactly one back-step, our options for general k are:

step forward 1, then there are F(k-1) ways to continue
step forward 2, then there are F(k-2) ways to continue
step backward 1, then there are fib(k+1) ways to continue
step backward 2, then there are fib(k+2) ways to continue

So F(k) = F(k-1) + F(k-2) + fib(k+1) + fib(k+2), giving the Case I from above directly (after accounting for differences in how I indexed). Special cases are F(0) = 0 (since we are stopped and can’t take the required back-step) and F(1) = 5 (step forward 2 is not an option).

We can rewrite this in the form in Case II by noting fib(k+1) + fib(k+2) = fib(k+3) = F(k) - F(k-1) - F(k-2), so fib(k+1) = F(k-2) - F(k-3) - F(k-4) and fib(k+2) = F(k-1) - F(k-2) - F(k-3). Substituting these two into our expression for F(k) gives us the recurrence involving only F(k) (we should find F(2) and F(3) as special cases though).

From this expression we can easily write the characteristic polynomial x^4 - 2x^3 + x^2 - 2x + 1, and if we factor it to (x^2 - x - 1)^2 we can jump straight to eq. 1.10 in the paper linked above (assuming we know about such equations).

ankitdbst · September 11, 2012, 6:15pm

Did anyone get successful with the approach II ? I unrolled the inner loop for matrix multiplication for a total of 16xlog(N)xT Complexity, but still got a timeout (using both C, C++).

aarifjindani · September 11, 2012, 7:19pm

I did it with II.
I started with JAVA Solution.
Instead of using loops for matrix multiplications I wrote all 16 equations and changed the matrix power function from recursive to iterative still got TLE.
But then I changed the same code to C++ with above modification it got accepted.

ankitdbst · September 11, 2012, 8:45pm

I did exactly the same but with C++ then with C, still TLE. Even now I tried some i/o optimizations but couldn’t get through. Can you take a look? http://www.codechef.com/viewsolution/1348740
The program is really fast it runs for worst case of 10^15 and 10000 Test cases in 0.2s approx.

Sumudu · September 11, 2012, 8:57pm

It’s perhaps a little misleading to call your constant 16 there, since you haven’t simplified away any of the multiplications (i.e. you are still doing the same 64 multiplies that three nested loops would). There are certainly patterns you can take advantage of in these matrix powers to save some work; I don’t know about case II but the matrix in case I will always have zeroes in the top right 2x2, while the top left and bottom right 2x2’s are identical, for example.

ankit_shukla · September 11, 2012, 11:09pm

My solution too employed the 4*4 matrix multiplication. However, I pre-calculated all the 2-power matrices(i.e. mat^2,mat^4…) and used them for all test cases.

betlista · September 18, 2012, 2:35pm

4x4 matrix and its exponentiation leads to slightly larger constants and needs several micro optimizations to stay within the time limit. Thus, a better approach is to not need to do matrix exponentiation over 4x4 matrices at all, as outlined in (III) below.

I tried a lot but no success with Java for approach I. Without optimizations first solution in C++ passed.

ashwin1907 · December 12, 2012, 12:35pm

It think there is a slight mistake in the characteristic polynomial. It is coming out to be x^4-2x^3-x^2+2x+1, which is equal to (x^2-x-1)^2.

vjs17 · September 29, 2015, 1:20pm

GOOD SOLUTION

https://www.codechef.com/viewsolution/1348129

shashank2543 · September 29, 2015, 1:22pm

YES Its A truly Great Solution
https://www.codechef.com/viewsolution/1348129