ANUMLA - Editorial

@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

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!

@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. :slight_smile:

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

3 Likes

My corrected sol : http://www.codechef.com/viewsolution/5199200

@prakharmy @johri thank you. understood

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.

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

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

can anyone explain the algorithm with example???

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

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

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

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

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

We can apply backtracing…

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