https://codility.com/programmers/lessons/4
ちょっと忙しかった時期があり、解答にも説明にも時間がかかる問題だったので放っておいたら、ブログのことをすっかり忘れていましたが、とりあえずアフィり許可がもらえたのでついでに再開しました。
で、この問題なんですが、凄く難しい上に、解答や説明が間違っているものがいろんなブログでありました（そのせいでちょっときちんと理解するのに手間がかかったり、説明を考えなければ行けませんでした。）。
基本的に、この問題はコンパイラ等を勉強するとレジスタ割り付けで出てくるような、「生存区間分析」とちょっと似た問題です。
とりあえず、いろいろな答えがあるのですが、段階を踏んで理解しつつ一番良い答えにたどり着きましょう。
1. 一番簡単な解答
一番シンプルな解答は、単に一つ一つディスクをとりあげて、他と重なるか見て行くことです。当然、スコアは最悪になります。
計算量も 'detected time complexity: O (N ** 2)' と表示され、まぁ、実際そんなもんです。
int solution(int A[], int N)
{
int cnt = 0; int i, j;
for (i = 0; i < N - 1; i++){ long long curl = (long long)i - A[i]; long long curr = (long long)i + A[i]; for (j = i + 1; j < N; j++){ long long posl = (long long)j - A[j]; long long posr = (long long)j + A[j];
if (posl <= curr && curl <= posr){ cnt++; if (cnt > 10000000){ return -1; } } } } return cnt; }
2. もうちょっと良いやり方。
もっと良いやり方を考えるために、とりあえず図にして考えてみましょう。これも他の人がよくやっている解答のようです。ソートも使いますし、sortingのセクション(Lesson 4)にあるには適切な解答かと思います。問題の要求するパフォーマンスにも合致しますし。
下にあるのが、例題のデータを図にした物です。線になっていますが、discの左端と右端に線を引いて、どこからどこまでdiscがあるか書いてあります。
こうやってみてみると、コンパイラの授業でやる生存区間の分析にそっくりですね。（日本の大学では授業ではそこまでやらないで、院に進む学生が自分で勉強するのでしょうか？）
それぞれのA[]の要素でしめされるディスクを変数とかんがえれば、それがコードのどこから何処の間で行きているか？みたいな問題になりますね。数を数えて、CPUのレジスタが足りなければ、メモリに一時的にでも変数の値を逃がす必要が出てきます。
なので、とりあえず生存区間分析の問題と思ってみて行けばいいのでしょうね。
生存区間が重なってるdiscは互いにintersectionがあると考えて良さそうです。でも実際には今回の問題ではいちいち生存しているdiscのペアを 全部あげる必要はなく、重なっている数だけですので、ちょっとしたテクニックが仕える訳です。
簡単に言うと、あるdiscが死ぬ時に、そこで行きている全部のdiscの数をが分かっていれば、それから１（discを引く）と、そこまでで生きているdiscにたいして重なっているdiscの数がわかりますね。
ですから、ソートを上手く使ったのちに、そのソートした配列を順番にスキャンしていけば上手く行きそうです。
このアプローチで一応100%のスコアがもらえ、計算の複雑性は, the detected time complexity is 'O(N * log(N)) or log(N)'と評価されます。,実際にはquick sort 'O(N * log(N))' が二つで、一つのfor loop でその後配列をスキャンする 'O(N)'の組み合わせです。(だから O(2 * N * log(N) + N),で、大きい方をとるとO(N * log(N) )の扱いになりますね。).
#include <alloca.h>
int compare(const void* a, const void *b)
{
long long l = *((long long*)a);
long long r = *((long long*)b);
if (l == r){
return 0;
}
return l < r ? -1 : 1;
}
int solution(int A[], int N) {
int memsize = sizeof(long long) * N;
long long* activate = (long long*)alloca(memsize);
long long* deactivate = (long long*)alloca(memsize);
long long i = 0;
for ( ; i < N; i++){
activate[i] = i - A[i];
deactivate[i] = i + A[i];
}
qsort(activate, N, sizeof(long long), compare);
qsort(deactivate, N, sizeof(long long), compare);
long long total = 0;
long long currentActive = 0;
long long activatedIndex = 0;
long long deactivatedIndex = 0;
for (i = 0; i < N; i++){
while (activate[activatedIndex] <= deactivate[deactivatedIndex] &&
activatedIndex < N){
activatedIndex++;
currentActive++;
}
currentActive--;
total += currentActive;
if (total > 10000000){
return -1;
}
deactivatedIndex++;
}
return total;
}
このコードだけ見ても、ちょっと掴みづらいかと思いますので、図で説明して行きましょう。とりあえず、右端、左端はそれぞれ別の配列にソートしてあり、小さいところから見て言っています。ここでもういちど、全部のペアを取る必要はなく、単にintersectionの数を数えれば良いだけのことにもう一度留意しましょう。
いま一番小さい右端をもつのは、A[0]のdiscですね。この'1'に注目すると、そこまでにある左端のかずは４つですね（A[0], A[1], A[2], A[4])です。A[0]がいま、一番小さい右端であるという前提でチェックしてるのですから、ここより小さい左端があるということは、必ずA[0]のディスクと重なっているディスクの左端だという事になります。
もし重なっていないディスクがこの中に含まれているとすると、A[0]の左端-1より小さいところに、そのディスクの右端がふくまれていることになり、A[0]が一番小さいという仮定（ソートしましたよね、さっき）に反しますね。
ですから、４つのディスクが１の時点まで生きていて、全てA[0]かそれとかさなっているディスクということになります。ここで１の時点で死ぬA[0]と他のディスクの重なりの数は、４−１＝３となります。
下の図を見て考えてみてください。
では、次にA[0]のディスクをもう取り除いてしまいましょう。なぜなら、A[0]と重なるディスクは全て数えたのですから、取り除いて数えてしまって構いませんね。もし残しておいて２度数えたらおかしな結果になりますよね。
取り除いたあと、今の状況で最も小さい右端をもつディスクはどれでしょうか？A[2]かA[3]ですね。どちらをとっても結局おなじ答えになるので、今回はA[2]を取ってみましょう。（興味がある方は、自分で同じようにためしてみてください）。
今はすでにA[0]は取り除かれたと考えているので、一番小さい右端はA[2]で、ここより左に左端をもつディスクは全て、A[2]とかさなっていると考えられますよね。そうでなければ、ソートしてあり現在はA[2]が最小だと言う仮定に反します。
今度は４にたどり着くまでに、A[3]の左端２で新しくもうひとつディスクが生まれました。そうすると、先ほどまで生きていたものと足して、４の時点では４つのディスクが生きていますね。さきほどの段階と同じようにA[2]が４で死ぬのですが、ここで３つのディスクがA[2]と重なっていることがわかりましたので、４−１＝３があらたにintersectionの合計に加えられます。先ほどの３と加えて、合計３＋３＝６が今までに見つかったintersectionになります。
それでは再度、A[2]を取り除いて同じことをしましょう。
今度はもう、新しいディスクは生まれないままA[3]の右端4にたどり着きますね。
生きているディスクは３のままですから、A[3]と重なるディスクは２つになります。
なので、結果、今のところのintersectionの合計は3 + 3 + 2 = 8になりますね。
A[5]にきましたが、これはディスクですが面積が０の点です。つまり５で生まれて５で直ぐ死ぬということですね。ですからA[5]が生まれてから、すぐ死ぬ直前では３つのディスクが生きているので、A[5]と重なるディスクは２つになります。つまり3 + 3 + 2 + 2 = 10が現在のintersectionの合計です。
また５を取り除いてみましょう。
次はA[1]の６が一番小さいですね。生きているディスクは２つですから、A[1]と重なるディスクの数は２−１＝１になります。これで合計すると3 + 3 + 2 + 2 + 1 = 11のインターセクションがここまで見つかりました。
そしてA[1]を取り除くともう一つしか残っていませんね。
つまり、もう他のディスクはみな死んだので、何とも重なっていません。ですから先ほどえた１１が解答になるわけです。
上のように図示したことで、わかりやすくなりましたか？もういちど強調したいのは、実際の生きているディスクのペアを取らなくていい問題で、単に数を数える問題ですから、上のようなアルゴリズムで、重なっている数だけを数えて行けば良かったのですね。
つまり、ディスクがactiveになる（liveになる)かdeactive(deadになる）かなるイベントをソート後に見て行けば、現在注目しているディスクの右端が一番小さい右端という仮定にもとづいて、そこより左に左端があるディスクは全て重なっていると言える。そうでなければ（重なっていないとすると）、現在注目しているディスクの右端より、左側に右端があるディスクがあると言うことになってしまう（そのディスクの右端が現在注目しているディスクの左端より左側にあることがこの場合重ならない条件ですね）ので、仮定に反するということになります。
ですから、今注目しているディスクの右端が一番小さいならば、そこより左側に左端があるディスクは絶対重なっていると言えるということです。
この性質をかんがえると、結局、有る地点でactiveなディスクの数が分かれば良いだけなので、更に問題を単純かして、ソートすらする必要がなくなります。
3. the best solution
上で述べた考えは、これはstack overflowで議論されていた解答で、ソートもいらないでO(N)の解答につながって行きます。ソートもいらないんですから、codilityの問題がソートのセクションにあるのがおかしいんじゃないかとも思うんですが、こういった詰めの甘さが常にcodilityにあるので、気にしないでいいのかもしれません。
http://stackoverflow.com/questions/4801242/algorithm-to-calculate-number-of-intersecting-discs
で、今から説明するやり方でも、きちんと１００％がでます。
この解答を理解するために、まずは、もうちょっと簡単にして考えましょう。
とりあえず、いままで分かったことは、実際に重なるディスクのペアは考えないでよく、重なりの数を数えるだけでした。そして、ある区間での生存状況と考えて調べて行きましたね。
結局分かったことは、「単にactivateされるイベントとdeactivateされるイベントがわかれば、0からN-1の数直線状の区間の有る点で、生きているディスクの数は分かるということです。
ですから、ソートするという考え方を辞めて二つの配列に、その数直線状の点で、activeになるイベントが幾つ発生したか、deactiveになるイベントが幾つ発生したかを考えればよさそうです。
そしてdeactiveになったときに我々はそこまで生きているactiveなディスクの数がわかれば、それから１をひくだけで、deactiveになったディスクと他のディスクの間のintersectionの数を得られるのでしたね。
とりあえず、この方針でかかれたのが下のコードです。今度はactivated, deactivatedの配列が用意されていますが、これらはactivate[i]やdeactivate[i]の時点で、activate/deactivateの各イベントが何回起きているかということを記録します。
また、仕様よりどのディスクの 右端も、からなず正になりますし、右端でそのディスクがdeactivateされると考えて重なりを計算するので,−１以下の左端は、0のところで始まったと考えてもよいということになります。同じような理由でN-1より右にディスクの左端があった場合、N-1で終わっていると考えてもよいことになりますね。
#include <memory.h>
#include <alloca.h>
int solution(int A[], int N) {
int memsize = sizeof(int) * N;
int* activated = (int*)alloca(memsize);
int* deactivated = (int*)alloca(memsize);
memset(activated , 0x00, memsize);
memset(deactivated , 0x00, memsize);
int i;
//counter the number of activation/deactivation at the index.
for (i = 0; i < N; i++){
//if the lower limit is below 0, consider it as 0.
//this won't affect the number of activated discs at the index.
long long lower_lim = i - (long long)A[i];
lower_lim = lower_lim < 0 ? 0 : lower_lim;
activated[lower_lim]++;
//the same to the upper limit.
long long upper_lim = i + (long long)A[i];
upper_lim = upper_lim > N - 1 ? N - 1 : upper_lim;
deactivated[upper_lim]++;
}
//let's scan the activated/deactivated arrays.
int total = 0;
int active = 0;
for (i = 0; i < N; i++){
active += activated[i];
if (active == 0 || deactivated[i] == 0){
continue;
}
//we have at least one deactivated disc at the index 'i'.
while (deactivated[i] > 0){
//active - 1is the number of the new intersection.
total += active - 1;
if (total > 10000000){
return -1;
}
//one disc is dead.
//so decrement the number of active discs.
active--;
deactivated[i]--;
}
}
return total;
}
さて、このコードのwhileループでは、ご丁寧にdeactivateのイベント一回につき、重なりの数を計算してtotalに足し、もし同じ地点に別のdeactivateイベントが残っていれば、さらにそれを同じ方針で何度も計算します。
でも、これ実際には等差数列の合計と全く同じですよね。たとえば７つ生存しているディスクがそこまでにあって、その地点で３つディスクが死ぬとすると、６、５、４とそれぞれのdeactivateイベントで合計にたされるわけですから。
つまり等差数列の和の計算の公式Sn = n (a + l) / 2（Snは合計、nは項数、aは初項、lは末項）でループ等せずとも計算できますね。
これをコードに適用して以下のようにします。当然パフォーマンスもあがるわけですし、１００％がもらえます。
#include <memory.h>
#include <alloca.h>
int solution(int A[], int N) {
int memsize = sizeof(int) * N;
int* activated = (int*)alloca(memsize);
int* deactivated = (int*)alloca(memsize);
memset(activated , 0x00, memsize);
memset(deactivated , 0x00, memsize);
int i;
//counter the number of activation/deactivation at the index.
for (i = 0; i < N; i++){
//if the lower limit is below 0, consider it as 0.
//this won't affect the number of activated discs at the index.
long long lower_lim = i - (long long)A[i];
lower_lim = lower_lim < 0 ? 0 : lower_lim;
activated[lower_lim]++;
//the same to the upper limit.
long long upper_lim = i + (long long)A[i];
upper_lim = upper_lim > N - 1 ? N - 1 : upper_lim;
deactivated[upper_lim]++;
}
//let's scan the activated/deactivated arrays.
int total = 0;
int active = 0;
for (i = 0; i < N; i++){
active += activated[i];
if (active == 0 || deactivated[i] == 0){
continue;
}
//Sn = n * (a + l) / 2
// where Sn is the sum of the sequence 9, 8, 7, 6, 5 ...
// n is the number of terms (= deactivated[i])
// a is the first term (= active - 1)
// n is the last term (= active - deactivated[i])
//
//int sn = deactivated[i] * ( (active - 1) + (active - deactivated[i]) / 2
int sn = deactivated[i] * (2 * active - 1 - deactivated[i]) / 2;
total += sn;
if (total > 10000000){
return -1;
}
active -= deactivated[i];
}
return total;
}
この問題は難しいし面白いかもしれませんが、いつ役にたつアルゴリズムなのか、自分は全く思いつきません。
ただ、様々なトリックをつかえるように問題が単純化してあるという嫌らしさです。この単純化のせいで良い解答が難しくなっているようですが、単純化したせいでこのアルゴリズムが他で役にたつのかというと、何処で役に立つか分かりません。本当にこういうのひつような状況があるのかなと思います．
実際のlinear register allocationなどを実装するときには、生きている変数のセットや知らないと、どの変数をレジスタにおいておくか、メモリに逃すかという判断が出来なくなるわけで、重なりの数だけ数えて意味がある場合はないですし、いつ使うんだろ、こういう戦略？
0 件のコメント:
コメントを投稿