Minimum Installed Difference

Question

I came across this question on this website called codility, but I can't figure out how to solve it, appreciate the help

For an array A of n integers and a sequence S of n elements 1 or -1, we determine the value:

Assume that the sum of the zero elements is zero. Write function

int min_abs_sum(int[] A); 

than a given array A of n integers from the range [-100.100] calculates the minimum possible value val (A, S) (for any sequence S with elements 1 or -1). You can assume that n <= 20,000 .

For example, this array: a = {1,5,2, -2}

your function should return 0, since for the sequence S = (- 1,1, -1,1) val (A, S) = 0.

Here are two links for some people: it does not show the solution, but shows the complexity of their algorithms, the first link shows the complexity with which the program should work, and the second is slower.

1st link of 100% marks

Second link 86% of stamps

Answer 1

This is a poorly worded version of a partition problem. You are going to split array A into 2 groups as close to each other as possible. The one with the largest amount will assign +1 to the S array, and the other group will get -1. Select a solution to the partition problem and configure it to return the answer to this question. Actually, this is a variant of the section that searches for the best possible value, and not 2 equal sets.

EDIT here is what Python code based on a document related to @Jerry Coffin

 def min_abs_sum(A): vals = [] for x in A: for v in vals: n = v+x if (abs(n)<=1000000) and (n not in vals): vals.append(n) n = vx if (abs(n)<=1000000) and (n not in vals): vals.append(n) if (x not in vals): vals.append(x) if (-x not in vals): vals.append(-x) return (min([abs(x) for x in vals])) 

One millionth is half a 20,000 (maximum number in A) times 100/2. I used a list instead of an array, which means that some things will be faster and slower than what they do in this article. It is possible that mines are achieved by summing the first half of the numbers and subtracting the second half - or something like that that requires large subtotals. I use a list, not an array, but the size is still limited. Sorry, I do not do Java.

Answer 2

This basically works with dividing a into two parts with the sum of the absolute values ​​of the two parts as close to each other as possible.

Then you want to multiply these elements by 1 or -1 to make one section negative and the other positive. As you do this, you summarize them to get the final answer.

From the point of view of the algorithm, I believe that the partition step is almost certainly NP-complete (phrases like “subset of the sum” and “partition problem” come to mind). From a programming point of view, it's pretty simple, but - exhaustively test the possibilities until you get the best. As long as the number of elements is small (up to a dozen or so [edit: since it's O (2 ^N ), you can probably increase it to 30-40) be fast enough.

I believe that it should be proportional to O (N!), Although if the array turns out to be big, time will quickly become unreasonable. Since you are only divided into two sets and the order inside the sets does not matter, O (2 ^N ) instead of O (N!). It does not grow almost as fast as O (N!), But still fast enough to make large sets unfounded for processing.

I should add, however, that Codility seems to specialize in issues that initially might seem NP-complete, but not really - if you missed out on any detail in your description, the problem could be significantly simpler.

Edit: When re-reading it, the problem may be that I ignored an important detail: a limited range. I'm not sure how you use it, but I'm sure it is important to create an effective solution. My immediate assumption is that it is based on something similar to changing a sort based on a sort (like a bucket). I did not think it out in any real detail, though ...

Edit2: When doing a little look (and prompting @Moron), a limited range is important, and my thinking about how it appears in the solution was generally correct. @Moron was kind enough to point to a Wikipedia entry for the problem of summing up a subset, but I did not find it particularly well written. With a little glance at the Cornell explanation document, I found it a bit cleaner / clearer.

Answer 3

