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

Lesson 14: TieRopes (Tie Ropes)

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

最初問題を勘違いしておりまして、長さ>=Kになったようなロープは取り除けるのだとおもってましたが、そうではなく、ずっと列に残るのですね。

ということは、これは簡単にgreedy algorithmがロープを結ぶのに使えるということです。

こう考えてみましょう。いま、現在で最大の数の長さ>=Kというようなロープが出来ています。で、間にいろいろと使われなかったロープが残っているとしますね。この使われなかったロープを先頭から右にあるロープに順々に結んでいっても、既にある最大の数の長さ>=Kのロープの数はかわらないですよね。長くなるだけで。もし増えちゃったら、最初の課程がまちがってるってとになります。（となりのロープとしか結べないのを忘れないようにしましょう！）

なので、左から右に先頭から順につなげて行って長さkを超えたら一本できたと考えて、次のロープを作って行けばいいんですね。

これで１００％の解答になります。

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

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

セグメントの右端でソートされているため、greedy algorithmで先頭から取って行けばOKです。　まず最初のセグメントをとって１とし、その次のオーバラッピングしてないセグメントを見つけたらそれをカウントします。それを繰り返します。

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

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

まず、配列をソートします。

この配列から三角形を探して行くのですが、ソートしたのでA[P] + A[Q] > A[R]だけをチェックすればいいことになります。なぜならつねに A[P] <= A[Q] <= A[R]となるので、 A[P] < A[Q] + A[R] と A[R] + A[P] > A[Q] はつねになりたちますね。

まずPの位置を決め、その次に隣にQ、その隣にRの状態にします。A[P] + A[Q] > A[R]  が成り立つあいだはRを右にスライドさせます。１回スライドするたびに(R - Q) 個の新しいコンビネーションが見つかることになりますね。Rの位置を固定して、Qの位置だけ変わるとすると(R-Q)個のQとRの組み合わせがみつかるということになるからですね。　 

もしRがこれ以上スライドできなくなった場合（上の条件が成り立たない場合）、こんどはQを一個動かしてみます。Qが大きくなったのでRが動かせるかもしれないからですね。もしQ==Rになった場合は、Rが重ならないように右にさらに一つ動かされます。

これを全てのかのうなPの位置に対して繰り返せばいいわけですね。

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

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: MinAbsSumTwo (Min Abs Sum Two)

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

まず配列を昇順にソートします。この時点で最大値が０か負だったり最小値が０か正だった場合は、答えはもうでていますね。

そうでなければ２つのカーソルをつかって配列をチェックしていきましょう。左から右へとすすむものと、右から左へと進むものの 、それぞれlとrと名付けましょう。

もし、lの位置の値がまだ負で絶対値が右のもののより大きければ、lを左へ、逆に右の絶対値が大きければrを左へ、同じならば両方を動かしましょう。

もしlの位置の値が０以上に なったらば、そこで探索をやめることができます。

以下のコードで１００％のスコアになります。

#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

範囲を右に拡大するたびに、拡大前にあった長さのスライスは全てもう一回右にうごかせる＝スライスが増えることになります。また、範囲が広がったことにより、その長さのスライスも追加できますね。

ということはで、一つ範囲を広げるごとに、現在の長さ分のスライスが増えるということになります。

下記のリンクの人の実装が非常によかったので、そのままCにうつしました。

https://github.com/acprimer/Codility/blob/master/src/Lesson13/CountDistinctSlices.java

これで１００％のスコアです

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




他の解法も実は頑張ってやっていたのですが、オーバーフローのバグで間違った答えがでて、気づかず四苦八苦していました。こういったコーディングの問題は、面接とかでは迷わずbig integerのある言語を使うべきですね。

下のコードではまず、既にマークした数字にであったら、とりあえずその範囲までに可能なdistinct sliceの数を全て計算し、その後、次のラウンドに再度出て来てしまうスライスの数を計算して、それを引いています。二重にカウントすると答えが間違ったものになってしまいますからね。

このコードはlとrの幅に依拠しているので、そこで余りに大きい数で計算することになると、オーバーフローしてしまうためlong longで計算しています。

このコードも100%のスコアが得られます。

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




上のコードは実はさらに簡単にできます。最初のコードと同じようにlの位置でそれまでにみつかったかどうか判定すれば、フラグをいちいちクリアする必要はないですね。

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

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