CPH003C - Editorial

PROBLEM LINK:

Practice
Contest

Author: Deepansh Parmani
Tester: Karan Malhotra, Dushyant Singh
Editorialist: Deepansh Parmani

DIFFICULTY:

EASY,

PREREQUISITES:

Loops,Fibonacci

PROBLEM:

Defining F(i) as F(i) = F(i-1) + 2*F(i-2) , given F(1) = a and F(2) = b find out F(i)%1000000007 t times

QUICK EXPLANATION:

the numbers of occurrences of a and b in F(i) is itself a fibonacci series

EXPLANATION:

If we observe the patter we will find that number of times a and b are present in F(i) is itself a a fibonacci sequence

F(1) = 1.a + 0.b
F(2) = 0.a + 1.b
F(3) = 2.a + 1.b
F(4) = 2.a + 3.b
F(5) = 6.a + 5.b
F(6) = 10.a + 11.b
.
.
.

1,0,2,2,6,10… and 0,1,1,3,5,11 are itself following the pattern i.e any number is sum of previous and twice the previous’s previous

let
hence number of times a is added is in F[i] will be - (times a in F[i-1]) + 2*(times a in F[i-2])

let \space A[i] \space be \space ith \space integer \space in \space pattern \space 1,0,2,2,6,10...
let \space B[i] \space be \space ith \space integer \space in \space pattern \space 0,1,1,3,5,11...

then \begin{equation} A[1] = 1 \space and \space A[2] = 0 \end{equation}

and \begin{equation} B[1] = 0 \space and \space B[2] = 1 \end{equation}

and

A[i] = A[i-1] + 2*A[i-2] % mod

and

B[i] = B[i-1] + 2*B[i-2] % mod

then we can precompute A[i] and B[i] upto to maximum value of n i.e is 10^5
then our ans is simply is (A[i].a + B[i].b)

Also we need to take mod with 1e9+7 at each step

ALTERNATIVE SOLUTION:

This question can be solved using matrix exponentiation in O(log(n)). Using this method we can calculate F(i) where i upto 10^18 .More about Matrix Exponentiation . This is shown in testers solution

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution(Karan Malhotra) can be found here.

What’s wrong with tescase 2?

I get WA for correct solution. It’s simple matrix exponentiation problem. Even author’s and tester’s solution receive Runtime Error (SIGSEGV) and Wrong Answer respectively.

Please, author of this problem, check testcase 2 and rejudge solutions.

This was an external contest. I fear nothing can be done about that.

Sorry for the late reply

It appears to me that they have changed some configurations from their old systems, and even AC solutions like the mine, tester’s and (this one)[CodeChef: Practical coding for everyone] are runtime errors
The test cases were fine when the problem was created and during it’s time,
but I am afraid I cannot edit testcases since my credentials for problem creation are revoked