QUCOITA - Editorial

PROBLEM LINK

Contest

Practice

Author: grebnesieh

Tester: krooonal

DIFFICULITY

Medium

PREREQUISITES

DP

PROBLEM

Given a set S, divide it into two dis-joint sets such that the sum of individual sets is less than a given integer C.

EXPLANATION

This one as well is rooted in truth. Somewhat.

In our first year we have several courses spread out over the two semesters in pretty much the same way as you see in the problem. There isn’t one called “Introduction to Algorithms” though. So this question was pretty much begging to be written.

This question also turned out to be a variation of common DP problems like knapsack or subset sum, which is why I decided to add the extra constraint.

First, the central problem. You can reduce it to the following.

Given a set of sumbers S. Divide it into two subsets X, Y according to the following constraints.

X union Y = S
X intersection Y = {}
sum(X) <= C
sum(Y) <= C

but, we can say that

sum(Y) = sum(S) - sum(X)

therefore,

sum(S) - sum(X) <= C

which gives you

sum(S) - C <= sum(X) <= C

We can now recursively iterate over the whole list and at each step we make the choice of whether or not we pick the current item, whenever we reach a recursive call that conforms to the condition derived above, we have a solution. Unfortunately, two choices over 100 items leads to a O(2 ^ 100) solution.

We can however greatly reduce that number by using memoization. Besically the upper bound on the sum of a selected subsequence of S is 10000. Therefore, our recursive call can have at most 100 * 10000 variations, and we have enough space to store the return call of each of them.

If you are confused, perhaps some code will make it more clear:

def solve(i, t):
    if (i, t) in D:             #
        return D[(i, t)]        # memoization
    D[(i, t)] = False           #
    if l <= t <= r:             
        return [[], A[i:]]      # return the skeleton of the two sets, the moment you find a solution
    elif i == n: 
        return False
    else:
        ret = solve(i + 1, t + A[i])
        if ret:                         #
            ret[0].append(A[i])         #
            return ret                  #
        ret = solve(i + 1, t)           #   rebuild the skeleton depending upon which 
        if ret:                         #   choice (if any) resulted in the acceptable division
            ret[1].append(A[i])         #
            return ret                  #
    return False
for _ in xrange(input()):
    n, g = map(int, raw_input().split())
    A = map(int, raw_input().split())
    l = sum(A) - g
    r = g
    D = {}
    A.sort()
    ans = solve(0, 0)
    if ans: 
        print "YES"
        for x in ans:
            print ' '.join(map(str, sorted(x)))
    else: 
        print "NO"

Here, solve(i, t) represents that the subset selected out of the items before the ith item has a total sum of t. Any time a function call returns False, we store it and hence don’t need to entertain it again. The moment we find an answer we stop.

I have used a dictionary for memoization in Python, in this case you could very well use a simple array/list or a map if you are using C++.

Now remains the question of whether or not our answer returns lexicographically smallest result for the set X. Since we first make the recursive call where we chose the i’th item, it ensures that the only time we don’t select it is when it is impossible to do so.

Since we initially sorted all the numbers, this leads to a lexicographically smallest set X.

1 Like

Where can we submit our code after the contest