AMIFIB - Editorial

editorial
, , , , , ,
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.

3 Likes
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.

7 Likes
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

1 Like
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.

21 Likes
5

@sikander_nsit, questions are not language dependent, some languages have advantages over others depending on the case. Competitors will always try and take advantage of their languages features.

1 Like
6

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.

7

test cases were weak

check the test case and solution given on this link

3 Likes
8

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 Likes
9

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!

4 Likes
10

@junior94 By language dependent I meant the same thing as one language being advantageous than other. My point was that a beginner who uses C/C++ would not have been able to solve this question. This should not be the case for the first(easiest) question in the contest.

4 Likes
11

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

1 Like
12

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

13

testers solution says 10256117644121029666 is a fibonacci no. but it isnt!

1 Like
14

ya definately there is something wrong with test cases !!

15

He is just doing the operations in a unsigned long long, so when ever over flow occurs he is JUST ALLOWING IT. It is equal to performing calculations modulo 2^64.

16

No, his solution is wrong. It says 10256117644121029666 is a fibonacci no., but it is not.

Your code link: http://ideone.com/WMDHVe
Tester code link: http://ideone.com/GLjOzF

1 Like
17

In the tester’s solution the mx limit upto which the fib sequence is calculated is taken as 6666.Is it just some random limit and if not then how’d we arrive to the no 6666.Someone please explain me the logic behind this.

18

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 ?

19

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 !

2 Likes
20

Tester’s solution also gives wrong answer for 10256117644121029666 which is not a fibonacci number.