The following Java solution will earn 100% in Codility. My solution is based on the "Section with duplicate items" section in an article related to @Jerry Coffin, but I also added some additional optimizations.

 import java.util.Arrays; class Solution { public int solution ( int[] A ) { int n=A.length,r=0,c=1,sum=0,mid=0; // Add all numbers, replace them with their absolute value, and sort them for(int i=0;i<n;i++) { A[i]=Math.abs(A[i]); sum+=A[i]; } Arrays.sort(A); // This minimizes the speed of growth of r in the loop below and allows us to count duplicates while scanning the array mid=sum/2; // If the number is odd the result is rounded down (the best possible solution is 1 instead of 0). // Find the subset of numbers whose sum is closest to half the total sum boolean[] bs=new boolean[mid+101]; // We only need to check sets that are equal or less than half the sum of the numbers (to avoid having to check the sum in the inner loop I sacrifice 100 booleans since 100 is the maximum value allowed) bs[0]=true; // The set with zero elements always adds to 0 for(int i=0;i<n;i++){ if( A[i]==0 ) continue; // Count duplicate entries if(i<n-1 && A[i]==A[i+1] ){ c++; continue; } // Scan the subset sum result array from right to left and add A[i] c times to existing subset sums for (int j = r; j >= 0; j--) if(bs[j] ){ int m= Math.min(mid, j+A[i]*c ); for(int k= j+A[i];k<=m && !bs[k];k+=A[i] ) bs[k]=true; // To avoid duplicate work when dealing with multiples of previous numbers the loop stops if we find an entry has already been set. } r=Math.min(mid, r+A[i]*c); // New rightmost subset sum can be no more than the mid point while(!bs[r]) r--; // Scan back to rightmost subset sum if(r==mid) break; // Found an optimal solution; no need to continue c=1; } return sum-2*r; // The rightmost subset sum that does not go over half the sum is the best solution, compute the difference of the complementary subsets (r and sum-r). } } 

Answer 4

So the goal would be as close to 0 as possible.

My first thought was that I sort the array in descending order, and then iterate over the list, doing something like this:

 int total = 0; foreach(int i in a) { total = Math.Min(Math.Abs(total - i), Math.Abs(total + i)); } 

which will work for a={1,5,2,-2} (total will be next 5,4,2,0 )

But I'm not sure if it works in all cases. I will look at it a little more, and then see if there is a case for which it does not work.

EDIT:

OK, I think brute force will work?

  public static int MinArray(int[] array) { int val = int.MaxValue; for (int i = 0; i < Math.Pow(2, array.Length); i++) { val = Math.Min(CalcMin(array, i), val); } return val; } private static int CalcMin(int[] array, int negs) { int ret = 0; for (int i = 0; i < array.Length; i++) { int neg = 1; if (negs != 0) { neg = negs % 2 == 1 ? -1 : 1; negs >>= 1; } ret += array[i] * neg; } return Math.Abs(ret); } 

So, I do every iteration of S (which is calculated by taking the binary code I in MinArray ) and finding min this way.

With a few changes, you can also get the correct value for S (if this is a requirement. If not, could this require you to score a few points in an interview?)

Answer 5

This can work fast:

 maxvalue = 100 def solve(data): def mark_sum(s): # wrap sum around maxvalue if s >= maxvalue: s -= maxvalue * 2 elif sum < -maxvalue: s += maxvalue * 2 # mark sum if s >= 0: s_new_pos[s] = True else: s_new_neg[s + maxvalue] = True s_old_pos = [False] * maxvalue # marks for sums [0..99] s_old_neg = [False] * maxvalue # marks for sums [-100..-1] s_old_pos[0] = True # seed array with zero sum for zero elements for n in data: s_new_pos = [False] * maxvalue s_new_neg = [False] * maxvalue for i in range(maxvalue): # mark new possible sums if s_old_pos[i]: mark_sum(i + n) mark_sum(i - n) if s_old_neg[i]: mark_sum(i - 100 + n) mark_sum(i - 100 - n) s_old_pos = s_new_pos s_old_neg = s_new_neg for i in range(maxvalue): if s_old_pos[i]: return i if s_old_neg[-1 - i]: return abs(-1 - i) raise AssertionError('my bad') 

No need to check all possible amounts (up to 1,000,000). You can simply wrap them around max_value. This replaces n with the value of max_value in time complexity.

Not sure yet: (

Answer 6

 def min_abs_sum(A): A[:] = sorted([ abs(i) for i in A if i != 0 ], reverse=True) s = sum(A) h = s / 2 r = find_balance_iter(h, A) return abs(2*(hr) - s) def find_balance_iter(v, A): r = v n = len(A) for i in xrange(n): if i and A[i] == A[i-1]: continue for j in xrange(ni-1): vv = v - A[i] rr = vv AA = A[i+j+1:] while True: if vv == 0 or vv in AA: return 0 if vv < 0 or not AA: rr = vv break if vv < AA[-1]: rr = min(vv-AA[-1], rr, key=compare) break vv -= AA[0] AA[:] = AA[1:] r = min(r, rr, key=compare) return r def compare(a): return (abs(a), a)