Lesson 4: MaxProductOfThree (Max Product of Three)

これはちょっとしたトリックでO(N)で解ける問題です。ソートしなくても良いのです。

３つの値を選んだとき、全て正の値なら当然大きいもの３つをかければいいのですが、ここで負の数が二つあった時の事を考えてみてください。そうすると負x負は正になりますね。

そう考えると大きい方から値３つと　小さいから値２つと最大の値１つ、それぞれの積が大きい方を選べば一番大きい値が得られます。

この為にはソートしないでも一回だけ配列をスキャンすればいいですね。

--------------------------------
SOLUTION
--------------------------------
int solution(int A[], int N) 
{
    if (N == 3){
        return A[0] * A[1] * A[2];
    }
    int max1 = -1001;  
    int max2 = -1001;    
    int max3 = -1001;   
    
    int min1 = 1001;   
    int min2 = 1001;      
    int i;        
    for (i = 0; i < N; i++){
        int tmp = A[i];
        if (tmp > max1){
            max3 = max2;
            max2 = max1;
            max1 = tmp;
        }     
        else if (tmp > max2){
            max3 = max2;
            max2 = tmp;
        }         
        else if (tmp > max3){
            max3 = tmp;
        }
        
        if (tmp < min1){  
            min2 = min1;   
            min1 = tmp;    
        }      
        else if (tmp < min2){
            min2 = tmp;
        }   
    }        
    
    int val1 = max1 * max2 * max3;    
    int val2 = max1 * min1 * min2;  
    
    return val1 > val2 ? val1 : val2;
}

Lesson 4: Distinct (Distinct)

簡単な問題です。

まずソートして、それから先頭から配列をスキャン。前の要素と違う要素にあたったら、カウンターを増やす。

多分、N == 0の時とかのチェックし忘れでバグになることがあるのではと。

int comparator(const void *a, const void *b)
{
    if (*(int*)a == *(int*)b){
        return 0;
    }
    
    if (*(int*)a < *(int*)b){
        return -1;
    }
    
    
    return 1;
}

int solution(int A[], int N) 
{
    if (N == 0){
        return 0;
    }
    
    qsort(A, N, sizeof(int), comparator);
    
    int cnt = 1;
    
    int i;    
    for (i = 1; i < N; i++){
        if (A[i - 1] != A[i]){
            cnt++;
        }
    }
    
    return cnt;
}

Lesson 4: Triangle (Triangle)

これも算数の問題ですね。

まず、配列を昇順にソートしましょう。
すると、かならず0 <= P < Q < R < Nにたいしては、A[P] <= A[Q] <= A[R]となりますね。

とりあえず、全部正の整数０以上の整数と考えましょう。
(0 <  A[P] <=  A[Q] <= A[R]).

ソートされているので、以下の事が言えます。

条件 'A[P] < A[Q] + A[R]' は常に成り立つ。
条件 'A[Q] < A[P] + A[R]' も常に成り立つ。
（A[R]は既に、A[P]、A[Q]よりも大きいですから、正の数を足しても大きいままですね）

ですから条件'A[R] < A[P] + A[Q]'だけをチェックすればいいのですね。
一つでも条件全てにあうtriangularなものがあるかないかを、１か０で返せという問題ですから、あるA[R]にたいして一番大きいA[P] + A[Q]だけを調べればいいということです。（そうすれば全ての条件が成り立つものがあるということになり１を返せば良い）
ということは、連続する３つのスロットをそれぞれA[P]、A[Q]、A[R]として調べればいいですね。

またもとにもどって、なぜ、０以下の値を無視していいのかを考えましょう。

もし、 A[P] <= 0 <= A[Q] <= A[R]であったら、A[P] + A[Q] <= A[Q]になりますね。そうすると’A[P] + A[Q] <= A[Q] <= A[R]’になりますので、条件’A[R] < A[P] + A[Q]’は成り立たなくなります。ですからすべて０以下になるようなPは全て無視していいのです。

この方針で100%のスコアになります。O(N log (N))の時間的な計算量を指定されているので、マージ・ソートなどを使う方が確実ですが（クイック・ソートの最悪実行時間はこれより大きい）、Cにはマージ・ソートのライブラリが標準でないので、qsortを使っています。

