[algogeeks] Re: partitioning the array
@gaurav both things are same, matrix is a simple and efficient way to do problem like this. . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: partitioning the array
yes we would use 2 dimensional array to store the values inbetween but the main question here is that is the reccurence realation correct?? On Mon, May 9, 2011 at 11:31 AM, anshu anshumishra6...@gmail.com wrote: @gaurav both things are same, matrix is a simple and efficient way to do problem like this. . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Gaurav Aggarwal SCJP -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: partitioning the array
@gaurav
f(i, j) = {(total number we need to make sum j including ith number in
array), if its not possible than -1};
f(i, j) = f(i-1, j-ar[i]) + 1 -- if (i-1, j-ar[i]) != -1;
answer will be the largest j for which f(i, j) will be exactly equals to
n/2;
there is something more in this but when you start to write the code you can
easily get that.
https://www.spoj.pl/problems/AMR10D/ a little bit similar problem on spoj.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: partitioning the array
1.Add 0 to the array if the number of elements in the given array is odd. 2.Count the frequency of each element or we can simply sort it. 3.If the frequency is even for any element then that element can be distributed among two parts equally(say p1 and p2). 4.For the elements having odd frequency(f) NOT=1, we can still distribute them by (f-1)/2 each into p1 and p2 leaving with only one instance of each odd frequency elements.(say in set S) 5.Now we are left with to divide the elements of the set S into p1 and p2(equal number of elements in each part) such that the difference of sum of p1 and p2 is minimum. 6.say the sum of the elements of the set S is X and the number of elements is N. So,we need to check if we can have N/2 elements in S such that their sum equals to X/2(if X is even;else (X-1)/2). And if it is not equal then try for the closest value. 7.If we are able to find such a combination then the difference will be 0(if X is even) or 1(if it is odd). if not then the minimum difference will be X-(2*sum of the N/2 elements(as close as possible to X/2)). thanks, Anitesh. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: partitioning the array
Use KnapSack DP. suppose the sum of element = s and number of elements = n make a 2-dimesnsional array of size n * ((s+1)/2); I think that much hint is enough. if we think little bit more we can optimize it also. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: partitioning the array
@anshu then shall we use the foll reccurence realation?? 1i=n S=(s+1)/2 f(i,S)= min( f(i-1, S), f(i-1, S- ar[i]) ) On Mon, May 9, 2011 at 10:42 AM, anshu anshumishra6...@gmail.com wrote: Use KnapSack DP. suppose the sum of element = s and number of elements = n make a 2-dimesnsional array of size n * ((s+1)/2); I think that much hint is enough. if we think little bit more we can optimize it also. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Gaurav Aggarwal SCJP -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: partitioning the array
simple.. sum all the n elements.. a= floor(sum/2) b=sum-a output is a b -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: partitioning the array
@cegprakash: it doesnt ensure that both the arrays will be having same number of elements On Sat, May 7, 2011 at 10:10 PM, cegprakash cegprak...@gmail.com wrote: simple.. sum all the n elements.. a= floor(sum/2) b=sum-a output is a b -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: partitioning the array
sorry, i misunderstood the problem statement On Sun, May 8, 2011 at 10:53 AM, Aakash Johari aakashj@gmail.comwrote: @cegprakash: it doesnt ensure that both the arrays will be having same number of elements On Sat, May 7, 2011 at 10:10 PM, cegprakash cegprak...@gmail.com wrote: simple.. sum all the n elements.. a= floor(sum/2) b=sum-a output is a b -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
