Take a test case:
1
3
0 1 2 3 4 5 6 7
Ans: 1 2 4.
So this logic fails.
@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.
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 ?
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)).
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
1 Like
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.
We can apply backtracingā¦
@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.
This was very useful as to be honest the original explanation was not clear enough despite authorās good effort.
Can anyone help explaining where I am going wrong calculating complexity :
for each new element found for valueSet, say n, we delete all subsets from sumSet which contains values already contained in valueSet + n. So for each new element n, we erase ~2^n elements in 2^nlog(2^n), and we need to do this n times, as valueSet contains n element. making time complexity O(n * 2^n* log(2^n) ). I agree with the proof of time complexity provided in editorial, just canāt understand where I am going wrong.
also donāt know why my solution gives SIGSGEV.
Thanks a lot bro, I love the way you explainā¦ Thank u so much
I am glad to mention here my simplest code. I have used same algorithm as editorial mentioned. But one could find easy understand the solution by this codeā¦link//
https://www.codechef.com/viewsolution/29314813
I have used min heap and a vector array of element found till now and their sums. First, sort sumSet and add 2nd and 3rd element and their sum in vector array. And add their sum to heap also. Now, proceed until we donāt get all elements.
- while our next element in sumSet is equal to top of heap, pop from heap and move to next element of sumSet. Note that top element of heap cannot be less than our current element of sumSet.
- Now, our current element of sumSet is our next actual element and print it. Add this element to all elements in vector array and push them to vector array and heap. Now, push current element to heap and move to next element of sumSet.
I am not able to find any test case that is failing this algo. Can anyone please tell me where I am wrong?
link to my solution
NICE EXPLANATION