Записи в блоге

№	Пользователь	Рейтинг
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

№	Пользователь	Вклад
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.)

Полный текст и комментарии »

Блог пользователя yoco