"Two Sets II" dynamic programming problem

I'm trying to solve https://cses.fi/problemset/result/3172518/#test11.

It states:

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}

This is what I got to now:

int n;
cin >> n;
int maxSum = n * (n + 1) / 2;
if (maxSum % 2 != 0) {
    cout << 0 << endl;
    return 0;
}
maxSum /= 2;
vector<vector<long>> dp(n+1, vector<long>(maxSum+1));
dp[0][0] = 1;
for (int currentNumIncluded = 1; currentNumIncluded <= n; ++currentNumIncluded) {
    for (int currentTargetSum = 0; currentTargetSum <= maxSum; ++currentTargetSum) {
        dp[currentNumIncluded][currentTargetSum] = dp[currentNumIncluded-1][currentTargetSum];
        int remainder = currentTargetSum - currentNumIncluded;
        if (remainder >= 0) {
            dp[currentNumIncluded][currentTargetSum] += dp[currentNumIncluded-1][remainder];
            dp[currentNumIncluded][currentTargetSum] %= 1000000007;
        }
    }
}
cout << dp[n][maxSum]/2 << endl;

I use simple DP to solve it. However, it doesn't pass 5 out of 26 test cases. I looked it up and it turns out that if you print dp[n-1][maxSum] instead of dp[n][maxSum]/2 everything works. Could anyone explain this to me?

1 answer

  • answered 2021-11-28 01:46 j_random_hacker

    dp[n-1][maxSum] is valid because it counts the number of ways of making half the original target sum using a subset of numbers that excludes the final number n. Why does this work?

    It's often easier to count "more ordered" versions of the things we want to count. Here, it's easy enough to count ordered bipartitions (that is, bipartitions in which we distinguish, say, 1, 4 | 2, 3 from 2, 3 | 1, 4), but for our purposes this would count them twice -- we want to count unordered ones. One way to do this is to continue counting the "more ordered version" as before, but impose constraints on which objects will be counted. Observe that, because all numbers are distinct, exactly one of the two parts in any "ordered bipartition" will contain the highest number n -- and that every unordered bipartition corresponds to exactly two of these ordered bipartitions (the one in which n appears in the first part, and the one in which n appears in the second part, obtained by swapping parts). So if we count only the "ordered bipartitions" in which the second part contains n, we count the number of unordered bipartitions. (This reasoning would work for any particular input element; n is just convenient.)

    dp[n][maxSum]/2 would work if you were using unbounded integers, instead of modulo arithmetic. It doesn't work here (all the time) because division does not respect the modulo arithmetic. Suppose the correct answer is 500000004. That means that, before dividing by 2, you must have dp[n][maxSum] = 1000000008 -- but the modulo computation in your code would reduce that back to 1, leaving the incorrect final result dp[n][maxSum]/2 = 1/2 = 0.

How many English words
do you know?
Test your English vocabulary size, and measure
how many words do you know
Online Test
Powered by Examplum