Lesson 99: ArrayInversionCount (Array Inversion Count)

Lesson 99: ArrayInversionCount
https://codility.com/programmers/lessons/14

I almost solved the problem, but I had to go out to dinner with my friends that day. So I googled so to not be frustrated during the dinner.

I had some intuition that this is about sorting, and possibly about heap-sort, but I didn't have the time to finish the last mile.

The problem I had is to fill this gap; this one is about sorting, and this is about merge-sort. If you don't parallelize merge sort and do it from the head of the data-area, you can easily check Q <R and A[Q] > A[R].

As I cheated by googling this time, I imposed myself to not use recursion for merge-sort.

Here is my answer that gives the 100% score. (Note that it is  'if (A[lpos] <= A[rpos])' as the problem A[Q] > A[R]').

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



int solution(int A[], int N) 
{
    int cnt = 0;
    int memsize = sizeof(int) * N;
    int*work    = (int*)alloca(memsize);
    
    
    for (int blksize = 1; blksize < N; blksize *= 2){
        
        int lpos = 0;
        int rpos = blksize;

        //merge each blocks
        while(lpos <= N){
            int writebackpos = lpos;
            
            int lend = lpos + blksize;
            lend = lend >= N ? N : lend;
            
                        
            int rend = rpos + blksize;
            rend = rend >= N ? N : rend;

            //merge
            int wpos = 0;
            while (lpos < lend && rpos < rend){
                if (A[lpos] <= A[rpos]){
                    work[wpos++] = A[lpos++];
                }
                else {
                    work[wpos++] = A[rpos++];
                    cnt += lend - lpos;
                    if (cnt >=  1000000000){
                        return - 1;
                    }
                }
            }
            
            while (lpos < lend){
                work[wpos++] = A[lpos++];
            }

            while (rpos < rend){
                work[wpos++] = A[rpos++];
            }

            //write back
            memcpy(A + writebackpos, work, sizeof(int) * wpos);

            //proceed to the next block
            lpos = rpos;
            rpos = lpos + blksize;
        }

    }
   
    return cnt;
}

Lesson 99: StrSymmetryPoint (Str Symmetry Point)

Lesson 99: StrSymmetryPoint (Str Symmetry Point)
https://codility.com/programmers/lessons/14

This is a simple problem. We only scan from both ends.
If the scanning positions reached the same position, that's the
answer.

int solution(char *S) { int len = strlen(S); if (len % 2 == 0){ return -1; } int l = 0; int r = len - 1; while (l < r){ if (S[l] != S[r]){ return -1; } l++; r--; } return l; }

Lesson 99: BinaryGap (Binary Gap)

Lesson 99: BinaryGap
https://codility.com/programmers/lessons/14

Here is my first solution. It gives the 100% score.

I was wondering why the expected worst time complexity of this problem is O(log(N)). as 'int' is always 32 bit in this environment.

Yet, I guess it is because we can terminate the loop when there is no more binary gap can be found.

int solution(int N) 
{
    int max = 0;
    
    int mask = 0x80000000;

    int i = 0;

    //find the first 1.
    for (   ; i < sizeof(int) * 8; i++){
        int tmp = (N << i) & mask;
        if (tmp != 0){
            break;
        }
    }
    
    //no 1 found.
    if (i == sizeof(int) * 8){
        return 0;
    }
    
    //let's seek for the binary gap
    int cnt = 0;
    for (i = i +1; i < sizeof(int) * 8; i++){
        int tmp = (N << i) & mask;
        if (tmp == 0){
            cnt++;    
        }
        else {
            max = max < cnt ? cnt : max; 
            cnt = 0;
        }
    }
       
    return max;
}

And here is the version to terminate the loop when there is no more binary gap. This is the O(log(N)) version.

int solution(int N) 
{
    int max = 0;
    
    int i = 0;

    //find the first 1.
    for (   ; i < sizeof(int) * 8; i++){
        int tmp = (N >> i) & 1;
        if (tmp != 0){
            break;
        }
    }
    
    //no 1 found.
    if (i == sizeof(int) * 8){
        return 0;
    }
    
    //let's seek for the binary gap
    int cnt = 0;
    for (i = i +1; i < sizeof(int) * 8; i++){
        int tmp = (N >> i);
        if (tmp == 0){
            break;
        }
        
        tmp = tmp & 1;
        if (tmp == 0){
            cnt++;    
        }
        else {
            max = max < cnt ? cnt : max; 
            cnt = 0;
        }
    }
       
    return max;
}

And here is a shorter version.

int solution(int N) {
    
    int max = 0;
    int flg = 0;
    int cnt = 0;
    
    while (N > 0){
        if (N & 1 == 1){
            if (flg == 0){
                flg = 1;
            }
            else {
                max = max < cnt ? cnt : max;
            }
            cnt = 0;
        }
        else {
            cnt++;
        }
        N = N >> 1;
    }
    
    return max;
}

Lesson 99: OddOccurrencesInArray (Odd OccurrencesInArray)

Lesson 99:  OddOccurrencesInArray
https://codility.com/programmers/lessons/14

First, I thought how I can do this in the O(1) space complexity until I notice that there is only one element left unpaired in this problem.

If all the elements except one is paired, we can use xor for this problem and just one scanning is okay. Since A xor A = 0, and B xor 0 = B, if we keep on performing xor for all the values, the one left after iteration is the value unpaired.

int solution(int A[], int N) {
    
    int val = 0;
    for (int i = 0; i < N; i++){
        val ^= A[i];
    }
    
    return val;

}

Lesson 99: TreeHeight (Tree Height)

Lesson 99: TreeHeight
https://codility.com/programmers/lessons/14

We simply have to traverse the array by recursion.

void traverse(struct tree * T, int depth, int*max)
{
    if (depth > *max){
        *max = depth;    
    }
    
    if (T->l != NULL){
        traverse(T->l, depth + 1, max);
    }
    
    if (T->r != NULL){
        traverse(T->r, depth + 1, max);
    }
    
    return;
}

int solution(struct tree * T) 
{
    //handle an empty tree here.
    if (T == NULL){
        return - 1;
    }
    
    int max = 0;
    
    traverse(T, 0, &max);
    
    return max;
}

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

Lesson 15: NumberSolitaire (Number Solitaire)

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

We already have solved a similar problem, Lesson 11:FibFrog.
Indeed, I was wondering why we have to use the dynamic programming concept  for this problem as it is scheduled in Lesson 15
http://codility-lessons.blogspot.tw/2015/03/lesson-11-fibfrog-fib-frog.html

Anyway, what we do is the almost the same as in the FibFrog problem. 
We prepare the array max_val[] and then initialize it with INT_MIN, which is smaller than the possible minimum value in the given conditions, except max_val[0], which is set the initial point we get when we start at A[0].

We begin from the position 0 and take the value at max_val[0]. Then, we add this point with the points we can obtain at each cell we can reach by the next jump and update the maximum value if it is larger than one that we obtained so far at the cell.

We repeat this until the cell we can perform the last jump (at the position N - 2, right before the goal).


This strategy gives the 100% score as below.

#include <alloca.h>
#include <limits.h>

int solution(int A[], int N) 
{
    int  memsize = sizeof(int) * N;
    int* max_val = (int*)alloca(memsize);
    
    //initialize the each cell with INT_MIN except the first one.
    max_val[0] = A[0];
    for (int i = 1; i < N; i++){
        max_val[i] = INT_MIN;
    }    
    
    //do dynamic programming for jump
    for (int pos = 0; pos < N - 1; pos++){
        
        //throw the dice (1-6)
        for (int j = 1; j <= 6; j++){
            //if out of range, neglect.
            int jump_pos = pos + j;
            
            //not to jump out of the range.
            if (jump_pos >= N){
                continue;
            }
            
            //update each cell's max value.
            int tmp = A[pos + j] + max_val[pos];
            max_val[jump_pos] = max_val[jump_pos] < tmp ? tmp : max_val[jump_pos];
        }
    }
    
    return max_val[N - 1];
}

Lesson 14: TieRopes (Tie Ropes)

Lesson 14: TieRopes 
https://codility.com/programmers/lessons/15

First, it had some time to think over the solution because I had some misunderstanding about the problem. Even when a rope became >= k, it can not be removed and remains in the same order even after being tied.(We can't remove the tied ropes even when they qualify the condition: length >= k.)

This suggests that we can use a greedy algorithm to tie ropes from the beginning.

Assume that we have the maximum number of ropes that is longer or equal to K and some ropes that is shorter than K are left untied now. Even when these ropes are tied to the ropes that is >= k on the right hand side won't increase the maximum number we already have; if not this contradicts the first assumption that we have the maximum number of the ropes (the length k >=0) already.

This strategy gives the 100% score as below.

int solution(int K, int A[], int N) 
{
    int cnt = 0;
    
    int current = 0;

    int i;
    for (i = 0; i < N; i++){
        current += A[i];
        if (current >= K){
            cnt++;
            current = 0;
        }
    }
    
    return cnt;
}

Lesson 14: MaxNonoverlappingSegments (Max Non-overlapping Segments)

Lesson 14: MaxNonoverlappingSegments (Max Non-overlapping Segments)
https://codility.com/programmers/lessons/15

As the segments are sorted in ascending order by their ends, we can use a greedy algorithm. First, we take the segment at the head, count it. Then we skip until the next non overlapping segment. 

This gives the 100% score.

int solution(int A[], int B[], int N) 
{
    //if N <= 1, we know the answer already.
    if (N <= 1){
        return N;
    }
    
    int cnt = 1;
    int prev_end = B[0];
    
    int curr;
    for (curr = 1; curr < N; curr++){
        if (A[curr] > prev_end){
            cnt++;
            prev_end = B[curr];
        }
    }
    
    return cnt;
}

Lesson 13: CountTriangles (Count Triangles)

Lesson 13: CountTriangles

https://codility.com/programmers/lessons/13

First we sort the given array. 

If we search the triangles from this sorted array, we only have to check if A[P] + A[Q] > A[R], because it is always A[P] <= A[Q] <= A[R]. A[P] < A[Q] + A[R] and A[R] + A[P] > A[Q] are always hold.

We check P from the beginning. When we check P, first we set Q just to the next to P, and R to the next to Q. We can slide R while A[P] + A[Q] > A[R] is hold and every time we slide R, we can have (R - Q) combinations for (P, Q, R).　(Why? suppose you have a certain location of R, then Q can be any place between P and R, since Q is just getting larger and this does not invalidate A[P] + A[Q] > A[R]).

If we can not slide R anymore, then we slide Q to the next position. If it becomes Q==R, then slide R again.

This gives the 100% score as below.

int compare_int(const void *a, const void *b)
{
   //don't do 'return *(int*)a - *(int*)b;',
   //as this can cause underflow or overflow.

   if (*(int*)a == *(int*)b){
       return 0;
   }

   if (*(int*)a < *(int*)b){
       return -1;
   }
   
   return 1;
}

int solution(int A[], int N) 
{
    qsort(A, N, sizeof(int), compare_int);

    int cnt = 0;
    
    int p, q, r, ap, aq, ar;

    p = 0;
        
    for (   ; p <= N - 3; p++){
        ap = A[p];
        
        q = p + 1;
        r = p + 2;

        while (r < N){
            aq = A[q];
            ar = A[r];
            
            if (ap + aq > ar){
                cnt += r - q;
                r++;
            }
            else {
                q++;
                if (r == q){
                    r++;
                }
            }
        }

    }
    
    return cnt;
}

Lesson 13: MinAbsSumOfTwo (Min Abs Sum Of Two)

Lesson 13: MinAbsSumTwo
https://codility.com/programmers/lessons/13

First, we sort the array in ascending order.

If the maximum value is negative or zero or if the minimum value is positive or zero, we already have the answer. 

If not, then use two cursors to check the values in the array, one of which move from left to right and other moves from right to left. We name them 'l' and 'r' respectively.

If the value at the position 'l' is still negative and its absolute value is bigger than the other end we move 'l' to the next position. If the absolute value at the position 'r' is bigger, then move the 'r' to the next position. If the absolute values of these two are equal, then move both.

If the value at the position l is larger than or equal to zero, we can terminate the search just there.

#include <alloca.h> #include <memory.h> #include <math.h> int compare_int(const void *a, const void *b) { //don't do 'return *(int*)a - *(int*)b;', //as it can cause underflow or overflow. if (*(int*)a == *(int*)b){ return 0; } if (*(int*)a < *(int*)b){ return -1; } return 1; } int solution(int A[], int N) { //first we sort in the ascending order qsort(A, N, sizeof(int), compare_int); int l = 0; int r = N - 1; //the initial value for the min int min = abs(A[0] + A[0]); while(l <= r){ int lval = abs(A[l] * 2); int rval = abs(A[r] * 2); int both = abs(A[l] + A[r]); //update the min value if (lval < min){ min = lval; } if (rval < min){ min = rval; } if (both < min){ min = both; } //we A[l] >=0, we have the smallest number already. if (A[l] >= 0){ break; } //move the positions. if (lval < rval){ r--; } else if (lval > rval){ l++; } else { r--; l++; } } return min; }