Lesson 99: ArrayInversionCount (Array Inversion Count)

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

ぎりぎりのところまで行ったのですが、友達と食事の時間がせまってたので、食事中に考えてフラストレーションがたまったりしないようにググってしまいました。

おそらく、ソートに関する問題でマージソート絡みだろうという直感はあったのですが、最後の１ピースが埋まらずorz

問題は結局自分でマージソート書けばいいのですよね。マージソートを「並列でやらないときは」、両行くの先頭からやっていけば、Q<R とA[Q] > A[R]の判定がソート中に出来ますと言う話でした。

なんか、カチンときたのもあり、皆再帰を使ってるのでループでやっておきました。

で、100%のスコアです。とりあえず、 if (A[lpos] <= A[rpos])で最初＜にしてしまってつまらないバグを出してしまいましたorz

#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

これは簡単な問題ですね。文字列を両端からスキャンして、文字を比較し、
両方のスキャンのポジションが重なったら、そこが答えです。

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

最初のバージョンはこれです。１００％もらえましたね。

ちょっとなぜこの問題の計算量がO(log(N))とされているのか悩みました。'int'はcordialityの環境では３２ビットなので。

おそらく、ループをそれ以上のbinary gapがない時には打ち切って良いのでlog(N)と言ってるのかなと思います。

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

で、こちらが途中でループを打ち切るバージョンです。

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

そして、より短い版です。


























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

最初、本当にO(1)のメモリ使用量でできるのかちょっと悩みましたが、良く問題を読むと、ペアにならないで残される要素は１つだけなんですね。

ですから、xorをざっと先頭からやっていけば、最後に残ったのがペアになっていない数です　（A xor A = 0, and B xor 0 = Bですから）。

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

単純に再帰でツリーを辿って行けば良いだけですね。

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

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

Lesson 15: NumberSolitaire (Number Solitaire)

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

似たような問題は既にやっていますね。Lesson 11:FibFrogです。
実際、自分としては、なぜLesson 15でやることになっているdynamic programmingがここにでて来ているのか、不思議におもっていました。
http://codility-lessons.blogspot.tw/2015/03/lesson-11-fibfrog-fib-frog.html


とにかく、やるべきことは殆どFibFrogの問題と殆どおなじですね。

今回は配列max_val[]を用意し、とりあえずINT_MINでクリアしましょう。これは問題で可能な範囲の一番小さい数字よりも小さいものです。ただmax_val[0]だけはスタート地点になりますので、A[0]を代入しておきます。

そして、これから配列を順番に先頭からみていきます。

スタート地点から順に、現在の位置のmax_val[]と、 飛ぶ事が可能な場所のA[]の要素をたし（点数をたし）、それが、その該当位置のmax_val[]の要素より大きければ、値を更新します。

これをN-2のポジションまで繰り返せば、N-1のポジションで得られる最大の値がわかることになりますね。

これで１００％のスコアになります。

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