PROBLEM LINK:Author: Anudeep Nekkanti DIFFICULTY:Easy PREREQUISITES:greedy, heaps (or STL multiset) PROBLEM:You have an unknown set of length N. We take all 2 ^ N subsets of it and sum elements for each subset. Given what we obtained, restore a possible initial set. QUICK EXPLANATIONWe build our solution step by step. Each step we take smallest element from sums. Suppose we’re at step i and we found element x[i]. We should erase now from sums all sums formed by x[i] and a nonempty subset of {x[1], x[2], ..., x[i – 1]}. EXPLANATIONLet’s call all 2^N sums sumSet. Also, let’s call a possible solution valueSet (making sum of all subsets of valueSet, you should obtain sumSet). The problem says there is always a possible solution. We’ll implement sumSet as a multiset from C++. This container allows following things, which will be needed later: find/delete an element and keep the set in increasing order. We’ll note first element from current sum set as sumSet[1], second element as sumSet[2] and so on. Let’s read all numbers from the input and add all of them in multiset sumSet. Smallest element from sumSet is always 0 (and it corresponds to empty subset). It does not give us any information, so let’s erase it from the set and move on. What’s smallest element now? Is it an element from valueSet? Is it a sum of a subset of valueSet? There exists at least one element from valueSet equal to smallest element from sumSet. Why? Suppose first element of sumSet is a sum of other elements of valueSet. sumSet[1] = valueSet[k1] + valueSet[k2] + .... where k1, k2, ... are some indexes. Since numbers are positive, we get that valueSet[k1] <= sumSet[1], valueSet[k2] <= sumSet[1] and so on. Since sumSet[1] is smallest element possible, we can only get that valueSet[k1] = sumSet[1], valueSet[k2] = sumSet[1] and so on. This means at least one element from valueSet will have value equal to sumSet[1]. We’ve found one element from valueSet. Let’s add it to valueSet (we build the set incrementally) and erase it from sumSet. Let’s move now to our new sumSet[1] element (smallest element from sumSet, not deleted yet). We can follow same logic from above and see that sumSet[1] is a new element from valueSet. Let’s add it to valueSet and erase it from sumSet. We move once again to sumSet[1]. Now, we have a problem. It can be one of following 2 possibilities:
Case b) is ideal, because we found one more element of valueSet. What to do with case a)? We know sum valueSet[1] + valueSet[2]. So we can simply erase it from sumSet, before considering sumSet[1]. Then, only case a) is left, so we find valueSet[3]. We erase now valueSet[3] from sumSet (I know, it becomes boring already, I’ll finish in a moment :) ). It’s more tricky now what can be sumSet[1]. It can be one of following: valueSet[3]+valueSet[1], valueSet[3]+valueSet[2], valueSet[3]+valueSet[1]+valueSet[2]. We can fix this by erasing all those elements from sumSet before considering sumSet[1]. Once again, we’re left with valueSet[4]. Let’s note that all sums that should be erased contain a valueSet[3] term and a nonempty subset of {valueSet[1], valueSet[2]}. Sums of subsets of {valueSet[1], valueSet[2]} are already erased in previous steps. Generalizing the algorithmLet’s generalize the algorithm. Suppose you want to calculate valueSet[n]. We need firstly to erase from set a combination of valueSet[n – 1] and a nonempty subset of {valueSet[1], valueSet[2], ..., valueSet[n – 2]}. Then, the smallest element is valueSet[n]. We can keep an additional array subsets[] representing all subset sums obtained from {valueSet[1], valueSet[2], ..., valueSet[n – 2]}. Then, at step of calculating valueSet[n], we need to erase subsets[j] + valueSet[n – 1] from our sumSet. Now, valueSet[n] is calculated. The new subset sum list will be the old one plus the one that contains valueSet[n – 1]. So, after we calculate valueSet[n], we update subsets with all values valueSet[n – 1] + subSets[j]. We run this algorithm as long as there is at least one element in sumSet. Time ComplexityEach element is added in the multiset once and erased once. Hence, the complexity is O(2 ^ N * log(2 ^ N)) = O(2 ^ N * N). AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 20 Oct '14, 00:22
showing 5 of 6
show all

The valueSet and sumSet thing is not very understandable. answered 20 Oct '14, 01:10

Weak test cases for this question.... My logic is completely wrong but it passed in the practice section. one of the test case is 1 , 3 , 0 1 1 2 2 3 3 4 giving 1 1 3 but correct answer is 1 1 2 . sol link : http://www.codechef.com/viewsolution/5196910 answered 21 Oct '14, 07:55
My corrected sol : http://www.codechef.com/viewsolution/5199200
(21 Oct '14, 08:21)

here in PREREQUISITES it says heap.. what is the use of heap here ?? answered 05 Oct '17, 16:18

5193943 is my submission id. I haven`t been able to find counter test case. So kindly help.link to my solution which is wrong is given. http://www.codechef.com/viewsolution/5193943 Thanks :) answered 20 Oct '14, 01:30
1
Hey @yogeshkr0007 have a look this testcase is the one to which your solution is wrong http://ideone.com/AtDZaH
(20 Oct '14, 02:33)
hey. i edited the link. same situ though. thanks anyways.
(20 Oct '14, 02:57)
May you please tell me how you got 0 0 1 1 1 1 2 2 by adding the elements of subsets of set={0,1,0} in your given test case as the possible subsets are {},{0},{1},{0,1},{1,0},{0},{0,1,0},{0,0} and the array formed is 0 0 1 1 1 0 1 0.Correct me if I am wrong.
(20 Oct '14, 19:38)
@hkbharath The test case you provided is wrong and does not satisfies the constraints in the first place. It is clearly give that the original array can only consist of positive integers, hence you cannot have more than one 0's in the test case itself.
(20 Oct '14, 20:25)
@rishavz_sagar 0,1,0 is the wrong answer for input 0 0 1 1 1 1 2 2. I gave a testcase for which code was returning wrong answer.
(28 Aug '17, 15:03)

I implemented a similar algorithm using unordered_map. I belive that the amortized timecomplexity must be around the same. Could anyone help me understanding why this would give TLE? Here is the relevant link. Thanks. http://www.codechef.com/viewsolution/5184582 answered 20 Oct '14, 04:51

Amazing !!! Anyone please look at these two solutions : 1.) http://www.codechef.com/viewsolution/5195961 2.) http://www.codechef.com/viewsolution/5195984 .First one is TLE whereas second is AC. Onlyone difference is that i'm just using "st.count" for checking whether that element is in that multiset before deleting it, it's a natural way of deleting element from STL containers..But,it gave TLE, whereas not checking this gives AC . Anyone please explain me the behavior or uses of these functions. answered 20 Oct '14, 15:39
That is because count() is linear in time.Refer this link I guess overall complexity is increased to O((2^n)log(2^n)(number of subsets at that time)).
(20 Oct '14, 21:28)

getting WA . please help http://www.codechef.com/viewsolution/5196157 answered 20 Oct '14, 16:38

Kudos to your Explanation and your Code Anudeep answered 20 Oct '14, 17:51

please add solutions...
Solutions are not opening, check the links please
it's ok now ;)
very well written :)
Very nice explanation :)
The concept is quite nice. I tried to implement exactly the same thing in code. However, I did not know about the container, and hence my solution became very complicated. :(