### yoco's blog

By yoco, history, 13 days ago,

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.

$\text{ans} = ( \sum_{i=1}^{n} (a[i] \% \text{mod})) \% \text{mod}$

But here are my two submitted codes:

1. Accepted: not taking the overall mod on summation.
2. Wrong Answer: taking the overall mod on summation.
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.)

• +6

 » 12 days ago, # |   0 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). Auxillary#define MOD 23 long long add(long long a, long long b) { return ((a + b)%MOD + MOD)%MOD; } long long mul(long long a, long long b) { return ((a * b)%MOD + MOD)%MOD; } 
•  » » 12 days ago, # ^ |   0 "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.
•  » » » 12 days ago, # ^ |   0 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.
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   0 [DELETED]
 » 12 days ago, # |   +3 CSES submissions are private.
•  » » 12 days ago, # ^ |   0 Oh thanks a lot for that, I'm sorry I didn't knew about that and have now put them in spoilers.
 » 12 days ago, # |   +6 another thing — you can't just divide a number under mod to get the correct answer. you should be multiplying by the modular inverse.
•  » » 12 days ago, # ^ |   0 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.
•  » » » 11 days ago, # ^ |   0 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.
 » 12 days ago, # |   0 You can try writing the first one as dp[i][j] = ((take % mod) + (notTake % mod) + mod) % mod; 
 » 11 days ago, # |   0 Modulo