I was practicing DP through CSES when I got to the Two Sets II problem, wherein I got the confusion on the usage of mod to get the correct answer.
I had read earlier that if we wish to take mod of a summation, we have to take mod of individual elements of the series and then take the mod of summation.
But here are my two submitted codes:
- Accepted: not taking the overall mod on summation.
- Wrong Answer: taking the overall mod on summation.
Wrong Answer Code
Accepted Code
Due to this, I got confused about how we should be taking the mod and, in general, how you tackle such situations. (Right now, I'm looking for a discussion like the one from which I got to know of the binary search method of while (r-l > 1), which I now use, so I can only stress more on the concept of the problem.)
Whenever the sum can be bigger than the mod you must take a mod, which is almost always. For example if you add two numbers the max of each of them is MOD-1 so the sum can be 2*MOD-2. In CP, you don't need to decide on where to add mod though just put it after every operation. Some people use auxillary functions or even mod int templates.
PS: If the thing you are taking mod of can be negative you must make it positive because in C++ mod works in a way different than math (see Auxillary for example).
https://github.com/atcoder/ac-library/blob/master/atcoder/modint.hpp
"if you add two numbers the max of each of them is MOD-1 so the sum can be 2*MOD-2"
"Whenever the sum can be bigger than the mod you must take a mod, which is almost always."
Yes, but then that gave me the wrong answer while taking up the mod on the sum and rather got accepted when I removed the mod on the sum. My major confusion is why taking mod on sum caused us harm. It is not getting a negative value anywhere in between so we won't have conflict in there.
Actually the problem in your case is not with taking overall mod. In fact, I am not sure if it can be hacked but it looks like it is a coincidence that it passed. It is not possible to divide numbers in mod, it is required to use a "modular inverse" to do that. https://cses.fi/paste/e0c08c1dc65da1609789a7/
I wonder if someone can prove or disprove that dividing by 2 in that case works.
[DELETED]
CSES submissions are private.
another thing — you can't just divide a number under mod to get the correct answer. you should be multiplying by the modular inverse.
so can it be hacked? My code, which got accepted.
and did you mean that it has to be (num * inv) % mod? I didn't understood that part.
I couldn't prove why it works but when I tried n from 1 to 500 I couldn't find a hack, so you are safe.
Modulo