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

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

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

Комментарии (11)

Написать комментарий?

terracottalite

4 месяца назад, # |

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

→ Ответить

yoco

4 месяца назад, # ^ |

"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