また、qsort用の比較関数で’return *(int*)a - *(int*)b;’とやってしまうと、アンダーフローして間違った比較がなされる事があります。同様に'r < p + q' として比較してしまうと、p　+　qがオーバーフローしてしまうので’r - p < q ’と書き換えて比較しましょう。（この辺で１００％でなかったのでハマってました…orz)

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) 
{
    if (N < 3){
        return 0;
    }
    
    qsort(A, N, sizeof(int), compare_int);
    
    int i;
    for (i = 2; i < N; i++){
        
        int p = A[i - 2];
        int q = A[i - 1];
        int r = A[i];
        
        //neglect negative values.
        if (p <= 0){
            continue;
        }

        //if write like 'r < p + q', 'p + q' may overflow.
        if (r - p < q ){
            return 1;
        }
    }
    
    return 0;
}

Lesson 3: CountDiv (Count Div)

https://codility.com/programmers/lessons/3
Lesson 3: CountDivの解答がこちらになります。

これも算数の問題ですね。

上の図のようになりますので

A % K == 0 なら (B - A) / K + 1
A % K != 0 なら (B - (A - A % K)) / K

が答えです。

----------------------------------------
SOLUTION
----------------------------------------
int solution(int A, int B, int K) 
{
    if (A % K == 0){
        return (B - A) / K + 1;
    }

    return (B - (A - A % K)) / K;
}

Lesson 3: MinAvgTwoSlice (Min Avg Two Slice)

https://codility.com/programmers/lessons/3
Lesson 3: MinAvgTwoSliceの解答がこちらになります。

基本、数学の問題だそうです。

Codilityの例題PDFにかかれたprefix sumのアルゴリズムの工夫だけでとけるのかな？と思って、ずっと考えてたのですがどうやら違いそうだという事でググってしまいました。

とりあえず下に色々みてわかった簡単な説明を。

まず、一番小さい平均を出す連続した配列のスロットは２つか３つのスロットを見ればわかるということです。

例えば、４つの大きさの連続した配列のスロットが一番小さい平均を出すと仮定してみましょう。これは２＋２の二つに分割できますよね。そうすると、前者か後者の２の平均がもし、全体の４つの平均より小さかった場合、仮定に反しますね。もし、大きかったらどうなるでしょう？もう一方のペアのほうの平均がもとの４つの平均より小さくなりますね。だから、２＋２に分割しても同じなのです。これは例えば５つのスロットを２＋３に分解しても同じ事です。

もっと一般化できますよね。適当なサイズの連続した配列のスロット中の値の平均が一番小さいと仮定した場合、先頭部分から２つか３つのペアをとってそれより小さいものが出来ると、最初の仮定に違反します。どちらにしろ、同じ平均を出せる部分が切り出せるということになりますから、２つか３つの平均だけを先頭から見て言って、一番小さいもので最初に現れた部分のインデックスを返せば良いという事です

これで１００％とれました。

int solution(int A[], int N) 
{
    int i = 0;
    
    if (N == 2){
        return 0;
    }

    //initialize the current minimum average of the first two slots.
    double minavg = (A[0] + A[1]) / 2.0;
    int idx = 0;
    

    for (i = 2; i < N; i++){
        double tmp1 = (A[i - 1] + A[i]) / 2.0;
        double tmp2 = (A[i - 2] + A[i - 1] + A[i]) / 3.0;
        
        if (tmp1 < minavg){
            idx = i - 1;
            minavg = tmp1;
        }
        if (tmp2 < minavg){
            idx = i - 2;
            minavg = tmp2;
        }
    }
    return idx;
}

Lesson 3: GenomicRangeQuery (Genomic Range Query)

https://codility.com/programmers/lessons/3
Lesson 3:  GenomicRangeQueryの解答がこちらになります。

また、別の「running total」の問題です。

やり方としては、一度文字列Sをスキャンしますが、その間に、ある位置でそれまでに出現したACGTのそれぞれの数を数えておきます。

