Possible overflow in solution

help
, , , ,
1

With respect to the problem RECNDNUM, these are the links to my solution in:
Python 3 and in C++.
The logic and equations used in both are the same, but the solution written in C++ gives a WA, possibly because of an overflow during multiplication.
I am unable to figure out which statement(s) is(are) causing the overflow.
In the links given above, you can also find a sample test case(similar for both) for which I get different answers using the two solutions.

  • Please help me figure out if the issue is an overflow or something else.

  • On several occasions a logic implemented in C++ gives a WA while the same implemented in python gives AC. So, when using C/C++, what practices are common or how should one deal with multiplication of numbers when N ≤ 10^9, to avoid potential overflow related issues.

Any other suggestions are most welcome.

2

I also did the same mistake.
Remember in CPP the modulo operator gives wrong modulo value for negative values which is not the problem with python, so just add “mod” to the final ans and take the mod again and it will not be negative.
CPP: -9 % 10 = -9
PYTHON: -9%10 = 1

3

But in case of this question, the final answer is never going to be negative.
And the possibility that an overflow causes the answer to be negative is ruled out by the fact that all the variables are declared as unsigned long long integers.
I have noted your suggestion.
If possible, please look for the problem in this particular case.

4

Line 29 : s = (wf*(wf+1ull))%mod this when taken the modulo can become small and then when you again subtract “- wf” then it becomes negative.

1 Like
5

This is not an overflow error.
In your solution I have changed all the ull to ll (usual meaning) and added a check for negative value and it got AC.
https://www.codechef.com/viewsolution/32390693
Hope that helps. :slightly_smiling_face:

6

I wouldn’t have realized this.
Thanks a lot man!

7

I wouldn’t have realized it either thanks to @everule1.

8

If it’s any better, This is me searching for the same mistake for 1 hour 15 minutes here. my solve function was returning a negative value in 2 test cases. I don’t think I’ll ever forget about this now.

1 Like
9

That was definitely some good amount of effort and for sure is unforgettable :sweat_smile:.