"Two Sets II" dynamic programming problem

Question

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?

Please make your question self-contained. People should not have to click links to understand your question. — orlp
– orlp, Commented Nov 27, 2021 at 22:52

j_random_hacker · Accepted Answer · 2021-11-28 01:46:42Z

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.

(dp[n][maxSum] * 500000004) % 1000000007 would be a correct way to divide by 2.

Collectives™ on Stack Overflow

"Two Sets II" dynamic programming problem

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related