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