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…
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 .
Hope this will help you to some extent
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.
This solution is not perfect, and will definitely have corner cases. A lot of them, in fact.
Please go through the speculation made by the users.
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
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 …
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 
Further reading on collisions=> http://codeforces.com/blog/entry/4898
Also One should use unsigned long long in c language to take the benefits of overflow.
2 Likes
for more information look at this …
http://threads-iiith.quora.com/String-Hashing-for-competitive-programming
a good tutorial by a great programmer .
So you mean to say dealing with 1000 or so character string and converting is called hashing ??
Not Exactly , Hashing/Mapping is something which let you to map the larger domain to a smaller domain possibly without colloision .
Thanks a lot…i will certainly refer to your links
A better example : Suppose you want to check whether a string is palindrome or not . you can prepare one hash from left to right another from right to left taking modulo with some big number say 10^18 . if they are equal you can say that yes it is palindrome (again there is always a possibility of some collision but it is extremely low depending upon the mod or base ).
1 Like