2888 - Child Play

[andmej]

I think this problem can be solved using dynamic programming (DP). I have built a table dp, where dp[i][j] is explained as follows:

Using slabs [0..i], I can organize them in such a way that the sum of the upper sides is a, and the sum of the lower sides is b. Now let the difference between a and b equal j, that is, abs(a - b) == j, then dp[i][j] == max(a, b) or -infinity if it's impossible to form 2 groups of difference j using first i slabs.

This approach let's me find out if I can form a difference of 0 using all slabs, and hence I have the answer when you should not discard any slabs.

But I don't know how to tell if discarding exactly one slab would let me form the groups to have a difference of 0.

Any help is appreciated.