testers solution says 10256117644121029666 is a fibonacci no. but it isnt!
1 Like
ya definately there is something wrong with test cases !!
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.
No, his solution is wrong. It says 10256117644121029666 is a fibonacci no., but it is not.
Your code link: WMDHVe - Online Python Interpreter & Debugging Tool - Ideone.com
Tester code link: GLjOzF - Online C++0x Compiler & Debugging Tool - Ideone.com
1 Like
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.
Tester’s solution also gives wrong answer for 10256117644121029666 which is not a fibonacci number.
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
@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
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
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
@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 
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?
@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?
1 Like