Help with Two Sets II from CSES

Link to the problem: https://cses.fi/problemset/task/1093

Code:

#include <bits/stdc++.h>
using namespace std;
 
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
 
const int MOD = 1e9 + 7;
const ll INF = (1LL<<62);
const int MAXN = 2e5+5;
 
int main()
{
    FASTIO
    int n;
    cin >> n;
    ll dp[MAXN];
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    int sum = (n*(n+1))/2;
    if(!(sum&1))
    {
        sum /= 2;
        for(int i=1; i<=n; i++)
        {
            for(int j=sum; j>=0; j--)
            {
                if(i+j <= sum)
                {
                    dp[i+j] += dp[j];
                    dp[i+j] %= MOD;
                }
            }
        }
        cout << dp[sum]/2 << "\n";
    }
    else
        cout << "0\n";
    return 0;
}

The above code fails on 5 out of 25 test cases. For example,

For n = 112
Correct output: 979144036
My output: 479144032

Can anyone please point out the error in the above code?

@everule1 Please Help.

dp[sum]/2

Print the answer modulo 10^9+7

Also Your code is much too complex.

Simpler code
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
const int p = 1e9 + 7;
void solve(){
    int n;
    cin>>n;
    int sum = n*(n+1)/2;
    if(sum&1){
        cout<<"0\n";
        return;
    }
    sum/=2;
    vector<int> dp(sum+1);
    dp[0] = (p+1)/2; //(1/2) in mod p
    for(int i=1;i<=n;i++){
        for(int j=sum;j>=i;--j){
            dp[j]+=dp[j-i];
            dp[j] >= p ? dp[j]-=p : 0;
        }
    } 
    cout<<dp[sum]<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
1 Like

You should divide the ans by the multiplicative inverse of 2 under modulo 1e9 + 7 (because you have to give answer under modulo so you can’t simply divide it by 2 as it is not under the modular divison)

1 Like

@everule1 What is (1/2) in mod p? And why do you set dp[j] as 0 if it is less than p, shouldn’t it be left as it is?

1 Like

Oh also the other part, it’s not set to 0 is it’s less than p, it’s left as is.
It opens up to

if(dp[j]>=p){
    dp[j]-=p;
}
else{
    0;
}
1 Like