Lesson 15: MinAbsSum

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., sum / 2).

じつのところ、この問題は下のPDFに既にCoility社によって書かれているので、今回は単にC言語版を書くだけにします。最後の答えを探す部分のループは別の方向へスタートする方が良いのではと思います（例えばsum / 2 から０へ）

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

(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

はやいのはこちらです。Nとmax(abs(A))の大きさによって、上のコードと今回のコードを切り替えるのが一番良いのではないかと思います。

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