Replace operators of equation, so that the sum is equal to zero

Question

I'm given the equation like this one:

n = 7
1 + 1 - 4 - 4 - 4 - 2 - 2

How can I optimally replace operators, so that the sum of the equation is equal to zero, or print  -1. I think of one algorithm, but it is not optimal. I have an idea to bruteforce all cases with complexity O(n*2^n), but (n < 300).

Here is the link of the problem: http://codeforces.com/gym/100989/problem/M.

Answer 1

You can solve this with dynamic programming. Keep a map of all possible partial sums (mapping to the minimum number of changes to reach this sum), and then update it one number at a time,

Here's a concise Python solution:

def signs(nums):
    xs = {nums[0]: 0}
    for num in nums[1:]:
        ys = dict()
        for d, k in xs.iteritems():
            for cost, n in enumerate([num, -num]):
                ys[d+n] = min(ys.get(d+n, 1e100), k+cost)
        xs = ys
    return xs.get(0, -1)

print signs([1, 1, -4, -4, -4, -2, -2])

In theory this has exponential complexity in the worst case (since the number of partial sums can double at each step). However, if (as here) the given numbers are always (bounded) small ints, then the number of partial sums grows linearly, and the program works in O(n^2) time.

A somewhat more optimised version uses a sorted array of (subtotal, cost) instead of a dict. One can discard partial sums that are too large or too small (making it impossible to end up at 0 assuming all of the remaining elements are between -300 and +300). This runs approximately twice as fast, and is a more natural implementation to port to a lower-level language than Python for maximum speed.

def merge(xs, num):
    i = j = 0
    ci = 0 if num >= 0 else 1
    cj = 0 if num < 0 else 1
    num = abs(num)
    while j < len(xs):
        if xs[i][0] + num < xs[j][0] - num:
            yield (xs[i][0] + num, xs[i][1] + ci)
            i += 1
        elif xs[i][0] + num > xs[j][0] - num:
            yield  (xs[j][0] - num, xs[j][1] + cj)
            j += 1
        else:
            yield (xs[i][0] + num, min(xs[i][1] + ci, xs[j][1] + cj))
            i += 1
            j += 1
    while i < len(xs):
        yield (xs[i][0] + num, xs[i][1] + ci)
        i += 1

def signs2(nums):
    xs = [(nums[0], 0)]
    for i in xrange(1, len(nums)):
        limit = (len(nums) - 1 - i) * 300
        xs = [x for x in merge(xs, nums[i]) if -limit <= x[0] <= limit]
    for x, c in xs:
        if x == 0: return c
    return -1

print signs2([1, 1, -4, -4, -4, -2, -2])

Answer 2

Here is the implementation in C++:

unordered_map <int, int> M, U;
unordered_map<int, int>::iterator it;
int a[] = {1, -1, 4, -4};

int solve() {
    for(int i = 0; i < n; ++i) {
        if(i == 0) M[a[i]] = 1;
        else {
            vector <pair <int, int>> vi;
            for(it = M.begin(); it != M.end(); ++it) {
                int k = it->first, d = it->second;
                vi.push_back({k + a[i], d});
                vi.push_back({k - a[i], d + 1});
            }
            for(int j = 0; j < vi.size(); ++j) M[vi[j].first] = MAXN;
            for(int j = 0; j < vi.size(); ++j) {
                M[vi[j].first] = min(M[vi[j].first], vi[j].second);
            }
        }
    }
    return (M[0] == 0 ? -1 : M[0] - 1);
}