DBFB - Unofficial Editorial

general
, , , , , ,
1

Practice

Contest

Author: Anuj Maheshwari

Editorialist: Vaibhav Jain

DIFFICULTY:

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
2

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

1 Like
3

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.

4

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…

5

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)

6

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