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

×

FIBQ - editorial

5
4

PROBLEM LINK:

Practice
Contest

Author: Sunny Aggarwal
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica

DIFFICULTY:

MEDIUM

PREREQUISITES:

Fibonacci Numbers, Segment Trees

PROBLEM:

Given an array A consisting of N elements, Chef asked you to process following two types of queries on this array accurately and efficiently.

  • C X Y: Change the value of X-th element of array to Y i.e A[X] = Y.
  • Q L R: Compute the function F over the subarray defined by the elements of array A in the range L to R, both inclusive.

The function F(S) is defined as $F(S)=(\sum_{W\subseteq S}{Fibonacci(Sum(W))})\ modulo\ (10^9+7)$, where Sum(W) denotes the sum of all the elements in the sub-multiset W and Fibonacci(Z)=the Z-th Fibonacci number.

The function F applied over a subarray [L,R] of the array A is defined as F(S) where S is the multiset consisting of all the elements from the range [L,R] from the array A (i.e. S={A(L), A(L+1), ..., A(R)}).

EXPLANATION:

We can use the following property of Fibonacci numbers: Fibonacci(A+B)=Fibonacci(A)xFibonacci(B+1)+Fibonacci(A-1)xFibonacci(B).

With this property we can use a segment tree in order to efficiently process updates and queries. For each interval corresponding to a node of the segment tree we will store 3 values:

  • sfib = sum of the values Fibonacci(Sum(W)) (modulo $10^9+7$), for all the sub-multisets W
  • sfibm1 = sum of the values Fibonacci(Sum(W) - 1) (modulo $10^9+7$), for all the sub-multisets W
  • sfibp1 = sum of the values Fibonacci(Sum(W) + 1) (modulo $10^9+7$), for all the sub-multisets W

For the leaves of the segment tree we will initialize these values directly. For a leaf node L corresponding to a position i of the array A we will simply set:

  • L.sfib = Fibonacci(A[i])
  • L.sfibm1 = Fibonacci(A[i] - 1)
  • L.sfibp1 = Fibonacci(A[i] + 1)

Since A[i] can be pretty large, we need an efficient method of computing Fibonacci(A[i]) (and, in general, for computing Fibonacci(Y) for Y as large as $10^9$). There are multiple methods which can be used for computing these values in O(log(Y)) time. Below you can see one such function which uses memoization:

Fibonacci(y) {
    if (y <= 0) return 0;
    if (y <= 2) return 1;
    if (y in fibonacci_cache) {
        return fibonacci_cache[y];
    }
    int f, b, a;
    b = y / 2; // integer division
    a = y - b;
    f = (Fibonacci(a) * Fibonacci(b + 1) + Fibonacci(a - 1) * Fibonacci(b)) % MOD;
    fibonacci_cache[y] = f;
    return f;
}

For a non-leaf node node we can use the following function for computing its information based on the information available in its left and right children:

CombineIntervalInfo(left, right, node) {
    node.sfib = (left.sfib + right.sfib + left.sfib * right.sfibp1 + left.sfibm1 * right.sfib) % MOD;
    node.sfibm1 = (left.sfibm1 + right.sfibm1 + left.sfib * right.sfib + left.sfibm1 * right.sfibm1) % MOD;
    node.sfibp1 = (left.sfibp1 + right.sfibp1 + left.sfibp1 * right.sfibp1 + left.sfib * right.sfib) % MOD;
}

Processing an update operation X Y can be done as follows in O(log(N)) time. For the leaf node L corresponding to the position X from the array we reinitialize its values:

  • L.sfib = Fibonacci(Y)
  • L.sfibm1 = Fibonacci(Y - 1)
  • L.sfibp1 = Fibonacci(Y + 1)

Then, for every ancestor of the node L, starting from its parent and going up to the root, we recompute its information using the CombineIntervalInfo function.

Handling a query L R can be done as follows, also in O(log(N)) time. We find the O(log(N)) nodes of the segment tree such that the disjoint union of their intervals is equal to the interval [L,R]. Let these nodes be node(1), ..., node(K). If K=1 then the answer is node(K).sfib. Otherwise, we will we compute a tuple ANS containing the same fields sfib, sfibm1 and sfibp1 as the information stored for each segment tree node. We initialize ANS by combining the information from node(1) and node(2). Then, for every $3\leq i\leq K$ we update ANS by combining its information with that of node(i). At the end, the answer is ANS.sfib.

AUTHOR'S, TESTER'S AND EDITORIALIST'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 02 Apr '16, 12:45

mugurelionut's gravatar image

7★mugurelionut
10.0k266990
accept rate: 18%

edited 11 Apr '16, 18:28

admin's gravatar image

0★admin ♦♦
19.8k350498541

Can this be solved using the golden ratio?

