Any hints for this problem will be appreciated.
Subset Sums
hint: meet in the middle
2 groups :)
Some more hints ? :)
more hints = solution.
if you want..
if you want..
OK I want it please ..
Divide element in two groups, with sizes N/2.
build array A consisting of every possible sum you can get by choosing subset of first group.
now do it for second group too, and think how we can merge these two arrays.
you can sort one array, and then do a binary search on it for every element from second array.
binary search can be avoided..but it passes tests even with it.
build array A consisting of every possible sum you can get by choosing subset of first group.
now do it for second group too, and think how we can merge these two arrays.
you can sort one array, and then do a binary search on it for every element from second array.
binary search can be avoided..but it passes tests even with it.
What for is binary search? Do I need to match sums?
yes, you need to match sums..
if second array is sorted and
if sum1 is one sum from first array, and sum2 and sum3 are sums from second array, and sum2 is before sum3 in sorted array, and sum1+sum3 is less than some bound, then sum1+sum2 is less than that bound too.
if second array is sorted and
if sum1 is one sum from first array, and sum2 and sum3 are sums from second array, and sum2 is before sum3 in sorted array, and sum1+sum3 is less than some bound, then sum1+sum2 is less than that bound too.
Alright I got it! thanks!
Still getting 9 wrong results :(
how to avoid binary search?
why to avoid ?
there are several possibilities...
here are two I can think of right now...
instead of binary search you can use some data structure like segment tree or kumulative table...
or you can sort both groups and then do linear...
you can do this by holding two pointers in second group, and when you go to the next one number in first group those two pointers can be changed just in one direction... which leads to linear after sorting... :D
there are several possibilities...
here are two I can think of right now...
instead of binary search you can use some data structure like segment tree or kumulative table...
or you can sort both groups and then do linear...
you can do this by holding two pointers in second group, and when you go to the next one number in first group those two pointers can be changed just in one direction... which leads to linear after sorting... :D
well ok i was also thinking about BIT or another sorting but still u cant avoid that extra time.thanks:D
Well sorting can be done faster, by using radix sort....