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

×

AMIFIB - Editorial

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.

This question is marked "community wiki".

asked 18 Nov '13, 00:12

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

edited 18 Nov '13, 22:01

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446376


19

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.

link

answered 18 Nov '13, 01:05

sikander_nsit's gravatar image

5★sikander_nsit
1.5k82130
accept rate: 0%

edited 18 Nov '13, 01:12

1

@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.

(18 Nov '13, 01:19) junior944★
4

@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.

(18 Nov '13, 01:42) sikander_nsit5★
1

@junior94 this is not a platform to test language skills. If algorithmic skills were to be tested, the limits would have been within 10^18.

(18 Nov '13, 17:46) rishul_nsit4★

@rishul_nsit, I didn't say it was a platform to test language skills, I only said that users usually take advantage of their language features. In cook offs it's always better to do a task in the shortest way possible. I won't deny that python and java had a significant advantage over C and C++ but this is not the first time that a question regarding BigInteger is appearing and possibly not the last either. But I must agree with @sikander_nsit statement too, for one of the easiest problems in the cook off, it required a significant amount of coding.

(18 Nov '13, 18:23) junior944★

@junior94 what I meant was such questions should appear in Long contests and not the cook offs

(18 Nov '13, 23:01) rishul_nsit4★

Those who know java or python well can easily solve it.... I applied the logic that if 5nn + 4 or 5nn - 4 is a perfect square number then the number would be fibinoci number... but that will not fit in the normal data types...this may be an easy problem....but not a confidence booster for newbies like me who are learning to swim in the pool of c++...:(

(18 Nov '13, 23:12) bipin23★
showing 5 of 6 show all

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

link

answered 18 Nov '13, 01:31

bminus's gravatar image

5★bminus
206114
accept rate: 0%

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.

link

answered 18 Nov '13, 00:51

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

edited 18 Nov '13, 01:01

Fast doubling method ! Thanks for a new concept :)

(19 Nov '13, 16:02) beethoven4★

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!

link

answered 18 Nov '13, 01:36

prakhs123's gravatar image

4★prakhs123
33641019
accept rate: 3%

edited 18 Nov '13, 01:37

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.

(18 Nov '13, 06:29) anudeep20116★
1

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

(18 Nov '13, 07:11) prakhs1234★

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 Nov '13, 07:50) sagar1pant72★

admin please answer!!!

(18 Nov '13, 16:26) prakhs1234★
1

As described, the method is based on hashing technique. Numbers which are bigger than ULL are automatically stored as remainders of this max value. Now when you take the input as string and convert it to number again and if IT ALSO generates the same remainder (after being 'wrapped' around ULL_MAX) will be found in the set, otherwise not.

This obviously assumes that there are no two numbers (one of which is Fibonacci while other not) that give same remainder, atleast in the given constraints). This technique however, doesn't guarantee solution and may or may not work.

(18 Nov '13, 23:40) vivekiitkgp2★

test cases were weak
check the test case and solution given on this link

link

answered 18 Nov '13, 01:25

nipun_poddar's gravatar image

4★nipun_poddar
563
accept rate: 0%

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

(18 Nov '13, 11:48) parispar4★

@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 .

link

answered 19 Nov '13, 13:30

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107171
accept rate: 12%

5

Was this done in purpose so Tester's solution would pass? Because while hashing is a nice and general technique, it shouldn't be used in such "tricky"/improvised way as it might mislead some beginners as to when to use hashing or not... The fact that the test cases were "good" enough so that this "natural hashing" technique would pass makes me think that this was done in purpose as this solution can't even guarantee correctness...

(19 Nov '13, 15:18) kuruma3★

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 !

link

answered 18 Nov '13, 11:45

beethoven's gravatar image

4★beethoven
2893512
accept rate: 8%

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

link

answered 18 Nov '13, 01:00

n2n_'s gravatar image

5★n2n_
1.8k61319
accept rate: 9%

Cant understand how the tester's solution works for big numbers...can any1 explain?

link

answered 18 Nov '13, 01:49

chalubhalu's gravatar image

4★chalubhalu
2882411
accept rate: 6%

@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 .

link

answered 18 Nov '13, 18:17

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107171
accept rate: 12%

edited 18 Nov '13, 18:18

3

Can you explain how the tester is storing 1000 digit numbers into a set of unsigned long long !

(18 Nov '13, 20:07) v_akshay4★

@vineetpaliwal, thanks for your reply and cofirmation :)

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

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

Best,

Bruno

link

answered 19 Nov '13, 18:00

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

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 :(

link

answered 19 Nov '13, 18:15

shreyans1995's gravatar image

5★shreyans1995
172
accept rate: 0%

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.

link

answered 18 Nov '13, 01:23

akiitkgp's gravatar image

3★akiitkgp
11
accept rate: 0%

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

link

answered 18 Nov '13, 02:03

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

1

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

(18 Nov '13, 02:29) prakhs1234★

ya definately there is something wrong with test cases !!

(18 Nov '13, 02:47) nipun_poddar4★

@nipun_poddar : There is no issue with test cases . There is definitely an issue with "tester's" solution .

(19 Nov '13, 15:58) vineetpaliwal6★

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 ?

link

answered 18 Nov '13, 10:40

gautam94's gravatar image

3★gautam94
474142646
accept rate: 11%

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

link

answered 18 Nov '13, 22:57

sambuddha's gravatar image

2★sambuddha
312
accept rate: 0%

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

link

answered 19 Nov '13, 01:27

sambuddha's gravatar image

2★sambuddha
312
accept rate: 0%

what is wrong in my solution ??

link

answered 24 Nov '13, 10:19

r3gz3n's gravatar image

4★r3gz3n
52128
accept rate: 0%

Please tell, how is checkSquare() method implemented in author's solution? Which formulae is used to check whether a number is perfect square or not? Any link/information will be highly appreciated. Thanks

link

answered 23 Jun '14, 17:12

robinsobti's gravatar image

2★robinsobti
1
accept rate: 0%

here is simplest solution by RAJAT De

hi here is a simple code
#include <stdio.h>
 #include <string.h>
 #include<iostream>

 using namespace std;
 long long c(char *s){

 long long i,n=0;
    for(i=0;i<strlen(s);i++)
        n=10*n+s[i]-'0';
      return n;
    }

  int main()
 {

            int t;
           cin>>t;

      while(t--)
    {
      long long a[6000],i,m;
      char s[1001];
      cin>>s;
      m=c(s);

      a[0]=1;a[1]=1;

      for(i=2;i<6000;i++){
          a[i]=a[i-1]+a[i-2];
          if(a[i]==m){
             cout<<"YES"<<endl;
             break;
          }
         if(i==5999){
          cout<<"NO"<<endl;
        }
    }
   }
   return 0;
 }

HAPPY CODING can anyone explain how it does work with long string

link

answered 27 Jun '15, 17:18

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

hey,can anyone tell me the error in the code, i am using property 5nn + 4 or 5nn - 4 or both are perfect square to solve it .https://www.codechef.com/viewsolution/10523345..

link

answered 17 Jun '16, 16:52

nanhe's gravatar image

3★nanhe
413
accept rate: 0%

For those who are saying this question was biased towards JAVA, Well then I solved this problem in C++ in 5 minutes https://www.codechef.com/status/AMIFIB,lmao_ and make sure you save my template so that you can do the BIGINTEGER stuff in c++ using strings.

link

answered 07 Dec '18, 00:43

lmao_'s gravatar image

3★lmao_
562
accept rate: 14%

-1

@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 .

link

answered 19 Nov '13, 15:57

vineetpaliwal's gravatar image

6★vineetpaliwal
12.4k47107171
accept rate: 12%

I don't get it. You say that you were aware of tester's approach and you raised a concern but don't you think generating the test cases that would not allow tester's solution to pass, for this particular problem, was easy?

(19 Nov '13, 19:13) sid_gup4★

@sid_gup : Generating test cases for one particular modulo hash is easy , but nothing can be done in general as one may use any particular for modulus for hashing .

(19 Nov '13, 19:20) vineetpaliwal6★

Isn't it true that the tester's solution is showing 'YES' for all inputs greater than 10^64?

(19 Nov '13, 21:59) shreyans19955★
1

@vineetpaliwal: Indeed. I completely agree that nothing can be done in general. But at least the tester's solution could have been ensured for sanity if you had included such common hashes. And anyways, why let such problems be included for contests when you know about the possible discrepancies beforehand? Aren't such things checked by contest organizers/admins? Moreover, don't you think this problem was biased towards Python/Java programmers?

(20 Nov '13, 14:03) sid_gup4★
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,852
×3,820
×1,056
×344
×137
×69
×11

question asked: 18 Nov '13, 00:12

question was seen: 10,361 times

last updated: 07 Dec '18, 00:43