(11 Apr '16, 18:36) ash_code3★

Can anyone explain how they are finding the sum of individual subsets in a given range?

(12 Apr '16, 20:01) suryavamsi2★
2

Excellent problem ,Poor editorial , with no explanation for Combineintervalinfo function..!! , it feels like like editorial wants us to digest us the solution without any explanation..!!

(14 Apr '16, 23:07) va1ts7_1003★

Answer is hidden as author is suspended. Click here to view.

answered 11 Apr '16, 17:38

sarvagya3943's gravatar image

4★sarvagya3943
(suspended)
accept rate: 36%

Let f(x) be the xth fibonacci number. Let M = [ [1,1], [1,0]].

Consider a 1-element range. The answer to this query is f(x) where x is the element, which is given by the [1][0] element of M^x. Let us call this A for now.

Consider now a 2-element range (x,y). Here the result must be f(x) + f(y) + f(x+y). Which is the [1][0] element of A + M^y + A.M^y where A = M^x and we use M^(x+y) = M^x.M^y . Now let us call this matrix as A.

Similarly for the 3-element range (x,y,z), we get the result as A + M^z + A.M^z and we can clearly see the recurrence kind of relation.

You can get 20 points for running a loop from l to r. But for 100 points you need to build a segment tree with each node containing a Matrix (yes, the segtree will be a 3-D array, an array of 2-D Matrices).

Here is the code. Took much less time than the editorial code and much much less heap memory.

link

answered 11 Apr '16, 19:35

atulshanbhag's gravatar image

4★atulshanbhag
22629
accept rate: 9%

Thank you Sir, for such a neat code. Wish everyone would write code of this clarity. (Y)

(17 Mar '17, 21:28) sumitjha43213★

I used Matrix exponentiation in my Solution I have added my explanation in it.

link

answered 11 Apr '16, 17:47

ashok1113's gravatar image

4★ashok1113
913
accept rate: 0%

It would be great if you can explain me how the multisets are generated of each interval in the segment tree from Fibo(A+B)?

link

answered 11 Apr '16, 22:05

typeof_yash's gravatar image

2★typeof_yash
411
accept rate: 0%

To partially answer your question: the interval multisets are not generated, it's not necessary. CombineIntervalInfo will calculate the correct answer, but I don't understand how. Specifically I don't understand how "F(A+B) = F(A).F(B+1) + F(A-1).F(B)" can be applied to Sum(F(Sum(s))) for s in multisets.

Here is an example where I computed the combination of [3, 4] and [1,2] and then [3, 4, 1, 2] separately, just to confirm it works: https://i.imgur.com/UwakZCg.jpg

(12 Apr '16, 03:44) luc4sdreyer4★
Answer is hidden as author is suspended. Click here to view.

answered 12 Apr '16, 20:32

javdroid_95's gravatar image

1★javdroid_95
(suspended)
accept rate: 0%

edited 12 Apr '16, 20:35

Where is the specific property described? What is its proof?

link

answered 11 Apr '16, 18:58

aragar's gravatar image

4★aragar
995
accept rate: 7%

I used the golden ratio and the polynomial multiplication approach https://www.codechef.com/viewsolution/9838337

link

answered 11 Apr '16, 19:55

apptica's gravatar image

5★apptica
949210
accept rate: 17%

A very nice problem, also excited for other approaches too.

link

answered 11 Apr '16, 17:37

saurabhsuniljain's gravatar image

2★saurabhsuniljain
8115
accept rate: 0%

@ash_code can be solved using golden ratio .. check this code check the last comments of this.

link

answered 11 Apr '16, 19:46

daoudakaleyire's gravatar image

2★daoudakaleyire
111
accept rate: 0%

There is one more optimization which should work for computing fibonacci. For modulus 10^9+7, pisano number was 2*10^9+18. So if number greater than this, we first take modulus with 2 * 10^9 + 18 and then compute Fibonacci.

link

answered 11 Apr '16, 20:15

saurabheights's gravatar image

4★saurabheights
11
accept rate: 0%

The problem could be made more challenging by introducing range update :)

link

answered 11 Apr '16, 22:26

mightymercado's gravatar image

4★mightymercado
2816
accept rate: 11%

may be not solvable also in given time or either lazy propogation also required ? can you explain solution idea...if this problem has range update also?

(14 Apr '16, 18:34) rcsldav20175★

good explanation can u describe how to done it with segment trees @atulshanbhag

link

answered 12 Apr '16, 02:27

rohitangira's gravatar image

2★rohitangira
939
accept rate: 0%

I also I don't find the relationship between Fibonacci(n+m) and F(A U {x}) intuitive at all. Does anyone have a justification of this, other than 'clearly' or 'notice' or 'easily see'?

link

answered 12 Apr '16, 18:42

tao_of_coding's gravatar image

3★tao_of_coding
12
accept rate: 0%

Here is a decent intro to segment trees: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

Here is a reference I used for Fibonacci generation: http://fedelebron.com/fast-modular-fibonacci

Hope that helps, though I think there is a little bit of mystery that noone has explained linked to regarding this particular function (not prereqs).

link

answered 12 Apr '16, 21:52

tao_of_coding's gravatar image

3★tao_of_coding
12
accept rate: 0%

Can some one explain how CombineIntervalInfo() generates multiset as well as the summation. Thanx in advance.

link

answered 12 Apr '16, 22:31

mr_za_11_0's gravatar image

3★mr_za_11_0
11
accept rate: 0%

whole time i was figuring out how can we get all subset of the set... as to me that was the main problem.. but after contest ended i came to know of -> (1+a)(1+b)(1+c)..(1+n)=1 + (allsubsetinproductform)... eg. (1+a)(1+b)(1+c)=1+a+b+c+ab+bc+ca+abc...

as u can see now we just can now easily use segment tree..

link

answered 13 Apr '16, 00:58

glow's gravatar image

3★glow
6312
accept rate: 0%

@rohitangira

Consider a segment tree "tree" where all nodes hold some matrix. Like I said in my previous comment, let us store in the leaf node, M^x where x is the corresponding element and M = [[1,1],[1,0]].

Now for a node which is not a leaf, we simply need tree[left] + tree[right] + tree[left].tree[right], where left and right are the left and right child respectively. We keep doing this recursively and build the segment tree.

Now for updating, we will update only one element and not a range. So we update a leaf node, and make sure to update all the ancestors of this leaf node. In other words, we are rebuilding the segment tree for every update. Also note, after using the array element initially to build the segment tree, the array is not needed anywhere else in the code. So actually when updating the array, we can only update the segment tree because all further computations will be held by the segment tree.

For query, I followed the basic segment tree propagation method (not lazy) to create a dummy matrix which will hold the data for the range query. This matrix will contain the final result. We only output the [1][0] element of this matrix. For further details, please read my code here and my earlier post. Cheers!

link

answered 13 Apr '16, 11:28

atulshanbhag's gravatar image

4★atulshanbhag
22629
accept rate: 9%

edited 13 Apr '16, 11:29

let array= [n1,n2,n3...nn]; A=(1+sqrt(5))/2 and B=(1-sqrt(5))/2 thus from a derivation i found Sum of all fibonacci multiset is=> 1/sqrt(5)*[(1+A^n1)(1+A^n2)...(1+A^nn)-(1+B^n1)(1+B^n2)..(1+B^nn)] with this fetch takes O(1) time. because:suppose x1=(1+A^n1) and y1=(1+A^n1) similarly x2=(1+A^n1)(1+A^n2) and y2=(1+B^n1)(1+B^n2). Thus if we make an array of x and y such as X=[x1,x1x2,x1x2x3,x1x2x3x4, to xn] and Y=[y1,y1y2,y1y2y3,y1y2y3y4, to yn]

thus for Q 1 5 we take (X5-Y5)/sqrt(5); thus happens in O(1) time. And to build this array we take O(n) time... I want to know why this approach is not suitable here?????? I have no clue whatsoever!!! I was getting wrong ans for this. I used long double for storing all double values!! can some one help??

link

answered 13 Apr '16, 16:32

liliput1992's gravatar image

3★liliput1992
1
accept rate: 0%

please give link to your code

(13 Apr '16, 17:49) atulshanbhag4★

could someone pls explain the reasoning/intuition behind the combineIntervalInfo() routine.

link

answered 14 Apr '16, 03:14

naivedya's gravatar image

3★naivedya
1
accept rate: 0%

Those who want proof of Fib(A+B) (Fibonacci shifting property) here it is!

link

answered 14 Apr '16, 22:19

redbaron's gravatar image

2★redbaron
1
accept rate: 0%

can anyone explain what we store in the node.sfibm1 and node.sfibp1 of a non-leaf node? I am able to understand what we store in node.sfib.. but can't able to understand the other two values stored.. plz reply..

link

answered 25 Apr '16, 14:24

shashank13_'s gravatar image

4★shashank13_
1915
accept rate: 0%

They are the sum over the same Fibonacci values as for node.sfib, but decreased by 1 (for node.sfibm1) or increased by 1 (for node.sfibp1). For instance, if node.sfib is Fibonacci(7)+Fibonacci(3)+Fibonacci(10), then node.sfibm1=Fibonacci(7-1)+Fibonacci(3-1)+Fibonacci(10-1) and node.sfibp1=Fibonacci(7+1)+Fibonacci(3+1)+Fibonacci(10+1).

(26 Apr '16, 19:33) mugurelionut7★

thanks.. for reply i have figured out

(26 Apr '16, 23:42) shashank13_4★
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,639
×2,586
×1,755
×137
×122
×23

question asked: 02 Apr '16, 12:45

question was seen: 9,236 times

last updated: 17 Mar '17, 15:58