Need help in CSES — Two Sets II: Confusion in usage of mod

#	User	Rating
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

#	User	Contrib.
1	awoo	161
2	maomao90	160
3	adamant	156
4	maroonrk	153
5	-is-this-fft-	148
5	atcoder_official	148
5	SecondThread	148
8	Petr	147
9	nor	144
9	TheScrasse	144

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:

Accepted: not taking the overall mod on summation.
Wrong Answer: taking the overall mod on summation.

Wrong Answer Code

#define int long long
 
const int mod = 1e9 + 7;
 
int rec(int i, int j, vector<vector<int>> &dp){
    if (j == 0) return 1;
    if (i == 0) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    int take = 0;
    if (j - i >= 0) take = rec(i-1, j-i, dp);
    int notTake = rec(i-1, j, dp);
    return dp[i][j] = (take % mod + notTake % mod) % mod;
}
 
void solve(){
    int n; cin>>n;
    int sum = (n*(n+1)) / 2;
    if (sum % 2 != 0){
        cout<<0;
        return;
    }
    int target = sum / 2;
    vector<vector<int>> dp(n+1, vector<int> (target+1, -1));
    cout<<rec(n, target, dp) / 2;
}

Accepted Code

#define int long long
 
const int mod = 1e9 + 7;
 
int rec(int i, int j, vector<vector<int>> &dp){
    if (j == 0) return 1;
    if (i == 0) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    int take = 0;
    if (j - i >= 0) take = rec(i-1, j-i, dp);
    int notTake = rec(i-1, j, dp);
    return dp[i][j] = (take % mod + notTake % mod);
}
 
void solve(){
    int n; cin>>n;
    int sum = (n*(n+1)) / 2;
    if (sum % 2 != 0){
        cout<<0;
        return;
    }
    int target = sum / 2;
    vector<vector<int>> dp(n+1, vector<int> (target+1, -1));
    cout<<rec(n, target, dp) / 2;
}

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.)

Comments (6)

Write comment?

terracottalite

3 hours ago, # |

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;
}

Mod Int

→ Reply

yoco

50 minutes ago, # ^ |

"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.

eysbutno

43 minutes ago, # |

CSES submissions are private.

14 minutes ago, # ^ |

Oh thanks a lot for that, I'm sorry I didn't knew about that and have now put them in spoilers.

13 minutes ago, # |

another thing — you can't just divide a number under mod to get the correct answer. you should be multiplying by the modular inverse.

stop_terror_on_cf

6 minutes ago, # |

You can try writing the first one as

dp[i][j] = ((take % mod) + (notTake % mod) + mod) % mod;

yoco's blog