# DBFB - Unofficial Editorial

Practice

Contest

Author: Anuj Maheshwari

Editorialist: Vaibhav Jain

EASY-MEDIUM

### PREREQUISITES:

Linear Recurrence Relation

### PROBLEM:

You are given two sequences A and B, each with size M, and an integer N. Consider the following pseudocode:

``````result := 0
for i := 1 to M
for j := 1 to M
array fib[1..max(2, N)]
fib[1] := A[i]
fib[2] := B[j]
for k := 3 to N
fib[k] := fib[k-1] + fib[k-2]
result := result + fib[N]
``````

Compute the final value of the variable result

### EXPLANATION:

Well approach which I am providing is quite simple.
Consider sample test case:
3 n
1 2 3
4 5 6

Now, we know for n=1 nth terms for combinations (1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6) will be 1,1,1,2,2,3,3,3 i.e. m times the total sum of first array.

Same is for n=2 where we need to sum of second array and multiply with m.

Now when n>=3

``````        1+4=5
4+5=9

1+5=6
5+6=11

1+6=7
6+7=13

2+4=6
4+6=10

2+5=7
5+7=12

2+6=8
6+8=14

3+4=7
4+7=11

3+5=8
5+8=13

3+6=9
6+9=15
``````

for n>=3 what we can do is take three variables s1, s2 and s3. s1 will hold sum of first array mulplied with m and s2 will hold sum of second array multiplied with m. s3 will hold sum of s1 and s2. These are initial conditions.

Now what can we see from above series is that when n=3, we need to have
(1+4)+(1+5)+(1+6)+(2+4)+(2+5)+(2+6)+(3+4)+(3+5)+(3+6)
(1+2+3)*m + (4+5+6)*m
i.e. s1+s2 which will be stored in s3

for n=4,
(4+5)+(5+6)+(6+7)+(4+6)+(5+7)+(6+8)+(4+7)+(5+8)+(6+9)
(4+5+6)*m + (5+6+7+6+7+8+7+8+9)
i.e. s2+s3

hence for n>=3

for(int i=2;i<n;i++)
{
s3=(s1+s2)%mod;
s1=s2;
s2=s3;
}
print(s3)

### TIME COMPLEXITY:

O(n+m) per test case

### EDITORIALIST SOLUTION:

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

1 Like

I have done that in O(m+log(n)) which is a better and efficient approach â€¦ here is my solution link

1 Like

when I analysed the algo given in this problemâ€¦ what I realised was as belowâ€¦

letâ€™s take A[i]=a and B[j]=b in generalâ€¦ computing innermost loop as given would end up getting result+= afib(n-1) + bfib(n);

hence for each possible pair a and b , where a belongs to array A & b belongs to array Bâ€¦ the same formula would be usedâ€¦

hence all over

result=fib(n-1) * {sigma(A[k]) from k=1 to n} + fib(n) * {sigma(B(k) from k=1 to n} ;

hence I computed fib(n) and fib(n-1) both at a time in O(logn) using matrix multiplication methodâ€¦ and just got the resultâ€¦

Another similar approach would be finding s1 and s2â€¦ and then using that as initial matrix as

s2 s1

s1 0

and multiplying it till power N would do the same thingâ€¦

In my solution i skipped left element of 2nd row i.e. s1 because it would be same as 1st element of 2nd columnâ€¦

Note that here matrix M(n)=M^n represents

fib(n+1) fib(n)

fib(n) fib(n-1)

However there are some exception for n=1 and n=2 which should be kept in mind while writing above solutionâ€¦

I just want to point out that the tester did not cover all the test cases. He missed out on one test case which checks for N=1 .
For N=1 , the answer returned should be m*(sum of A[i]'s).
But since Tester did not cover this test case, even returning answer as (sum of A[i]'s) for N=1, is passing as correct, which is wrong.