10032 Tug of war

[Stephan.Ritscher]

Some time ago I submitted a solution (AC) to this problem, but when thinking about it I found a test case on that my solution failes:
1
8
120 111 111 101 20 11 11 1

Please add this and similar test cases.

PS: My algorithm first makes an initial distribution. Therefore every person is assigned to the group with the so far smaller sum of weights. (This can be even improved by sorting the persons decending). You also have to make sure that both groups have (almost) same number of persons.
Then the algorithm improves the distribution. It searches pairs (a, b) with person a in the first group and person b in the second group so that switching a and b improves the distribution (difference of weights gets smaller).
If no pair satifying this condition is found, the algorithm terminates.
If the critical test cases are too small, one could extend the algorithm to search tupels (a, b, c, d) with a,b in group one and c,d in group two - as soon as no pairs are found.

[Carlos]

I'm trying to solve that. I made a random input, but I couldn't find any two AC submissions giving the same result.

Now I'm rejudging every submissions using one of the outputs I got from those programs - the one I think is correct (don't get afraid if you get a WA veredict, it's only temporary). If I find a valid solution I'll finish making the right input.

[Carlos]

I thi I've found a good solution, and about 5% people got AC. If any of you still think the problem datasets are not ok, please open another thread.