0
$\begingroup$

Your task is to count the number of ways numbers $1,2,…,n$ can be divided into two sets of equal sum. For example, if n=$7$, there are four solutions: ${1,3,4,6}$ and ${2,5,7}$, ${1,2,5,6}$ and ${3,4,7}$, ${1,2,4,7}$ and ${3,5,6}$, ${1,6,7}$ and ${2,3,4,5}$ Input The only input line contains an integer n. Output Print the answer modulo $1e9+7$. $1$$n$$500$

Source: cses

My approach: It's a pretty straightforward DP problem, where we follow a loop from $1$ to $n$ and for each such i in $1$ to $n$, we fill the sum DP.

    int s=sum/2;
    vector<int>dp(s+1);
    dp[0]=1;
    for(int i=1;i<=n;++i){
        for(int k=s;k>=0;--k){
            if(k-i>=0){
                dp[k] = (dp[k] + dp[k-i])%mod;
            }
        }
    }
    int ans=dp[s]/2;

My question is, if I change here the loop from $1$ to $n-1$ and then output $dp[s]$, then the answer is correct, however if I loop from $1$ to $n$, then output $dp[s]/2$, it is incorrect. I think both should be correct since in the second method, I am counting all the possibly ways of making sum=$n*(n+1)/4$ and then simply dividing by $2$ since we take only $1$ out of the $2$ sets.

$\endgroup$

1 Answer 1

1
$\begingroup$

I have figured this out after experimenting some time with the code. The issue was that we cannot divide $dp[sum]/2$ since we need modulo inverse to calculate the quotient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.