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

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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 (11)

Write comment?

terracottalite

4 months 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

4 months 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.

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.

← Rev. 2 →

[DELETED]

eysbutno

CSES submissions are private.

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

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.

stop_terror_on_cf

You can try writing the first one as

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

convergent

Modulo

yoco's blog