I’m following an approach similar to that in the editorial still I get the verdict as WA, might be some bug in the code, will someone please help me with this.
Well, i don’t know much about c++
So your code appears like greek to me. But anyway, i have explained my approach using difference array.
Following link to my explanation
Above link contain the link to my code (java).
Feel free to ask anything
You are suffering from overflow.
I generated a test case of format
Input 1 5 5000 1 1 5 1 1 2 1 1 3 2 1 4 2 1 5 . . . 2 1 5000 Your Output 947572220 947572220 -34951858 -17475929 -17475929
The negative numbers arent expected as modulo means we are expecting a positive number.
It worked after I changed the operation ( a - b) % mod -> ( a + (mod - b) ) % mod
Wanna know the reason how this works…??
Well, the number (a-b) must be less than 0, which causes the solution to fail…
Changing that to (a + (mod-b))%mod ensures that value never goes negative…
Another alternative would have been, to add a line after
x = (a-b)%mod
Please UPVOTE and Accept if you find this helpful…
I’m taking the mod each time I perform an arithmetic operation, am I missing something here? thanks.
vijju, how do you generate numbers?
I cant say what you are missing dear. You need to see it on your own, but you are failing on large numbers.
@kunnu120 - We write a program to generate test cases. Lot of work O_O
OMG KUNNU HOW DID YOU MAKE THAT?!! I want to know it for…purposes :3
copy paste lol, but you can make it with your keyboard too like
It worked after changing ( x - y) % mod to ( x + ( mod -y) ) %mod
You were not paying attention to fact that “modulo” in problem statement means the modulo which is “always positive”