Problem

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: 

    function solution($A);

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.

Write an efficient algorithm for the following assumptions:

·         N is an integer within the range [0..20,000];

·         each element of array A is an integer within the range [−100..100]. 

Note

| . . . | means take the positive value of what is inside.

In order to better understand the problem, three different sets of S are used for illustration, as follows: 

A = [1, 5, 2, -2] and S = [-1, +1, -1, +1]

val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }| = |1x(-1) + 5x(+1) + 2x(-1) + (-2)x(+1)|

= |(-1) + (+5) + (-2) + (-2)| = |-1 + 5 – 2 – 2| = |0| = 0 .

Note that the given set for S = [-1, +1, -1, +1] is just one of 2^N sets; other two sets of which are as follows: 

A = [1, 5, 2, -2] and S = [1, 1, 1, 1]

val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }| = |1x1 + 5x1 + 2x1 + -2x1| = |1 + 5 + 2 – 2| = |+6| = 6

A = [1, 5, 2, -2] and S = [-1, -1, +1, -1]

val(A, S) = |sum{ A[i]*S[i] for i = 0..N−1 }| = |1x-1 + 5x-1 + 2x+1 + -2x-1| = |-1 + -5 + +2 ++ 2| = |-1 - 5 + 2 + 2| = |-2| =  2 . 

The three answers here are 0, 6 and 2 and the minimum is 0. Zero does not necessarily have to be the minimum for other similar problems (tasks). The minimum can still be any number higher than 0 (for other problems).

In the problem description, it is said, “(Assume that the sum of zero elements equals zero.)”. So when N is 0 for an empty set, val(A, S) = 0. 

Problem Interpretation

Using the given example, the question is, what is the minimum absolute sum of a given set of numbers, with all the different possible combinations of negative and positive signs, for the numbers. From above, the given set is the A = [1, 5, 2, -2]. Now {−1, 1, −1, 1} is one set of positive and negative signs. {1, 1, 1, 1} is another set of positive (and negative signs/zero-negative). {−1, -1, −1, -1} is yet another set of (positive and) negative signs.

If the set of signs is {−1, 1, −1, 1}, then the absolute minimum sum is |-1 + 5 – 2 – 2| = |0| = 0. If the set of signs is {1, 1, 1, 1}, then the absolute minimum sum is |1 + 5 + 2 – 2| = |+6| = 6. If the set of signs is {-1, -1, 1, -1}, then the absolute minimum sum is |-1 - 5 + 2 + 2| = |-2| = 2. 

Illustration

The given example is used for illustration. Let the + sign of +1 be represented by the bit (Binary Digit) of 1. Let the negative sign of -1 be represented by the bit (Binary Digit) of 0. So the set {−1, 1, −1, 1} becomes the binary number 0101 which is the decimal number 5₁₀. The set {1, 1, 1, 1}} is the binary number 1111 which is the decimal number 15₁₀. The set {-1, -1, 1, -1} is the binary number 0010 which is the decimal number 2₁₀.    

So the different decimal values for k are 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15. In binary, these numbers are: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, with each considered from the right end. If there are N elements in the given set, then there are N (or N+1 which includes the empty set) sets, consisting of 1’s and/or 0’s – see table below. Remember that each value for k represents a sub-task. The different possible sub-task results, are actually from the different combinations of k and the indexes from 0 to N. Each combination has a result. dp stands for dynamic programming. 

So, 0₁₀ means - , considered as - - - -. 1₁₀ means + , considered as - - - +. 2₁₀ means +,- , considered as - - + -. 3₁₀ means +,+ , considered as - - + +. 4₁₀ means +,-,- considered as - + - -. 8₁₀ means +,-,-,- , considered as + - - -; and so on.

Different Examples

Well, the following tables show the results for different sets: 

The given set is {1, 5, 2, -2}.

For the set {1, 5, 2, -2}, the minimum abs(sum) of 0 is obtained at index 5 with -1,+1,-1,+1 (0101) or at index 10 with +1,-1,+1,-1 (1010).

The given set is {1, -4, 2}.

For the set {1, -4, 2}, the minimum abs(sum) of 1 is obtained at index 0 with -1,-1,-1 (000) or at index 7 with +1,+1,+1 (111). 

The given set is {2, -5}.

For the set {2, -5}, the minimum abs(sum) of 3 is obtained at index 0 with -1,-1, (00) or at index 3 with +1,+1 (11).

The given set is {6}.

For the set {6}, the minimum abs(sum) of 6 is obtained at index 0 with -1 (0) or at index 1 with +1 (1).

The Program

In the code, conversion of the index k from base 10 to base 2 is used. 

The pow() function for power is in the math library. So the math.h header has to be included. To evaluate 2^N, do

    ret = pow(2, N) 

The abs() function for absolute, is in the cstdlib library. So the cstdlib header has to be included.

The assumptions in the program description are:

·         N is an integer within the range [0..20,000];

·         each element of array A is an integer within the range [−100..100]. 

So the minimum absolute sum cannot exceed 20000 * 100 + 1 = 2000001 (could still be 2000000)

The program is (read the comments as well): 

<?php
    function solution($A) {
        $N = count($A);
        $pw = pow(2,$N);
        $minAbsSum = 20000 * 100 + 1;

        if ($N==0) return 0;
    
        //code for binary content
        for ($k=0; $k < $pw; $k++) {    //converting each number in the range K, to base 2 number
            $no = $k;                 //as well as looking for minimum |sum{ A[i]*S[i] for i = 0..N−1 }|
            $j = $N-1;
            $sum = 0;
            while ($j >= 0) {    //the number bits
                $remainder = $no % 2;
                if ($remainder == 0)
                    $sum = $sum + (-1 * $A[$j]);
                if ($remainder == 1)
                    $sum = $sum + (+1 * $A[$j]);   

                if ($j == 0) 
                    break;
            
                $no = (int)($no / 2);    //integer division
                $j--;
            }

            $sum = abs($sum);

            if ($sum < $minAbsSum)
                $minAbsSum = $sum;
        }

        return $minAbsSum;
    }

    $A = [1, 5, 2, -2];
    $ret1 = solution($A);
    echo $ret1 . "\n";

    $B = [1, -4, 2];
    $ret2 = solution($B);
    echo $ret2 . "\n";

    $C = [2, -5];
    $ret3 = solution($C);
    echo $ret3 . "\n";
    
    $D = [6];
    $ret4 = solution($D);
    echo $ret4 . "\n";

    $E = [10, 20, 30, 5];
    $ret5 = solution($E);
    echo $ret5 . "\n";

    $F = [];
    $ret6 = solution($F);
    echo $ret6 . "\n";
?>

Output is: 

At app.codility.com/programmers the scoring for this solution(), using the particular test cases at app.codility.com/programmers, is:

    Task score : 54% -  Correctness : 100% ; Performance : 0%

Analysis summary 

Example tests

Correctness tests

 Performance tests

Conclusion

The author believes that all the answers on performance by the examiner are wrong assessments, for the following reasons: 

-          No timing complaint has been made. In fact, the timings for some of them are OK.

-          Take for example, the case of medium2. The examiner's expected answer is 5 (got 2000001) and the author's equivalent answer is also 5, for his program above.

-          All the examiner's answers have "got 2000001". Does that make sense?

So the scoring for the author should have been: 

    Task score : 100% -  Correctness : 100% ; Performance : 100%

Thanks for reading