I think there is an overflow at boundary condition.
case ex.
40 0
1 1000000
1 1000000
upto 40 times.
calculation will reach beyond the scope of greatest of data types like long long. should I assume there is is no such case in the judge while testing the code??

i’m pretty sure there is an overflow if you look for all subset in the case I mentioned

I wonder how people are going past this???

There is no such thing as overflow… Only “overflow”, i.e., if you think that the answer will exceed the capacity of the largest possible data type (which is not even long long btw), then there are three possibilities:

  1. You must be given a mod value so the answer gets small enough to fit on a native type;

  2. You must use big number arithmetic;

  3. Your logic is wrong or you haven’t completely understood the problem;

Either way, good luck,


1 Like

Will not overflow with 64 bits unsigned int.

@kuruma I know this is possible. But in this question n<=38 should have been there. I overlooked my doubt and submitted it and got ac. So I can assume that case is not there in the test files although it is very well possible according to the given constraints.
I came with this doubt because I generally look for the corner cases after coding and this was the corner most case that seemed possible and my code failed for that and after performing some checks I saw that my calculation was overflowing although my code was doing good for cases below n<=38.

this is a small thing but took lot of my time. In my code there was a small glitch and instead of finding that I took this to be the reason of my 3-4 wa submissions although it was true. :frowning:

@nikhilg Yes it will overflow for that too. calculation reaches a point where a variable will have to store a value of like 20*(10^18).
unsigned 64 bit int has range upto only 18*(10^18).True answer for my case is 20000000 but you will get some random answer for that. wait for the competition to end and then you test and verify. :slight_smile: