USACO Training "subset": Subset Sums

USACO Training "subset": Subset Sums

Problem Statement

Subset Sums
JRM For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.
For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:

• {3} and {1,2}

This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).
If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:

• {1,6,7} and {2,3,4,5}
• {2,5,7} and {1,3,4,6}
• {3,4,7} and {1,2,5,6}
• {1,2,4,7} and {3,5,6}

Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.
Your program must calculate the answer, not look it up from a table.

PROGRAM NAME: subset

INPUT FORMAT

The input file contains a single line with a single integer representing N, as above.

SAMPLE INPUT (file subset.in)

7

OUTPUT FORMAT

The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, ..., N}. The output file should contain 0 if there are no ways to make a same-sum partition.

SAMPLE OUTPUT (file subset.out)

4

Interpretation and Algorithms

We need to count the number of ways to partition a set {1,2,3,...,n} into two sets such that the sum of both sets are equal. Hmm... a O(n!) method to count each set... on second thought, let's not do that. This problem satisfies the DP property: each calculation is based on a calculation before it. So what are the DP variables? The only variable we are querying is how many way we can assemble an array such that the sum is j. The one variable that this is based upon is how many numbers we are permitted to use, or i. Therefore, our recurrence equation is P[j](ways to assemble) = P[j](ways to assemble with i) + P[j-i](ways to assemble without i). Our answer is P[N(N+1)/4]/2, since N(N+1)/2 is the sum of both arrays, so, N(N+1)/2 is the sum of one array. The /2 at the end is to correct for over-counting, some partitions can be counted twice (like {3},{1, 2} and {1,2},{3} would count as 2.)

Common Pitfalls

- Use long long instead of int, which will likely overflow.

The Code

/*

ID: qlstudi3

LANG: C++14

PROG: subset

*/

#include <cstdio>

using namespace std;

long long P[42]={0};

int main()

{

freopen("subset.in","r",stdin);

freopen("subset.out","w",stdout);

int n; scanf("%d",&n);

int k=n*(n+1);

if(k%4!=0)

{

printf("0\n");

return 0;

}

k/=4;

P[0]=1;

for(int i=1; i<=n; i++)

for(int j=k; j>=i; j--)

P[j]+=P[j-i];

printf("%d\n",P[k]/2);

}