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