This solution >>> https://www.codechef.com/viewsolution/4569721
As the number in the input is of 1000 digits how this solution got AC ?
Even long long won’t be able to hold such a large value so how this solution got accepted ??
lol,seems like test cases are pretty weak.
That’s what I’m wondering. How can a number of 1000 digits fit in long long.
Its mentioned by the problem setter @vineetpaliwal in the comments of the editorial that such solutions (including the Tester’s solution) are storing the fibonacci number in the 64-bit int data type and letting the overflow occur. After overflow what remains is the value of that number mod 2^64. It then check if any fibonacci number gives the same value mod 2^64 or not. This is similar to hashing technique.
This method assumes that no 2 fibonacci numbers within the given range give the same value mod 2^64 i.e. no collisions.
This method is not correct but passes because the test cases might be weak.
1 Like
Read the interesting “comments” int the editorial page. Wondering how the solvers got away with it.
Oh, Now I got it thanks a lot but isn’t it wrong to let such an incorrect solution to get AC. And I was reading the editorial too and there are many cases at which this solution gives wrong answer.
lol,I found the editorial too. The comments are really interesting.
@c_utkarsh I think you mean to say that the method assumes no hash collision occurs between a Fibonacci and a non-Fibonacci number, rather than 2 Fibonacci numbers.
Also the numbers are being stored modulo 264, and not 264-1.
1 Like
Exactly. And about the mod, the tester’s solution uses unsigned long long whose limit is 2^64 - 1 and thus the numbers are being stored mod 2^64. Thanks for correcting. Updated now.