While going through some successful submissions of Am I Fibonacci Number in COOK40, I have seen that some of them just use unsigned long long to store digits of the form of 1000 digits and still getting correct answers.
Please tell me how this is getting correct and dont we need to use any bigint type class…
2 Likes
Unsigned long long can only store around 18 digits. There must be some other trick or weakness of testdata used that allows it.
2 Likes
the highest is unsigned long long int and it can take only upto 18 digits…
The accepted cases are done with some other tricks…they have stored the answer in an array or string or something…a typical example is “small factorials” in the practice section…
Even Tester solution does not seem to be working correctly for all cases and some of the solutions like http://www.codechef.com/viewsolution/2996264 which are accepted are not correct for all input, which means test cases were weak. You have to implement Big Integer class in c/c++ to handle large data.
yah i know that unsigned long long store only upto 10^18 digits…
but i actualy i am unable to get the trick…
like in the solution http://www.codechef.com/viewsolution/2995891 i am unable to find any trick bt still it is accepted??
yah i know that unsigned long long store only upto 10^18 digits… but i actualy i am unable to get the trick…
like in the solution http://www.codechef.com/viewsolution/2995891 i am unable to find any trick bt still it is accepted??
The reason that the tester has used unsigned long long is because once the number exceeds 10^18, it gets wrapped around so the number stored is basically fib % (max range of unsigned long long).The tester is assuming that each fibonacci number will have a unique value modulo max_LL. This can be said to be like some form of hashing where you are mapping fibonacci numbers to range if unsigned long long values. I am pretty sure this will give wrong answer for some values but might work for these test cases. This is the most probable logic of using unsigned long long.
3 Likes
@r3gz3n I think your method can be used to rule out certain numbers – if you take all the 1000-digit Fibonacci numbers and take their values mod m, and the 1000-digit number you’re testing has a value mod m not in that group, then you can rule it out. But you can’t rule numbers in.