Lesson 13: AbsDistinct (abs distinct)

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

簡単な問題ですね。

二つのカーソールを用意します。一つ目の'l'は配列を左から右に、もう一つの'r'は配列を右から左にスキャンします。

もし abs(A[l]) > abs(A[r]), であれば、左のカーソルを右に一つ 
もし abs(A[l]) < abs(A[r]), であれば、右のカーソルを左に一つ
もし abs(A[l]) == abs(A[r]), であれば、両方のカーソルをそれぞれ動かします。

上のどれであるにしろ、新しいabsolute distinct valueひとつ見つかったということですから、カウンタを一つ増やします。

昇順に数字が並んでいるので、これで大丈夫で末。

あとは、配列Aに入っている値が同じ値が連続していることがあるというのがちょっとしたトラップです（例えば、[-5, -4, -4, -4, 0, 1, 1, 1...]）。こういう場合を考えると、同じ値が続いているなら、無視して更に進めないと行けないですね。

ですが、これだけではthe 90% correctness scoreで（パフォーマンスは１００％ですが）した。トータルは９２％。何故かというと、arith_overlowテストに失敗したからです。

#include <math.h>

int solution(int A[], int N) 
{    
    int l = 0;
    int r = N - 1;
    
    int cnt = 0;
    
    while(l <= r){
        
        int absl = abs(A[l]);
        int absr = abs(A[r]);
        
        //we are sure we are going to find one distinct number.
        cnt++;
        
        //move the cursor 
        if (absl < absr){
            //skip if the same abs value is found in the new position.
            while(r > 0 && absr == abs(A[r])){
                r--;
            }
        }
        else if (absl > absr){
            //skip if the same abs value is found in the new position.
            while(l < N && absl == abs(A[l])){
                l++;
            }
        }
        else {
            //skip if the same abs value is found in the new position.
            while(r > 0 && absr == abs(A[r])){
                r--;
            }
            while(l < N && absl == abs(A[l])){
                l++;
            }
        }
    
    }
    
    return cnt;
}

バグです。簡単な問題なのに。Cの整数の範囲は（Codilityは32bit環境ですので）[−2,147,483,648..2,147,483,647]になりますね。正の方が一つ範囲がすくないですね。

なのでabs(−2,147,483,648) は−2,147,483,648になってしまうのです。

これを考慮して、まず最小の値が−2,147,483,648であれば、カウンタを１増やした後、abs関数を使っても安全な値が出るまで、スキャンしましょう。

これで１００％のスコアがもらえました。

BigIntegerなどの型がある言語でやっている人には関係のないバグですね…

#include <math.h>

int solution(int A[], int N) 
{    
    int l = 0;
    int r = N - 1;
    
    int cnt = 0;
    
    //we can't handle abs(-2147483648). Since the max value for int is
    //2147483647, abs(-2147483648) becomes -2147483648.  
    if (A[l] == -2147483648){
        cnt++;
        while(l < N && A[l] == -2147483648){
            l++;
        }
    }
    
    while(l <= r){
        
        int absl = abs(A[l]);
        int absr = abs(A[r]);
        
        //we are sure we are going to find one distinct number.
        cnt++;
        
        //move the cursor 
        if (absl < absr){
            //skip if the same abs value is found in the new position.
            while(r > 0 && absr == abs(A[r])){
                r--;
            }
        }
        else if (absl > absr){
            //skip if the same abs value is found in the new position.
            while(l < N && absl == abs(A[l])){
                l++;
            }
        }
        else {
            //skip if the same abs value is found in the new position.
            while(r > 0 && absr == abs(A[r])){
                r--;
            }
            while(l < N && absl == abs(A[l])){
                l++;
            }
        }
    
    }
    
    return cnt;

}

NOTE: Pythonで 'len(set([abs(x) for x in A]))' とか書いている人もおおいですが、これはO(N)にならなそうです。Setに対する新しい挿入がN回行われるので、挿入のコストをNに書けなければ行けません。実装によりますがSet内の要素が増えれば増えるほど挿入のコストは増加しそうですね。（定数時間でやるような無駄なメモリを使う実装にはなっていないと思います）。

ハッシュテーブルを使えば 挿入がO(1)ですむという人も居るでしょうがNの範囲が[1..100,000]、値の範囲が[−2,147,483,648..2,147,483,647]なので、想定されているワーストケースの空間計算量がO(N)ということは、ハッシュ値の衝突が当然予想されます(32bitの長さのテーブルを用意することは現実にはないでしょう）。

ということで、len(set([abs(x) for x in A]))は答えとしてはO(N)にはならないと予想で来ます。