hello everyone…i am having this doubt for months.please try to understand what i want to ask.see i was trying this problem.but i failed to solve this because it involve number of digits=1000.then i found this guy’s
solution(@rajat1603) his solution link .after seeing his solution listen to my doubt please.
see he is reading 1000 digit number and then converting into integer in his function long long c(char *s). How he was able to return 1000 digit number just by long long and how number of 1000 digit get stored in just long long(it is still 1000 digit number).please please respond,this might be stupid question but i have many question pending just because of this…

@doodle90

Yes you are right . I am also amazed to see his code but if we take it logically what is he doing (taking mod with a large number which is kept hidden from you as well as from me) . I mean that when overflow occur (it is nothing but taking mod with the limit of long long) and the same is happening when he is calculating fibonacci number (modulo operation is very well defined on addition) . Instead of compararing the exact number he is comparing of modulo of two result which should be same . Contrary to that i am not saying that his solution is correct as there are chances of collision .

Regards Ma5termind

2 Likes

At first glance, I was amazed at what was happening here. There is no way a long long can store something >10^19. Moreover, it seemed absurd that we were calculating even the 5999th fibonacci number and storing the result in a long long variable.
It turns out that your doubt has already been asked in the comments section of the editorial. In fact the tester has allowed the overflow, and is using it for something which is called a “hash”. long long’s upper limit is just acting as a modulus operation.

http://discuss.codechef.com/questions/29654/amifib-editorial

This solution is not perfect, and will definitely have corner cases. A lot of them, in fact.

1 Like

Thanks a lot…i still wonder how taking mod makes the same sense as whole 1000 digit number.please make this some more clear…Not just in this question but every question having digits like 1000 or similar i have seen people taking mod at each step.i always wonder why is this so…please make this clear thanks alot

As stated by ma5termind:Clearly, Solution is taking benefits of weak test cases( ) of codechef.

But I am too lazy to find out those cases

Also One should use unsigned long long in c language to take the benefits of overflow.

2 Likes

Or you can teach me how to deal with these question having 1000 digits and how to convert and save them

think of this as rolling hash … for ex :

http://www.codechef.com/viewsolution/4708311

You will love to see that such techniques are very very useful infact it can be used to find the longest common substrings between two given string in O(Nlog^2(N)) time where N is the length of the string …