You are not logged in. Please login at www.codechef.com to post your questions!

×

Equal sum partition

Equal partition: Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (Hint: complexity O(2n/2))

How do I solve this problem using meet in the middle? I found it on this blog.

asked 04 Jul '17, 12:43

manjrekarom29's gravatar image

1★manjrekarom29
2113
accept rate: 0%


This problem requires you to divide and conquer. The set of 40 real numbers must be broken to two smaller sets of 20, and merged efficiently.
One clever algorithm to do this is Meet in the Middle. A hint for this is you are looking for an aggregate function on the two sets (sum), hence MitM is a possibility.

Here is a video editorial I made on Meet in the Middle!

Cheers!

link

answered 26 Sep '17, 11:19

gkcs's gravatar image

4★gkcs
2.6k11127
accept rate: 9%

don't you understand this explanation?

We already know that the 2 subsets we are looking for have the same sum which is equal to the sum of all the elements in the set / 2, so we only need to find the elements of 1 of the 2 subsets. A neat solution would be splitting the set into 2 random disjoint subsets of size N / 2, namely A and B. Then we insert each sum of every combination of elements from A into a hash table. We then check the sums of every combination of elements from B i. e. for a sum K, if S / 2 - K is in the hash, then we have a solution. Final complexity: O(2 ^ (N / 2 + 1)). An alternative to this solution would be a well implemented algorithm which randomly moves elements from one subset to the other. This outperforms the 2 ^ (N / 2) algorithm on memory and may even have better results on time.

link

answered 04 Jul '17, 12:53

hruday968's gravatar image

4★hruday968
1.7k210
accept rate: 14%

I went through it before but I couldn't understand. Though I get it now.

(04 Jul '17, 14:09) manjrekarom291★

For anyone else trying to understand it, we are trying to reduce the problem to find a single set of elements whose sum is equal to S/2 where S is sum of all elements in the array.

  1. So we divide set of size N(=40) into two halves(=2*20) A and B.
  2. Find all possible sums for A array(T = 2^20) and store it in a hash-table.
  3. Generate sum of elements from array B and at every step check for a sum K in B array, is there a sum = S/2 - K in the hash-table.
  4. If it's there you have your solution. So the first subset will be a collection of all the elements from array A forming sum = S/2 - K and elements from array B (forming sum=K) such that the sum is now S/2 of the complete subset and the second subset has all other elements not included in the first subset.
link

answered 04 Jul '17, 14:51

manjrekarom29's gravatar image

1★manjrekarom29
2113
accept rate: 0%

Would this algorithm run efficiently for large inputs (10^10)?

link

answered 12 Jan, 14:49

arul_verman's gravatar image

1★arul_verman
212
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×294
×62

question asked: 04 Jul '17, 12:43

question was seen: 4,569 times

last updated: 12 Jan, 14:49