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

Lesson 13: CountDistinctSlices (Count Distinct Slices)

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

As every time we extend the range, all the possible length of the slices before extension will have one more move and one new slice, the length of which is the same as the extended range, can be added.

This guy has a good implementation for the problem and I simply applied his strategy in my C version.
https://github.com/acprimer/Codility/blob/master/src/Lesson13/CountDistinctSlices.java

The code gives the 100% score.

#include <alloca.h> #include <memory.h> int solution(int M, int A[], int N) {      int memsize = sizeof(int) * (M + 1);      int*found = (int*)alloca(memsize);      memset(found, 0xFF, memsize);      
    int r = 0;      int l = -1;      
    int cnt = 0;

    for ( ; r < N; r++){    
        if (found[A[r]] > l){ 
            l = found[A[r]];
        }

        cnt += r - l;
        
        found[A[r]] = r;
        if (cnt > 1000000000){
            return 1000000000;
        }
    }      
    return cnt; }







I was also struggling with an alternative solution below. I made some bug due to overflow... I think for this kind of the coding problem, it is better to use the languages with the big-integer type...

In this code, when we found the number we have already marked, first we compute the number of distinct slices until the point and then subtract the number of distinct slices that will appear again in the next round so to avoid count them twice.

As the code can overflow depending on the range of (l,r), we typecast them to 'long long' when computing.

This solution gives also the 100% score. 

#include <alloca.h> #include <memory.h> int solution(int M, int A[], int N) {      int memsize = sizeof(int) * (M + 1);      int* found = (int*)alloca(memsize);      //this initialize the array with -1.      memset(found, 0xFF, memsize);      
    int r = 0;      int l = 0;      
    int cnt = 0;      
    for ( ; r < N; r++){          if (found[A[r]] == -1){
            found[A[r]] = r;
            continue;
        }
     
        //to avoid overflow, we use long long here...
        long long all = ((long long)r - l) * (r - l + 1) / 2;
        long long tmp = (long long)r - (found[A[r]] + 1);
        long long sub = tmp * (tmp + 1) / 2;
         
        //to avoid overflow...
        if (all - sub >= 1000000000){
            return 1000000000;
        }
        
        cnt += all - sub;
        if (cnt >= 1000000000){
            return 1000000000;
        }
        while (l <= found[A[r]]){
            found[A[l]] = -1;
            l++;
        }
        found[A[r]] = r;
    }      
    //to avoid overflow      long long rest = ((long long)r - l) * (r - l + 1) / 2;      if (rest > 1000000000){          return 1000000000; 
    }      
    cnt += rest;      
    return cnt > 1000000000 ? 1000000000 : cnt; }



The above code can further be simplified as below.
This also gives the 100% score.

#include <alloca.h> #include <memory.h> int solution(int M, int A[], int N) { int memsize = sizeof(int) * (M + 1); int* found = (int*)alloca(memsize); //this initialize the array with -1. memset(found, 0xFF, memsize); int r = 0; int l = 0; int cnt = 0; for ( ; r < N; r++){ if (found[A[r]] < l){ found[A[r]] = r; continue; } //to avoid overflow, we use long long here... long long all = ((long long)r - l) * (r - l + 1) / 2; long long tmp = (long long)r - (found[A[r]] + 1); long long sub = tmp * (tmp + 1) / 2; //to avoid overflow... if (all - sub >= 1000000000){ return 1000000000; } cnt += all - sub; if (cnt >= 1000000000){ return 1000000000; } l = found[A[r]] + 1; found[A[r]] = r; } //to avoid overflow long long rest = ((long long)r - l) * (r - l + 1) / 2; if (rest > 1000000000){ return 1000000000; } cnt += rest; return cnt > 1000000000 ? 1000000000 : cnt; }