supersonglj
BAN USERcan only give out O(n^3) soln
want to know any improments...
dp: dp[i][j] means the # of ways of chossing i integers from the first j elements and the last element being j
boundary: for i=1 to n do dp[1][i]=1
dp[i][j]=sigma(k=1 to j-2)(dp[i-1][k])
the final ans is: sigma(i=1 to n)(dp[k][i])
@lol
it can be done in O(n), i will state it more clearly
what i mean to mark them is using an additional int array, its size is n, the array looks like:
[...1...2...3....3...2...1...]
each pair is a solution to sum n1, denote the number of solutions to be num1
then do the same thing in dealing with sum n2, denote the number of solutions to be num2
without loss of generality, suppose num1>=num2>0(if any is zero, no soln)
the confliction only occurs when:
case 1: num1=num2=1, and they share atleast one of the same number;
eg.
[1....1]
[1.1...]
case 2: num1=2,num2=1, for the only pair which sums to n2, one of the number share with the first pair in n1 and the other share with the second pair in n1.
eg.
[1..2...2..1]
[1......1...]
for all the other cases, it can be ensure that there is a solution which doesn't have a duplicate.
i am afraid it is wrong
consider this case:
[1 2 4 8 16 32 64] and needed sum is 43
according to your soln, p3 will point to 32,16,8,4, then you decrement p4
you will lose an answer which is 1,2,8,32
for this problem, currently i cannot think of any proper strategy about moving which pointer at each step.
just give out my solution which is other than O(n^3), it is O(n*sum), so whether it is better or worse depends on sum...
sort(a,a+n);
for (int i=2;i<=sum/2;i++) {
n1=i;n2=sum-i;
// check whether there are two items in array which sums to n1, mark all of them O(n)
// check whether there are two items in array which sums to n2, and not conflict with above mark O(n)
}
an alternative way to solve this problem is using dp method, something like knapsack problem. the time complexity is also O(n*sum)
- supersonglj August 26, 2011i doubt if it is actually O(n^2)
- supersonglj August 26, 2011*if currSum > reqSum
do you mean to decrement the 3rd until it becomes adjacent to p2?
what's your strategy about moving 3rd or 4th?
For your first question, the actual size of f[][] is (n/2+1)*(sum/2+1). And in IF sentence, I restricted "k+a[i]<=sum/2", so it won't exceed. This is also why in my for loop for j, the maximum value is min(i,n/2)-1, this ensures j+1 will smaller than or equal to n/2.
As I stated before, f[i][j] in my method means choosing exactly i elements, the sum can be j or not. And our final target is to see if f[n/2][sum/2] is true, or find the maximum k(<=sum/2) that f[n/2][k] is true. So for f[i][j] where i>n/2 or j>sum/2, it doesn't need to calculate.
In addition, my for loops for j and k are backwards(from max value to 0), this ensures no input will be counted twice. If these for loops are forwards, then that means all the input will be counted arbitrary many times.
I'm not sure if I explained clearly. @_@
Yes, the size of f[][] is n/2*sum/2.
what do you mean by "recurrence (in sentence)"?
you cannot ensure the sizes for two sets be the same
try this data:
4
1 2 3 6
your code will return diff=0, but this is based on {1,2,3} and {6}
in your code, memo[i][j] means using up to i numbers, the sum can be j, but in my method, f[i][j] means choosing exactly i numbers.
the difference is here
obviously, cannot ensure that set1.size() equals to set2.size()
e.g.
1 2 3 6
this problem can be solved using a DP method, something like a knapsack problem.
let n be the number of elements, a[1..n] be the list
let sum be the sum of all n elements
denote bool f[i][j] means choose i numbers, whether the sum can be j or not.
initially, all f are false except f[0][0]=true
for (i=1;i<=n;i++) {
for (j=min(i,n/2)-1;j>=0;j--) {
for (k=sum/2;k>=0;k--) if (f[j][k] && k+a[i]<=sum/2) f[j+1][k+a[i]]=true;
}
}
for (i=sum/2;;i--) if (f[n/2][i]) {
// found the minimal diff
// the diff is sum/2-i;
break;
}
if the detailed numbers in each set is needed, just record it in another array when doing DP
- supersonglj August 17, 2011i think you are wrong.
in your method, every neighbouring pair(1st and 2nd, 3rd and 4th, ...) will be put into different set. consider this case:
1 2 3 4 5 9
the answer should be {1,2,9} vs {3,4,5}
according to your method, the final result will be {1,4,5} vs {2,3,9}
meanwhile, i think this question is a little bit difficult for "SDE in tests", for SDE is a good question
- supersonglj August 16, 2011
- supersonglj August 30, 2011