# Problem 'Do not gather'

Subtask 4 gives the following error message: Execution timed out. I don’t know what else I could do differently.
Here is my code:

``````#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

// constraints
#define MAXN 100000

// input data
long long N, D, s, j, count, u;
long long P[MAXN];

int main() {

assert(2 == scanf("%Ld %Ld", &N, &D));
for(s=0; s<N; s++)
assert(1 == scanf("%Ld", &P[s]));

for(int i = 0; i < N-1; i++){
u = 0;
j = i;
while(u < D){
u += abs(P[j+1] - P[j]);
if(u < D){
count++;
}
j++;
}
}
long long answer = count;

printf("%lld\n", answer); // print the result
return 0;
}``````

Think whether or not binary search could be useful for this exercise. Note that there is also a linear time complexity solution which is similar to yours but avoids useles increments of `j`.

Thanks for answering.
Could you tell me the approach of the linear time complexity solution?

Knowing that values are sorted, you can keep track with just two variables l and r, how many value are still necessary to consider

Basically `j` 's value at the i-th iteration will be greater than or equal to `j`'s value at the (i-1)-th iteration, so instead of setting `j = i` you can keep the prevoius value of `j`. In this way both `i` and `j` are incremented at most N times, having a linear time complexity.

2 Mi Piace

Your suggestion helped me a lot. But also here the problem is that the same error message: Execution timed out, occurs at subtask 4.
It can’t be because of the time complexity.

``````for(int i = 0, j = 1; i < N-1;){
diff = P[j] - P[i];
if(diff >= D || j >= N){
i++;
j = i+1;
}else{
j++;
count++;
}
}``````

Does anyone know why this error message keeps coming up and how to fix it?
The code fails on the “No additional limitations” subtask. I do not understand why.

Can you post the complete code cause this part shouldn’t be enough

``````#include <stdio.h>
#include <assert.h>
using namespace std;

// constraints
#define MAXN 100000

// input data
long long N, D, s, j, count, diff;
long long P[MAXN];

int main() {

assert(2 == scanf("%Ld %Ld", &N, &D));
for(s=0; s<N; s++)
assert(1 == scanf("%Ld", &P[s]));

for(int i = 0, j = 1; i < N-1;){
diff = P[j] - P[i];
if(diff >= D || j >= N){
i++;
j = i+1;
}else{
j++;
count++;
}
}
long long answer = count;

printf("%lld\n", answer); // print the result
return 0;
}``````

You are basically doing the same iterations you did in the first solution you posted. When tou do `j = i + 1` you are ignoring what I said here:

I don’t quite get it. If I keep the previous value of j, isn’t it possible that I skip a pair whose difference is smaller than D?
For example:

6 100
120 200 210 250 300 400

``````for(int i = 0, j = 1; i < N-1){
diff = p[j] - p[i];
if(diff >= D || j >= N){
i++;
}else{
j++;
count++;
}
}
``````

200 - 120 = 80 --> smaller j++ count++
i = 0 and j = 2 and count = 1

210 - 120 = 90 --> smaller j++ count++
i = 0 and j = 3 and count = 2

250 - 120 = 130 --> bigger i++
i = 1 and j = 3

250 - 200 = 50 --> smaller j++ count++
i = 1 and j = 4 and count = 3

300 - 200 = 100 --> bigger/equal i++
i = 2 and j = 4

300 - 210 = 90 --> smaller j++ count++
i = 2 and j = 5 and count = 4

400 - 210 = 180 --> bigger i++
i = 3 and j = 5

400 - 250 = 150 --> bigger i++
i = 4 and j = 5

400 - 300 = 100 --> bigger/equal i++
i = 5 and j = 5

Count = 4
Expected = 6

When I increase j to 3, i remains 0. The difference between 250 and 120 is bigger than D, which means I increase i by 1. Then I compare 250 with 200. But I never actually compared 210 with 200, because I have already increased j to 250.
I still have a mistake in my thinking somewhere.

You are trying to count each good pair individually, but this approach is too slow because the number of “good-pairs” could be quadratic. Want you really need to do is: for each `i` find the smallest `j` such that `P[j]-P[i] >= D`, and update the current answer adding the new `j-i-1` good pairs you just found ({i, i+1}, {i, i+1},…,{i,j-1}).
Like I said before the new `j` will be greater than or equal to the `j` of the previous iteration, so you don’t need to set `j` to `i+1`.

1 Mi Piace

Thank you so much! I finally got it right. Thank you.

``````    #include <stdio.h>
#include <assert.h>
using namespace std;

// constraints
#define MAXN 100000

// input data
long long N, D, s, j, count, diff;
long long P[MAXN];

int main() {

assert(2 == scanf("%Ld %Ld", &N, &D));
for(s=0; s<N; s++)
assert(1 == scanf("%Ld", &P[s]));

for(int i = 0, j = 1; i <= N-2;){
diff = P[j] - P[i];
if(diff >= D || j >= N){
count += (j-i-1);
i++;
}else{
j++;
}
}
long long answer = count;

printf("%lld\n", answer); // print the result
return 0;
}
``````