You are not logged in. Please login at www.codechef.com to post your questions!

×

DBFB - Editorial

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}^{N} 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.

This question is marked "community wiki".

asked 19 May, 18:15

tncks0121's gravatar image

2★tncks0121
137
accept rate: 0%

edited 10 Aug, 19:34

admin's gravatar image

0★admin ♦♦
19.3k348495534


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

link

answered 23 May, 11:31

veda_19's gravatar image

2★veda_19
11
accept rate: 0%

edited 23 May, 11:31

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,005
×3,393
×105
×3

question asked: 19 May, 18:15

question was seen: 871 times

last updated: 10 Aug, 19:34