AMIFIB - Editorial

binary-search
cook40
easy
editorial
fibonacci
hashing
offline

#1

PROBLEM LINK:

Practice
Contest

Author: Vineet Paliwal
Tester: Roman Rubanenko
Editorialist: Jingbo Shang

DIFFICULTY:

Easy

PREREQUISITES:

Fibonacci Property, Quick Sort, Offline Algorithm, Hash, Binary Search

PROBLEM:

Given T big integers with at most D digits, determine whether it can be a fibonacci number. The total digits are L.

EXPLANATION:

There are a number of ways to solve this problem.

If you look up fibonacci properties online, you may find the followings:
n is a fibonacci number if and only if 5 * n * n + 4 or 5 * n * n - 4 is a perfect square number.
Using this property, together with big integer multiplication and sqrt, you can get the answer.

However, this method is too complex to pass this problem. It is worth noting that fibonacci number increases exponentially. And thus, there are only O(D) fibonacci numbers have at most D digits. This observation gives us the intuition to solve this problem much simpler.

The fist method is an offline version. First, we load all queries and sorted them. This step will take O(TDlogT) if we use quick sort. Second, we compute fibonacci numbers one after another using big integer addition. For each fibonacci number, check its relationship with the current smallest query number:

If the they are same, then the answer of that query is YES and let’s look at the next query number;
If the fibonacci number is smaller, then let’s look at the next fibonacci number;
if the fibonacci number is larger, then the answer of that query is NO and let’s look at the next query number.

This procedure needs O((D + T)D) time. Therefore, this offline version’s time complexity is O(TDlogT + (D + T)D).

The second one involves hash. We can simply generate O(D) fibonacci number and only restore the remainder of some relatively big number, for example, 2^64 or 10^9+7. And then, check the query number’s remainder to see whether it occurred using hash table or tree set. Suppose we use hash table, the time complexity is O(D + L).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.


#2

I used fast doubling method to compute all Fibonacci numbers uptil the 4800th Fibonacci number, because it has 1003 digits(just greater than 1000 digits) and then just checked if the query occurred in the computed list.

In fast doubling, using f(n) and f(n+1) we can compute f(2n) and f(2n+1).

f(2n) = f(n)(2f(n+1) - f(n))

f(2n+1) = (f(n+1))^2 + (f(n))^2

Click here to see my solution in Python.


#3

I got AC using the property that if n is a fibonacci number then 5 * n * n + 4 or 5 * n * n - 4 is a perfect square number. http://www.codechef.com/viewsolution/2996125


#4

This question was biased towards python, java and other such languages. I don’t think there were many C/C++ users who solved this without the BIGINT template and those who did would have suffered greater time penalty. In my opinion the easiest question of the contest should not be language dependent.


#5

Used arrays to store Fibonacci numbers.Each digit stored in different index. Somewhat similar approach as given in the tutorial for small factorials practice(easy). Worked fine.


#6

test cases were weak

check the test case and solution given on this link


#7

The input was not properly formatted. It cost me 3 penalties in python. I finally used int(raw_input()) instead of input() to scan integers and it got accepted :expressionless:


#8

Tester’s Solution uses a unsigned long long for a the number which is 1000 digits long!

Someone please explain how its working!

ALL SEE TESTER’s SOLUTION ONCE!


#9

Cant understand how the tester’s solution works for big numbers…can any1 explain?


#10

Hello @all,

I too attempted to solve this question in Python using the idea described in the first paragraph of the editorial and got multiple NZEC and WA veredicts… And I have to admit that precomputing the values up to a large limit never occurred me during the contest…

Can anyone just clear me if the test cases were well designed and there are actually numbers with up to 1000 digits there?

Also, I’m assuming that the tester’s solutions works since it implicitly uses the property of when an overflow occurs the value is “automatically” wrapped around the range of an ULL and this would serve as a (possibly very cumbersome) hashing technique?

Because if such trick doesn’t apply here then something was definitely wrong with the test cases I think…

Best,

Bruno


#11

We can simply generate O(D) fibonacci number and only restore the remainder of some relatively big number, for example, 2^64 or 10^9+7.

I don’t understand this part. Are we storing the Fibonacci numbers or number % 10^9 + 7 ?


#12

The testcases are weak. People who did the problem with unsigned long long int also passed the testcases. Basically, according to the testcases, storing fibonacci numbers MOD 2^64 would have passed all the test cases !


#13

@all : I am the setter for this problem .

You could generate all fibonacci numbers till 1000 digits ( no modulo is needed like the tester did ) and store them . The time limit and memory limit was conducive to do such a computation . You could store them in an array and do binary search for solving each query .

Or , otherwise you could use the fibonacci number property that 5nn + 4 or 5nn - 4 or both are perfect square to solve it . My solution ( setter’s solution ) uses it .

There were indeed test cases which had near about 1000 digits .


#14

What’ the problem with my solution??? It was not accepted but I compared the output with others solutions which are accepted. I took large numbers (like 354224848179261915075 fib(100)) also… My code works fine… but when I submitted,its giving wrong answer… http://www.codechef.com/viewsolution/3000210… Please help me…


#15

My solution is perfect… I ran the tester’s solution and it starts generating wrong fibonacci numbers after F(94)… So my solution was not get accepted… Tester’s F(95) - 1293530146158671551… My F(95) - 19740274219868223167…


#16

@all : Tester is not storing big numbers . He is storing number mod 2^64-1 . Since numbers overflow by themselves he is not doing modulo operation . While this approach may pass , this cannot guarantee correctness , and I am not surprised that it fails some of the test cases that users are talking about .


#17

@kurumua : I made the problem statement and test cases . The tester wrote and submitted his code after the test cases were posted . I discussed with the tester that “hashing” on any particular “modulus” can’t guarantee correctness . However since the output for the test cases was generated by my solution , the correctness was guaranteed . And we could not have prevented all possible “modulus” for hash from passing the test cases .

@kuruma : I agree that giving the “hashing” based solution to “editorialist” as a reference solution is highly misleading especially beginners . If you want you can write to codechef admin’s at bugs@codechef.com to get the “tester’s” solution replaced . I had already raised this issue during the problem setting process .


#18

@vineetpaliwal, thanks for your reply and cofirmation :slight_smile:

I will definitely e-mail codechef admins regarding this matter as soon as possible for me :smiley:

By the way, the problem was interesting and your idea for solving it was also very good :slight_smile:

Best,

Bruno


#19

I ran the tester’s code on my system, I am very sad to see that the output is ‘YES’ for all numbers greater than 10^64 :frowning:


#20

what is wrong in my solution ??