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

×

ANUMLA - Editorial

41
6

PROBLEM LINK:

Practice
Contest

Author: Anudeep Nekkanti
Tester: Constantine Sokol
Editorialist: Florin Chirica

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 EXPLANATION

We 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 non-empty subset of {x[1], x[2], ..., x[i – 1]}.

EXPLANATION

Let’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:

  • sum of subset {valueSet[1], valueSet[2]}

  • a new element of valueSet.

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 non-empty subset of {valueSet[1], valueSet[2]}. Sums of subsets of {valueSet[1], valueSet[2]} are already erased in previous steps.

Generalizing the algorithm

Let’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 non-empty 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 Complexity

Each 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:

Author's solution
Tester's solution

This question is marked "community wiki".

asked 20 Oct '14, 00:22

elfus's gravatar image

3★elfus ♦♦
0102527
accept rate: 0%

edited 20 Oct '14, 03:25

dpraveen's gravatar image

4★dpraveen ♦♦
2.4k52127164

please add solutions...

(20 Oct '14, 00:34) rudra_sarraf3★

Solutions are not opening, check the links please

(20 Oct '14, 00:45) saurabhsuniljain3★

it's ok now ;-)

(20 Oct '14, 01:01) betlista ♦♦3★

very well written :)

(20 Oct '14, 02:05) kunalkukreja5★

Very nice explanation :)

(20 Oct '14, 02:20) aj954★

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. :(

(20 Oct '14, 10:38) paramjitrohit2★
showing 5 of 6 show all

The valueSet and sumSet thing is not very understandable.

link

answered 20 Oct '14, 01:10

rick93's gravatar image

2★rick93
612
accept rate: 0%

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

link

answered 21 Oct '14, 07:55

hatim009's gravatar image

3★hatim009
46421122
accept rate: 8%

(21 Oct '14, 08:21) hatim0093★

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 :)

link

answered 20 Oct '14, 01:30

yogeshkr0007's gravatar image

3★yogeshkr0007
111
accept rate: 0%

edited 20 Oct '14, 02:56

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) hkbharath3★

hey. i edited the link. same situ though. thanks anyways.

(20 Oct '14, 02:57) yogeshkr00073★

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) rishavz_sagar3★

@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) ayushj103★

@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, 15:03) hkbharath3★

I implemented a similar algorithm using unordered_map. I belive that the amortized time-complexity 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

link

answered 20 Oct '14, 04:51

fool_for_cs's gravatar image

4★fool_for_cs
462
accept rate: 33%

There can be problem when we have the next element in the valueset that is equal to sum of other subsets in valueset. for example, when we have our original valueset as 1 1 2. Then, the sumset would have originally contain 0 1 1 2 2 3 3 4. So, after finding Valuset[0] = 1, Valuset[1] = 1. If we remove ValueSet[0] + ValueSet[1] i.e. 2 from SumSet, then it would remove the original ValueSet[2] = 2 element. And the new state of the Sumset would be 3 3 4. So, we will miss element 2.

Please clariy if i am wrong anywhere.

link

answered 20 Oct '14, 12:35

suraj_singh89's gravatar image

2★suraj_singh89
-11
accept rate: 0%

Why are you removing both 2's??It's a multi-set, so only one instance of 2 will be removed and then it will become {2,3,3,4}.

(20 Oct '14, 14:31) xpertcoder4★

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.

link

answered 20 Oct '14, 15:39

thecoderju_np's gravatar image

4★thecoderju_np
151
accept rate: 0%

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) xpertcoder4★

Kudos to your Explanation and your Code Anudeep

link

answered 20 Oct '14, 17:51

raviteja1452's gravatar image

2★raviteja1452
151
accept rate: 0%

Since all the elements of the array are positive integers. Can we sort the subsets and get the first smallest N numbers ? have I understood the problem correctly ?

link

answered 20 Oct '14, 19:23

bajaj6's gravatar image

2★bajaj6
39135
accept rate: 0%

1

nope...u havent!!!

(20 Oct '14, 20:01) kunal3614★

Take a test case: 1 3 0 1 2 3 4 5 6 7 Ans: 1 2 4. So this logic fails.

(20 Oct '14, 20:02) johri212★

for array [1,2,4] possible subset {0},{1},{2},{4},{1,2},{2,4},{1,4},{1,2,4} . According to this line "Then for each subset, he calculated the sum of elements in that subset and wrote it down on a paper ". so the input will be: 0,1,2,4,3,6,5,7 ( in any order). @johri21 how you got that test case ?

(20 Oct '14, 20:43) bajaj62★
1

okay so take input

0 1 2 4 3 6 5 7 and your program would produce erroneous output 1 2 3 instead of correct output 1 2 4

(20 Oct '14, 22:57) prakharmy3★

@bajaj6 You will have T=1 N=3 than 0 1 2 3 4 5 6 7. I think you were not able to get T=1 and N=3. :)

(21 Oct '14, 01:09) johri212★

@prakharmy @johri thank you. understood

(21 Oct '14, 09:38) bajaj62★
showing 5 of 6 show all

Can anyone tell me what is wrong with following approach?

First check if there are more than 1 zeros. If there are two zeros then '0' is the first element otherwise if only one zero is found then the smallest non-zero positive element of given array is the first element of our ans.

Now subtract this min element from all other elements of given array. Again find the smallest positive and non-zero element it is the 2nd element and so on...

Please correct me if I am wrong!

Thank you!

link

answered 21 Oct '14, 00:17

mtbar131's gravatar image

2★mtbar131
163
accept rate: 0%

edited 21 Oct '14, 00:18

It is clearly given that the original array can only consist of positive integers, hence you cannot have more than one 0's in the test case itself.

And haven't you read the editorial? You can't subtract the first element from all the elements, because they may or may not contain the value of the first element in their sum.

(21 Oct '14, 16:13) ayushj103★

Can anyone provide me a good corner case where my solution fails? I'm getting WA.

Link to solution: http://www.codechef.com/viewsolution/5191980

Thanks in advance :)

link

answered 21 Oct '14, 16:15

ayushj10's gravatar image

3★ayushj10
163
accept rate: 0%

edited 21 Oct '14, 19:42

Can anyone give me a tricky/corner test case for this question. I am getting WA.

link

answered 21 Oct '14, 16:31

megatron_64's gravatar image

3★megatron_64
32236
accept rate: 0%

can anyone explain the algorithm with example????

link

answered 22 Oct '14, 09:09

nil96's gravatar image

2★nil96
18071842
accept rate: 5%

Can anyone please tell why the code is giving RTE http://ideone.com/sQbNRz

link

answered 22 Oct '14, 15:14

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

Can we apply the following algorithm? The maximum element (say max) in the sumset will be equal to sum of all elements in required array (since all elements are +ve). we know the value of N. Then subtracting max from next N largest element will give us the value of N elements in a array.. P.S correct me if i am wrong

link

answered 23 Oct '14, 13:51

legalroot's gravatar image

2★legalroot
212
accept rate: 0%

http://ideone.com/YSYAst ! for all test cases given above this gives the right answer .... can anyone reckon me the test case where i am wrong?

sum of the test cases i worked on are :-

8

3

0 1 1 1 2 2 2 3

3

0 1 2 3 3 4 5 6

3

0 1 100 1000 101 1001 1100 1101

4

0 1 2 3 4 3 4 5 5 6 7 6 7 8 9 10

4

0 1 1 2 2 2 3 3 3 3 4 4 4 5 5 6

2

1000000000 1000000000 2000000000 0

1

0 21

2

0 0 0 0

link

answered 03 Nov '14, 13:49

holyfuck's gravatar image

1★holyfuck
11
accept rate: 0%

edited 03 Nov '14, 13:50

Why s.erase(s.begin()) is not written in else part of the author's solution?? Can anyone please explain?!!

link

answered 28 Jan '15, 21:46

singh_abhinav's gravatar image

4★singh_abhinav
245615
accept rate: 0%

Why my logic is not working (getting runtime error.).....

Please help me out...

logic :- As we have the size of array (which is lost) then numbers present apart from the first one (which is always 0) the numbers from index (1) <..as index 0 the number is zero..> to N (size of lost array) we can have the numbers lost...

For eg.

line 1 :1

line 2 :3

line 3 :0 1 2 3 3 4 5 6

Ans :(1,2,3)(...after that the numbers would the sums of these numbers...)

My solution is : http://www.codechef.com/viewsolution/7481486

link
This answer is marked "community wiki".

answered 14 Jul '15, 22:59

kislaya123's gravatar image

2★kislaya123
111
accept rate: 0%

We can apply backtracing......

(14 Jul '15, 23:14) kislaya1232★

Can anyone tell me why i am getting runtime error? Link to my code is https://www.codechef.com/viewsolution/9950306

link

answered 20 Apr '16, 15:32

cpsupriya1996's gravatar image

2★cpsupriya1996
1
accept rate: 0%

i tried to sorted the input array in descending order and then subtract elements in 1 to n from 0: input[i]-input[0]....this gives me the n required elements...please tell me what is wrong with this approach

link

answered 23 Jul '16, 05:33

saurav_2014's gravatar image

3★saurav_2014
1
accept rate: 0%

What if we sort the array in descending order and then subtract each element from i=1 to n from element at i=0.... each element = sorted_input[0]-sorted_input[i] from i=1 to i=n

link

answered 23 Jul '16, 13:46

shubham805's gravatar image

3★shubham805
1
accept rate: 0%

For most of the test cases my code is working fine. I even checked for the end cases. But it is giving wrong answer. Can someone please help me to find the problem in the code or just provide some cases for which my code is not working. Any help is greatly appreciated.

https://www.codechef.com/viewsolution/11587934

link

answered 22 Sep '16, 00:45

cyberhax's gravatar image

2★cyberhax
261
accept rate: 50%

edited 22 Sep '16, 00:47

see my approach : I first sorted the values(sum of subsets) entered by user in ascending order and then I took first N of those sorted list(except the first zero) and displayed them out. for eg: sum of subsets enetred by user are: 0 10 24 11 15 6 5 4 after sorting : 0 4 5 6 10 11 15 24 result i displayed : 4 5 6 (only three are diplayed after zero because number of element is 3). but i am getting wrong answer.why?

link

answered 14 Mar, 05:38

neeraj745's gravatar image

4★neeraj745
1
accept rate: 0%

see my approach : I first sorted the values(sum of subsets) entered by user in ascending order and then I took first N of those sorted list(except the first zero) and displayed them out. for eg: sum of subsets enetred by user are: 0 10 24 11 15 6 5 4 after sorting : 0 4 5 6 10 11 15 24 result i displayed : 4 5 6 (only three are diplayed after zero because number of element is 3). but i am getting wrong answer.why?

link

answered 14 Mar, 05:40

neeraj745's gravatar image

4★neeraj745
1
accept rate: 0%

Let the input be : 0 1 2 4 3 6 5 7 so after sorting it is 0 1 2 3 4 5 6 7 and that gives the set {1,2,3} which is not right. The correct set is {1,2,4}

(14 Mar, 08:34) apptica5★

can anybody explain me the time complexity part ...why log(2^n)is multiplied with 2^n? thank you

link

answered 06 Apr, 18:39

jayant12's gravatar image

2★jayant12
1
accept rate: 0%

I approach the problem with the similar idea to the solution but I'm getting WA.Can anyone please help me?

http://ideone.com/F2G4iJ

link

answered 11 Jul, 11:48

tieuchanlong's gravatar image

0★tieuchanlong
11
accept rate: 0%

https://www.codechef.com/viewsolution/15146067

followed the editorial.. getting sigsev

link

answered 28 Aug, 03:25

ab9999's gravatar image

2★ab9999
11
accept rate: 0%

https://www.codechef.com/viewsolution/15146067

followed the editorial.. getting sigsev

link

answered 28 Aug, 03:25

ab9999's gravatar image

2★ab9999
11
accept rate: 0%

here in PREREQUISITES it says heap.. what is the use of heap here ??

link

answered 05 Oct, 16:18

bhola_nit's gravatar image

4★bhola_nit
1394
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:

×12,340
×2,686
×738
×149
×120
×58

question asked: 20 Oct '14, 00:22

question was seen: 10,487 times

last updated: 05 Oct, 16:18