USACO: subsets (ineffective)

Question

I am trying to resolve subsets from the USACO training gateway ...

Problem Statement

For many sets of consecutive integers from 1 to N (1 <= N <= 39), this set can be divided into two sets whose sums are identical.

For example, if N = 3, you can partition the set {1, 2, 3} so that the sums of both subsets are the same:

{3} and {1,2} This is considered the only division (that is, it cancels the number of orders as the same split and, therefore, does not increase the number of splits).

If N = 7, there are four ways to split the set {1, 2, 3, ... 7} so that each section has the same amount:

{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 in which a set containing integers from 1 to N can be divided into two sets whose sums are identical . Print 0 if no such paths exist.

Your program should calculate the answer, and not look for it from the table.

End

Before I worked on O (N * 2 ^ N), simply rearranging through the set and finding the sums.

Finding out how terribly inefficient I went on to display the sequences of sums ... http://en.wikipedia.org/wiki/Composition_(number_theory )

After many coding problems, to clear the repetitions is still too slow, so I went back to the square: (.

Now, when I look at the problem more closely, it seems that I should try to find a way not to find the sums, but actually go directly to the number of sums using some kind of formula.

If anyone can give me directions on how to solve this problem, I am all ears. I am programming in java, C ++ and python.

Answer 1

In fact, there is a better and simpler solution. You should use Dynamic Programming instead. In your code, you will have an array of integers (whose size is the sum), where each value in the index i represents the number of ways the numbers can be split, so one of the sections has the sum i. Here is what your C ++ code would look like:

int values[N]; int dp[sum+1]; //sum is the sum of the consecutive integers int solve(){ if(sum%2==1) return 0; dp[0]=1; for(int i=0; i<N; i++){ int val = values[i]; //values contains the consecutive integers for(int j=sum-val; j>=0; j--){ dp[j+val]+=dp[j]; } } return dp[sum/2]/2; } 

This gives you an O (N ^ 3) solution that is fast enough for this problem.

I have not tested this code, so a syntax error or something else may occur, but you get the point. Let me know if you have more questions.

Answer 2

This is the same as finding the coefficient term x ^ 0 in the polynomial (x ^ 1 + 1 / x) (x ^ 2 + 1 / x ^ 2) ... (x ^ n + 1 / x ^ n), which should take the upper bound O (n ^ 3).