Question: https://codility.com/demo/take-sample-test/delta2011
Question Name: Delta2011 or Min-Abs-Sum or MinAbsSum
I did not solve it in a golden way. The official solution is so elegant.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | def solution(A): # Since S could be 1 or -1, it does not matter that # each element in A is positive or negative. A = [abs(item) for item in A] sumOfA = sum(A) # Get the number distribution. So we do not need to try # each number for multiple times. numbers = {} for item in A: numbers[item] = numbers.get(item, 0) + 1 # This is the KEY point. # Typically, we will use possible = [False] * len to track, which numbers # could be the result by summing up subsets of A. # For a number, appeared for many times, there will be multiple attempts # for it. But in this way, when we are trying number n, # possible[i] == -1 means it is impossible. # possible[i] == i >= 0 means it is possible and there are i n(s) left to use. # So for ALL number n(s), we only need ONE scan over the record. possible = [-1] * (sumOfA // 2 + 1) possible[0] = 0 for number in numbers: # Try each distinct number for trying in xrange(sumOfA//2+1): if possible[trying] >= 0: # Can be reached with previous numbers possible[trying] = numbers[number] elif trying >= number and possible[trying-number] > 0: # Cannot be reached with only previous numbers. # But could be achieved with previous numbers AND current one. possible[trying] = possible[trying-number] - 1 # Divide the A into two parts: P and Q, with restriction P <= Q. # So P <= sumOfA // 2 <= Q. We want the largest possible P, so that # Q-P is minimized. for halfSum in xrange(sumOfA//2, -1, -1): if possible[halfSum] >= 0: return sumOfA - halfSum - halfSum raise Exception("Should never be here!") return 0 |
Is there a link with more official solutions like the one you provided in this post?
Thanks
I do not have a list of official solutions. Typically, if there is, a link to the official solution is provided in the problem description.
First, I am very sorry if I am beginner. I dont’ understand the part at set {-1,1}. What is it about? Could someone please explain it to me?
It means, every element in S is either 1 or -1.