Codility and other programming lessons: Lesson 15: MinAbsSum (Min Abs Sum)
18 return result
(1) The O(N^2 * max(abs(A))) solution
Let dpi equal 1 if it is possible to achieve the sum of i using elements of A, and 0 otherwise
int solution(int A[], int N)
{
int max = 0;
int sum = 0;
for (int i = 0; i < N; i++){
A[i] = abs(A[i]);
max = max < A[i] ? A[i] : max;
sum += A[i];
}
int memsize = sizeof(int) * (sum + 1);
int* dp = (int*)alloca(memsize);
memset(dp, 0x00, memsize);
dp[0] = 1;
for (int i = 0; i < N; i++){
for (int j = sum; j >= 0; j--){
if (dp[j] == 1 && j + A[i] <= sum){
dp[j + A[i]] = 1;
}
}
}
int result = sum;
for (int p = 0; p * 2 <= sum; p++){
if (dp[p] == 1){
int q = sum - p;
int diff = q - p;
result = diff < result ? diff : result;
}
}
return result;
}
Golden solution O(N · M2)
• dpj = −1 if we cannot get the sum j, • dpj 0 if we can get sum j.
int solution(int A[], int N) { int max = 0; int sum = 0; for (int i = 0; i < N; i++){ A[i] = abs(A[i]); max = max < A[i] ? A[i] : max; sum += A[i]; } //the absolute values of A[] are between [0..100] int num_memsize = sizeof(int) * (max + 1); int* count = (int*)alloca(num_memsize); memset(count, 0x00, num_memsize); for (int i = 0; i < N; i++){ count[A[i]]++; } int dp_memsize = sizeof(int) * (sum + 1); int* dp = (int*)alloca(dp_memsize); //clear up with -1. memset(dp, 0xFF, dp_memsize); dp[0] = 0; for (int i = 1; i <= max; i++){ if (count[i] <= 0){ continue; } for (int j = 0; j <= sum; j++){ if (dp[j] >= 0){ dp[j] = count[i]; } else if (j >= i && dp[j - i] > 0){ dp[j] = dp[j - i] - 1; } } } int result = sum; for (int p = 0; p * 2 <= sum; p++){ if (dp[p] >= 0){ int q = sum - p; int diff = q - p; result = diff < result ? diff : result; } } return result; }
http://phiphy618.blogspot.jp/2013/05/codility-delta-2011-minabssum.html
to-do: http://codesays.com/2014/solution-to-min-abs-sum-of-two-by-codility/
Read full article from Codility and other programming lessons: Lesson 15: MinAbsSum (Min Abs Sum)
For a given array A of N integers and a sequence S of N integers from the set {−1, 1}, we define val(A, S) as follows:
val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }|
(Assume that the sum of zero elements equals zero.)
For a given array A, we are looking for such a sequence S that minimizes val(A,S).
Write a function:
int solution(int A[], int N);
that, given an array A of N integers, computes the minimum value of val(A,S) from all possible values of val(A,S) for all possible sequences S of N integers from the set {−1, 1}.
For example, given array:
A[0] = 1 A[1] = 5 A[2] = 2 A[3] = -2
your function should return 0, since for S = [−1, 1, −1, 1], val(A, S) = 0, which is the minimum possible value.
Assume that:
- N is an integer within the range [0..20,000];
- each element of array A is an integer within the range [−100..100].
Complexity:
- expected worst-case time complexity is O(N*max(abs(A))2);
- expected worst-case space complexity is O(N+sum(abs(A))), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
https://codility.com/media/train/solution-min-abs-sum.pdf
Since we can arbitrarily
choose to take the element or its negative, we can simplify the problem and
replace each number with its absolute value. Then the problem becomes dividing
the numbers into two groups and making the di erence between the sums of the
two groups as small as possible. It is a classic dynamic programming problem.
Assume the
sum of absolute values of all the numbers is S. We want to choose some of the numbers (absolute values) to make
their sum as large as possible without exceeding S2 . Why? Let P be the sum of the first group, Q be the sum of the other group and P < Q. We have P ¬ S2 ¬ Q and Q + P = S.
The larger is P , the smaller is Q and the di erence Q − P . Hence, the
largest possible P ¬ S2 gives the optimal
result. Let M be the maximal element
in the given array A. We create an
array dp of size S.
Slow solution O(N2 · M)
1 def slow_min_abs_sum(A):
2
N =
len(A)
3
M = 0
4 for i in xrange(N):
5 A[i] = abs(A[i])
6 M = max(A[i], M)
7
S = sum(A)
8 dp = [0] * (S + 1)
9
dp[0] =
1
10
for j in xrange(N):
11
for i in xrange(S, -1, -1):
12
if (dp[i] == 1) and (i + A[j] <= S):
13 dp[i + A[j]] = 1
14
result = S
15
for i in xrange(S // 2 + 1):
16
if dp[i] == 1:
17 result = min(result, S - 2 * i)18 return result
Golden solution O(N · M2)
1 def golden_min_abs_sum(A):
2
N = len(A)
3
M = 0
4 for i in xrange(N):
5 A[i] = abs(A[i])
6 M = max(A[i], M)
7
S = sum(A)
8 count = [0] * (M + 1)
9 for i
in xrange(N):
10
count[A[i]] += 1
11
dp =
[-1] * (S + 1)
12
dp[0] =
0
13
for a in xrange(1, M + 1):
14
if count[a] > 0:
15
for j in xrange(S):
|
16
|
if
dp[j] >=
|
0:
|
|
|
17
|
dp[j] =
|
count[a]
|
|
|
18
|
elif (j >= a
and dp[j
|
- a] > 0):
|
|
|
19
|
dp[j] =
|
dp[j - a]
|
- 1
|
20
result = S
21
for i in xrange(S // 2 + 1):
22
if dp[i] >= 0:
23
result
= min(result, S - 2 * i)
24
return result
The time complexity of the above solution is O(N
· M 2), where M is the maximal element, since S
= O(N · M) and there are at
most M di erent values in A.
http://codesays.com/2014/solution-to-delta2011-min-abs-sum-by-codility/
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
Also check http://codesays.com/2014/solution-to-delta2011-min-abs-sum-by-codility/(1) The O(N^2 * max(abs(A))) solution
Let dpi equal 1 if it is possible to achieve the sum of i using elements of A, and 0 otherwise
int solution(int A[], int N)
{
int max = 0;
int sum = 0;
for (int i = 0; i < N; i++){
A[i] = abs(A[i]);
max = max < A[i] ? A[i] : max;
sum += A[i];
}
int memsize = sizeof(int) * (sum + 1);
int* dp = (int*)alloca(memsize);
memset(dp, 0x00, memsize);
dp[0] = 1;
for (int i = 0; i < N; i++){
for (int j = sum; j >= 0; j--){
if (dp[j] == 1 && j + A[i] <= sum){
dp[j + A[i]] = 1;
}
}
}
int result = sum;
for (int p = 0; p * 2 <= sum; p++){
if (dp[p] == 1){
int q = sum - p;
int diff = q - p;
result = diff < result ? diff : result;
}
}
return result;
}
Golden solution O(N · M2)
• dpj = −1 if we cannot get the sum j, • dpj 0 if we can get sum j.
int solution(int A[], int N) { int max = 0; int sum = 0; for (int i = 0; i < N; i++){ A[i] = abs(A[i]); max = max < A[i] ? A[i] : max; sum += A[i]; } //the absolute values of A[] are between [0..100] int num_memsize = sizeof(int) * (max + 1); int* count = (int*)alloca(num_memsize); memset(count, 0x00, num_memsize); for (int i = 0; i < N; i++){ count[A[i]]++; } int dp_memsize = sizeof(int) * (sum + 1); int* dp = (int*)alloca(dp_memsize); //clear up with -1. memset(dp, 0xFF, dp_memsize); dp[0] = 0; for (int i = 1; i <= max; i++){ if (count[i] <= 0){ continue; } for (int j = 0; j <= sum; j++){ if (dp[j] >= 0){ dp[j] = count[i]; } else if (j >= i && dp[j - i] > 0){ dp[j] = dp[j - i] - 1; } } } int result = sum; for (int p = 0; p * 2 <= sum; p++){ if (dp[p] >= 0){ int q = sum - p; int diff = q - p; result = diff < result ? diff : result; } } return result; }
http://phiphy618.blogspot.jp/2013/05/codility-delta-2011-minabssum.html
首先对数组做处理，负数转换成对应正数，零去掉，计数排序统计有多少个不同元素及其对应个数，并累加所有数的和sum，不妨记b=sum/2，不同元素个数为m，则目标转换为在m个不同元素中挑出若干个元素（每个元素可以重复多次，但少于它们的出现次数），使得它们的和不大于b并尽量接近。到了这里，应该有点熟悉的感觉了吧。对了，其实这就是0-1背包问题！
记 f[i][j] 为只允许选前 i 个元素，总和不超过 j ，则有 f[i][j] = max { f[i-1][j], f[i][j-D[i]]+D[i] }, 其中 D[i] 为第 i 个元素对应的值。由于每种元素的数量不是无穷多，因此对每个 f[i][j] ，都需要记录第 i 种元素的消耗数量，保证小于该元素的出现次数。
第一次的代码并未完全通过，75分，大数据全挂。原因是这里一个元素可以出现多次，是多重背包问题。
public int solution(int[] A) { // write your code here... if (A.length == 0) return 0; int sum = 0; int max = 0; for (int i = 0; i < A.length; i++) { if (A[i] < 0) A[i] = -A[i]; sum += A[i]; } int target = sum / 2; int dp[][] = new int[A.length][target]; for (int i = 0; i < A.length; i++) { for (int j = 0; j < target; j++) { // j+1 is the weight limit if (i == 0) { if (A[i] <= (j+1)) { dp[i][j] = A[i]; } else { dp[i][j] = 0; } } else // i != 0 { int w1 = dp[i-1][j]; int w2 = 0; if (j-A[i] >=0 ) { w2 = dp[i][j-A[i]] + A[i]; } dp[i][j] = w1 > w2 ? w1 : w2; } } } max = dp[A.length - 1][target - 1]; return (sum - max * 2); }Read full article from Codility and other programming lessons: Lesson 15: MinAbsSum (Min Abs Sum)
