admin please answer!!!
@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.
1 Like
@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 .
3 Likes
@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.
Can you explain how the tester is storing 1000 digit numbers into a set of unsigned long long !
3 Likes
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âŚ
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++âŚ
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.
1 Like
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âŚ
@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 .
4 Likes
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âŚ
5 Likes
@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 [email protected] to get the âtesterâsâ solution replaced . I had already raised this issue during the problem setting process .
2 Likes
@nipun_poddar : There is no issue with test cases . There is definitely an issue with âtesterâsâ solution .
Fast doubling method ! Thanks for a new concept 
@vineetpaliwal, thanks for your reply and cofirmation
I will definitely e-mail codechef admins regarding this matter as soon as possible for me 
By the way, the problem was interesting and your idea for solving it was also very good
Best,
Bruno
1 Like
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
1 Like
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?
@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 .
Isnât it true that the testerâs solution is showing âYESâ for all inputs greater than 10^64?