getting WA ANUMLA

getting WA problem link: ANUMLA Problem - CodeChef
solution link: CodeChef: Practical coding for everyone
plz give your suggestion thanks!!

Hi! Lets take an example t=1, n=3, input numbers are 0, 1, 2, 1, 5, 4, 5, 6. After sorting it gives 0, 1, 1, 2, 4, 5, 5, 6. As per your approach the answer would be 1, 1, 2. The correct answer is 1, 1, 4. Detailed explanation given at ANUMLA Editorial.

1 Like

Let us take three numbers x,y,z. The subsets formed are {},{x},{y},{z},{x+y},{x+z},{y+z},{x+y+z}

In your solution, you assumed that the smallest three numbers are the elements of array i.e. x,y,z are the smallest elements in this whole power set arrangement but it is not.

Let us take x=1, y=1 and z=3

The subset sum of {x+y} comes to be 2 which is lesser than z and hence it comes before in the sorted order

So try to correct your approach

You can also refer to my solution using bit masking http://www.codechef.com/viewsolution/5187836

1 Like