"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[currentNumIncluded1][currentTargetSum];
int remainder = currentTargetSum  currentNumIncluded;
if (remainder >= 0) {
dp[currentNumIncluded][currentTargetSum] += dp[currentNumIncluded1][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[n1][maxSum]
instead of dp[n][maxSum]/2
everything works. Could anyone explain this to me?
1 answer

dp[n1][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 numbern
. 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
from2, 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 numbern
 and that every unordered bipartition corresponds to exactly two of these ordered bipartitions (the one in whichn
appears in the first part, and the one in whichn
appears in the second part, obtained by swapping parts). So if we count only the "ordered bipartitions" in which the second part containsn
, 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 is500000004
. That means that, before dividing by 2, you must havedp[n][maxSum] = 1000000008
 but the modulo computation in your code would reduce that back to1
, leaving the incorrect final resultdp[n][maxSum]/2 = 1/2 = 0
.
do you know?
how many words do you know