Lesson 15: MinAbsSum (Min Abs Sum)

Lesson 15: MinAbsSum
https://codility.com/programmers/lessons/16

Indeed, this problem is already described in the below PDF by Codility, so I simply show some C version of the solution. I think the last part to seek for the answer can be better to start from other direction (i.e., from sum / 2 to 0).

https://codility.com/media/train/solution-min-abs-sum.pdf

First, here I the slower version.

This gets the 100% correctness, but fails many tests for the performance score.

(1) The O(N^2 * max(abs(A))) solution

#include <alloca.h>
#include <memory.h>
#include <math.h>

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;
}

(2) The O(N * max(abs(A))^2) solution

The faster version gives the 100% score.
So I think switching the algorithms to use depending on the N and Max would be a better strategy.

#include <alloca.h> #include <memory.h> #include <math.h> 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; }