DBFB - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

Author: anuj_2106

Tester: Suchan Park

Editorialist: Suchan Park

I wasn’t aware that the actual editorialist wrote an editorial here, but anyway I decided to upload my work to avoid confusion.

DIFFICULTY:

Easy

PREREQUISITES:

Almost none, good to know properties of Fibonacci numbers

PROBLEM:

Given two sequences A and B with size M, and an integer N, compute the result of this code modulo 10^9 + 7.

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]

QUICK EXPLANATION:

Analyze what the innermost loop is doing, and then it is easy to see that fib[N] is a linear combination of A[i] and B[j], and the coefficients of them form a fibonacci sequence. Then, write down the whole summation, and simplify it using the properties of summation.

EXPLANATION:

Let’s first analyze the innermost part of the loop. This part adds fib[N] to result, where fib is a sequence defined by the following:

  • fib[1] = A[i]
  • fib[2] = B[j]
  • For k \ge 3, fib[k] = fib[k-1] + fib[k-2]

As you can see from the name and the form of the recurrence, it is very similar to the well-known Fibonacci sequence. The only difference is that the first two terms are A[i] and B[j], not 0 and 1 (or 1 and 1) as usual.

Since the recurrence only sums up the last two elements, we can see that for each k, we can express fib[k] as

fib[k] = C_k \cdot A[i] + D_k \cdot B[j]

for some fixed constants C_k and D_k. Let’s find what C_k and D_k are. From the definition of the sequence,

  • fib[1] = A[i] = 1 \cdot A[i] + 0 \cdot B[j] \rightarrow C_1 = 1, D_1 = 0
  • fib[2] = B[j] = 0 \cdot A[i] + 1 \cdot B[j] \rightarrow C_2 = 0, D_2 = 1
  • For k \ge 3,
    • fib[k] = fib[k-1] + fib[k-2]
    • = C_{k-1} \cdot A[i] + D_{k-1} \cdot B[j] + C_{k-2} \cdot A[i] + D_{k-2} \cdot B[j]
    • = (C_{k-1} + C_{k-2}) \cdot A[i] + (D_{k-1} + D_{k-2}) \cdot B[j]
    • \rightarrow C_{k} = C_{k-1} + C_{k-2}, D_{k} = D_{k-1} + D_{k-2}

Now, using this recurrence, we are able to compute the values of C_{N} and D_{N} (using dynamic programming). Also, you can notice that C_{k} and D_{k} are successive elements of the fibonacci sequence (write down C_{k} and D_{k}, and you will see!)

In conclusion,

fib[n] = C_{N} \cdot A[i] + D_{N} \cdot B[j]

The outer loop just iterates all 1 \le i, j \le M and sums up all fib[N]. Therefore, we can write the value of result as:

\sum_{i=1}^{M} \sum_{j=1}^{M} \{ C_{N} \cdot A[i] + D_{n} \cdot B[j]\}

Use the properties of \Sigma to simplify the summation:

\begin{aligned} \sum_{i=1}^{M} \sum_{j=1}^{M} \{ C_{N} \cdot A[i] + D_{N} \cdot B[j]\} &= \sum_{i=1}^{M}\sum_{j=1}^{M} C_N \cdot A[i] + \sum_{i=1}^{M}\sum_{j=1}^{M} D_{N} \cdot B[j] \\ & = M \cdot C_{N} \cdot \sum_{i=1}^{M} A[i] + M \cdot D_{N} \cdot \sum_{j=1}^{M} B[j] \end{aligned}

Now, it is easy to calculate each part – we can construct the answer using the sums of array A and B, and the coefficients C_{N} and D_{N}. Note that we need to keep the answer value 10^9 + 7 during the whole computation, to avoid overflow.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.

2

https://www.codechef.com/viewsolution/18503035
what have i done wrong in this??

3

import java.util.;
import java.lang.;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner in=new Scanner(System.in);
int t=in.nextInt();
while(t–>0){
int m=in.nextInt();
int n=in.nextInt();
int a[]=new int[m];
int b[]=new int[m];
for(int i=0;i<m;i++)
a[i]=in.nextInt();
for(int i=0;i<m;i++)
b[i]=in.nextInt();

                int fact[]=new int[100001];
                fact[1]=1;fact[2]=1;fact[0]=1;
                for(int i=3;i<100001;i++){
                    fact[i]=fact[i-1]+fact[i-2];
                }
                int ans=0,mod=1000000007;
               if(n>2){
                for(int i=0;i<m;i++){
                    ans=(ans+((((fact[n-2]%mod)*(a[i]%mod))%mod)*(m%mod)%mod))%mod;
                    //ans+=(a[i]*fact[n-2]*m);
                    //System.out.println(ans);
                }
                for(int i=0;i<m;i++){
                    ans=(ans+((((fact[n-1]%mod)*(b[i]%mod))%mod)*(m%mod)%mod))%mod;
                    //ans+=(b[i]*fact[n-1]*m);
                    //System.out.println(ans);
                }}
                if(n==2){
                    for(int i=0;i<m;i++){
                    ans=(ans+((((fact[n-1]%mod)*(b[i]%mod))%mod)*(m%mod)%mod))%mod;
                    //ans+=(b[i]*fact[n-1]*m);
                    //System.out.println(ans);
                }
                }
                if(n==1){
                    n=2;
                    for(int i=0;i<m;i++){
                    ans=(ans+((((fact[n-2]%mod)*(a[i]%mod))%mod)*(m%mod)%mod))%mod;
                    //ans+=(a[i]*fact[n-2]*m);
                    //System.out.println(ans);
                }
                }
                
                System.out.println(ans);
	}
}

}