そうした場合、ある位置pでACGTのそれぞれの今までのトータルが[4,2,3,1]であり、ある位置qでは[4,5,5,1](p <= qとします）、AとTのカウントは増えてないので、pとqの間には存在しないと言えます。逆にCとGのカウントは増えていますから、存在したと言えます。

下のサンプルのように、このやり方で１００％のスコアがでますね。

--------------------------------
SOLUTION
--------------------------------
struct Results solution(char *S, int P[], int Q[], int M) 
{
    typedef struct ACGT {
        int a;
        int c;
        int g;
        int t;
    } ACGT;
    
    int N = strlen(S);
    ACGT* acgt = calloc(sizeof(ACGT), (N + 1));
    
    int i;
    int a = 0;
    int c = 0;
    int g = 0;
    int t = 0;

    //count the numbers of ACGT. 
    for (i = 0; i < N; i++){
        switch(S[i]){
            case 'A':
                a++;
                break;
            case 'C':
                c++;
                break;
            case 'G':
                g++;
                break;
            case 'T':
                t++;
                break;
            default:
                exit(-1);
        }
        //we leave acgt[0] untouched (filled with zero)
        //so that we can simplify the next step.
        acgt[i + 1].a = a;
        acgt[i + 1].c = c;
        acgt[i + 1].g = g;
        acgt[i + 1].t = t;
    }
    
    
    struct Results result;
    
    result.A = calloc(sizeof(int), M);
    result.M = M;
    
    for (i = 0; i < M; i++){
        ACGT s = acgt[P[i]];
        ACGT e = acgt[Q[i] + 1];
        if (e.a - s.a > 0){
            result.A[i] = 1;
        }
        else if (e.c - s.c > 0){
            result.A[i] = 2;
        }
        else if (e.g - s.g > 0){
            result.A[i] = 3;
        }
        else {
            result.A[i] = 4;
        }
    }
    
    
    free(acgt);
    
    return result;
}

Lesson 3: PassingCars (Passing Cars)

https://codility.com/programmers/lessons/3
Lesson 3: Passing Carsの答えがこちらになります。

西に進んでいる車は、反対側からくる東にすすんでいる車の全てにあうことになります。

ですから、東に進んでいる車の数を数えつつ、配列を調べていき、東に進んでいる来るまであれば、「東に進んでいる車のカウンタ」を一つ増やします。

西に進んでいる車があったら、「すれ違う車のカウンタ」に、「東に進んでいる車のカウンタ」を足せばよいのです。

で、忘れ易いのが1,000,000,000以上カウントが増えたら-1を返せという仕様ですね。
codilityの環境はintの範囲内の値なので、カウンタその他はint型でいいですね。

この方針で１００％がでます。

int solution(int A[], int N) 
{
    int cnt = 0;
    int cntCarsTravelingEast = 0;
    
    int i;
    for (i = 0; i < N; i++){
        if (A[i] == 0){
            cntCarsTravelingEast++;
        }
        else {
            cnt += cntCarsTravelingEast;             
            if (cnt > 1000000000){
                return -1;
            }
        }
    }
    
    return cnt;
}

Lesson 2: MissingIntegers (Missing Integers)

https://codility.com/programmers/lessons/2
Lesson 2: Missing Integersの答えがこちらになります。

やり方として最初に浮かぶのは、ある値が見つかったかどうかわかるようにフラグたてておいて、後でチェックすることですね。　問題もO(N)のメモリ使用量で良いと言ってるので、簡単にNの大きさの配列を作ってしまいましょう。

このやり方でも、ちゃんとやろうとすると、一つの値につき、見つかった・見つかっていないの１ビットですむのですが、文句を言われなければそうはせず、単純にintとかで富豪的に試してしまいましょう。

最も小さい正の整数といわれているので、０以下は無視して良く、またNより大きい値があった場合は、必ずN以下にかけている数字が入ってきますからNより大きい値は無視していいですね。

1-Nまで全部見つかった場合は、当然N+1がないという答えでよいので、これで取りあえず実装してみましょう。

とりあえず１００％のスコアがでたので、これでよいということにしましょう。

--------------------------------
       the solution
--------------------------------

int solution(int A[], int N) 
{
    //prepare the flags
    int* flag = (int*)calloc(sizeof(int), N);
    
    //iterate the given array A.
    int i;
    for (i = 0; i < N; i++){
        //we can neglect the value below 1 or larger than N.
        if (A[i] <= 0 || A[i] > N){
            continue;
        }
        //turn on the flag. this is the zero-indexed array.
        //so give -1 as the offset.
        flag[A[i] - 1] = 1;
    }
    
    //if there is no positive integer lacking between 1 - N,
    //the answer should be N + 1.
    int ans = N + 1;
    //found the minimum integer that is not found in the array A.
    for (i = 0; i < N; i++){
        if (flag[i] == 0){
            //the answer is (the index + 1). (we have -1 offset).
            ans = i + 1;
            break;
        }
    }
    
    //free the allocated memory space.
    free(flag);
    
    return ans;

}

Lesson 2: MaxCounters (Max Counters)

https://codility.com/programmers/lessons/2
Lesson 2:MaxCountersの解答がこちらになります。

これは結構面白い課題で、普通に問題の言う仕様でそのまま作ってしまうと、パフォーマンスが悪くて点数がもらえません。

たとえば、下のそういったかんじの実装ですと７７％しかもらえないのです。

 


--------------------------------------------
A Simple Solution
--------------------------------------------
struct Results solution(int N, int A[], int M) 

{
    struct Results result;

    result.C = calloc(sizeof(int), N);
    result.L = N;

    int max = 0;
    
    int i, j;
    for (i = 0; i < M; i++){
        int op = A[i];
        //if the op is max counter.
        if (op == N + 1){
            for (j = 0; j < N; j++){
                result.C[j] = max;
            }
        }
        //if the op is increase(x)
        else {
            //op is beweetn 1 to N, but the index for the array C 
            //is between 0 and (N-1). Decrease op to adjust it.
            op--; 
            result.C[op]++;
            if (result.C[op] > max){
                max = result.C[op];
            }
        }
    }

    return result;
}


おそらく、これはいちいちmax counter命令が発効された時に、配列を全部更新しているからで、それをやめれば良さそうです。

いちいち更新するかわりにフラグをおさめる配列を用意して、max counterの時はそれを一気に０クリアするだけ、そして、ある位置がincrease命令を発効されたら、その位置と対応するフラグをみて、初めてそこで更新という戦略にしてみました。

スコアは88%まであがりましたが、まだまだ先がありそうです。

--------------------------------------------
A Better Solution (1)
--------------------------------------------

struct Results solution(int N, int A[], int M) 

{

    struct Results result;

    result.C = calloc(sizeof(int), N);

    result.L = N;

    int* flg = alloca(sizeof(int) * N);

    memset(flg, 0x00, sizeof(int) * N);

    

    int max = 0;

    int maxAtTheLastMaxCntOp = 0;

    

    int i;

    for (i = 0; i < M; i++){

        int op = A[i];

        //if the op is max counter.

        if (op == N + 1){

            maxAtTheLastMaxCntOp = max;

            memset(flg, 0x00, sizeof(int) * N);    

        }

        //if the op is increase(x)

        else {

            //op is beweetn 1 to N, but the index for the array C 

            //is between 0 and (N-1). Decrease op to adjust it.

            op--; 

            if (flg[op] == 1){

                result.C[op]++;

            }

            else {

                result.C[op] = maxAtTheLastMaxCntOp + 1;

                flg[op] = 1;                

            }

            

            if (result.C[op] > max){

                max = result.C[op];

            }

        }

    }

    

    //apply the 'max counter' operation

    //to the slot(s) where it should be applied. 

    int j;  

    for (j = 0; j < N; j++){

        if (flg[j] == 0){

            result.C[j] = maxAtTheLastMaxCntOp;

        }

    }

    return result;

}

結局、フラグを使うのではダメだという事がわかりました。ここで気づくのは、もし、更新しようとしている位置が、過去のmax counterが発行された時の値より小さいかどうかだけ調べればフラグっていらないんですよね。そうするとフラグのクリアなどをする必要がなくなります。

この方針だと１００％になりますね。ちょっとした発想の転換を試される問題でした。

--------------------------------------------
A Better Solution (2)
--------------------------------------------
struct Results solution(int N, int A[], int M) 
{
    struct Results result;

    result.C = calloc(sizeof(int), N);
    result.L = N;
    
    int max = 0;
    int maxAtTheLastMaxCntOp = 0;
    
    int i;
    for (i = 0; i < M; i++){
        int op = A[i];
        //if the op is max counter.
        if (op == N + 1){
            maxAtTheLastMaxCntOp = max;
        }
        //if the op is increase(x)
        else {
            //op is beweetn 1 to N, but the index for the array C 
            //is between 0 and (N-1). Decrease op to adjust it.
            op--; 
            if (result.C[op] < maxAtTheLastMaxCntOp){
                result.C[op] = maxAtTheLastMaxCntOp + 1;
            }
            else {
                result.C[op]++;
            }     
            //update the max value if necessary.
            if (max < result.C[op]){
                max = result.C[op];
            }
        }
    }
    
    //apply the 'max counter' operation
    //to the slot(s) where it should be applied. 
    int j;  
    for (j = 0; j < N; j++){
        if (result.C[j] < maxAtTheLastMaxCntOp){
            result.C[j] = maxAtTheLastMaxCntOp;
        }
    }
    return result;
}

Lesson 2: FrogRiverOne (Frog River One)

https://codility.com/programmers/lessons/2
Lesson 2: FrogRiverOneの答えがこちらになります。

position 1 - Xまでの間が全て葉っぱで埋まったかどうかという事をチェックするだけなので、
別の配列B、サイズはXを用意して、そこに葉っぱが既に落ちたかどうかのフラグに利用します。
既に落ちてればカウントはせず、初めて落ちた時にカウントして、カウント数がXになれば、そこまでのみちが完成した事になります。

int solution(int X, int A[], int N) 
{
    //the array to store flags
    int B[X];

    //clear the flags.
    memset(B, 0x00, sizeof(B[0]) * X);
    
    //let leaves fall!
    int t;
    int cnt = 0;
    int ans = -1;
    for (t = 0; t < N; t++){
        //get the position where a leave fall at time T. 
        int p = A[t] - 1; //(the array B is from 0 to X-1)
        //if it is between 0 to X-1 and 
        //no leave has fallen onto the position before, count it.
        if (p < X && B[p] == 0){
            B[p] = 1;
            cnt++;
            //is the route filled with leaves?
            if (cnt == X){
                ans = t;
                break;
            }
        }
    }

    return ans;
}

Lesson 2: PermCheck (Perm Check)

https://codility.com/programmers/lessons/2
Lesson 2 - PermCheckの答えがこちらになります。

この問題のcomplexityは下のようになっていますね。

最悪実行時間はO(N)ってことは、多分「ループはネストしてない」とかというお話で、最悪メモリ使用量がO(N)なのは「入力のサイズに比例したメモリ使っていい」というお話のはず。

========================================================================

Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage 

(not counting the storage required for input arguments).

========================================================================

で、下のコードになります。バケツ戦略？みたいなよくある手法です。

まず、配列B（入力と同じサイズ＝最悪メモリ使用量O(N))を用意して、そこにフラグを建てていきます。この配列Bでは、B[i] = 1の場合、iという数字が配列Aの中で見つかったという事になります。０なら見つからなかったという意味にします。

最初に配列Aをスキャンして配列Bにフラグをたてていきます。このときN以上の数字があったら、その時点でpermutationできてないので結果がわかっておしまい、そうでなければ配列Bのスキャン。

配列Bをスキャンしている間に０があったら、その数字は欠けているので、permutationになっていません。全部１だったら、出来てます、ってことですね。

================================================================================

int solution(int A[], int N) 

{

    int B[N];

    memset(B, 0x00, sizeof(B));

    int i;

    for (i = 0; i < N; i++){

        if (A[i] > N){

           return 0;

        }

        B[A[i] - 1] = 1;

    }

    

    for (i = 1; i < N; i++){

        if (B[i] == 0){

           return 0;

        }

    }

    

    return 1;

}