# Problem 'Do not gather'

**URL:** <https://forum.olinfo.it/t/problem-do-not-gather/6500>\
**Category:** Olimpiadi\
**Created:** [16 Gennaio 2021, 1:57pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500 "2021-01-16T13:57:01Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![Leyonad](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/3bc359/32.png) [@Leyonad](https://forum.olinfo.it/u/Leyonad)\
**Post date:** [16 Gennaio 2021, 1:57pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/1 "2021-01-16T13:57:02Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [16 Gennaio 2021, 3:01pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/2 "2021-01-16T15:01:24Z")

</div>

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`.

---

<div class="post-metadata">

**Author:** ![Leyonad](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/3bc359/32.png) [@Leyonad](https://forum.olinfo.it/u/Leyonad)\
**Post date:** [16 Gennaio 2021, 3:13pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/3 "2021-01-16T15:13:32Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mauro\_losmauro](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mauro_losmauro/32/2910_2.png) [@mauro\_losmauro](https://forum.olinfo.it/u/mauro_losmauro)\
**Post date:** [16 Gennaio 2021, 3:38pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/4 "2021-01-16T15:38:29Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [16 Gennaio 2021, 3:49pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/5 "2021-01-16T15:49:39Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Leyonad](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/3bc359/32.png) [@Leyonad](https://forum.olinfo.it/u/Leyonad)\
**Post date:** [16 Gennaio 2021, 5:55pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/6 "2021-01-16T17:55:52Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Leyonad](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/3bc359/32.png) [@Leyonad](https://forum.olinfo.it/u/Leyonad)\
**Post date:** [16 Gennaio 2021, 9:55pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/7 "2021-01-16T21:55:28Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [16 Gennaio 2021, 10:24pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/8 "2021-01-16T22:24:06Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Leyonad](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/3bc359/32.png) [@Leyonad](https://forum.olinfo.it/u/Leyonad)\
**Post date:** [16 Gennaio 2021, 10:49pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/9 "2021-01-16T22:49:37Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [16 Gennaio 2021, 11:08pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/10 "2021-01-16T23:08:26Z")

</div>

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:

> [@frakkiobello](#):
>
> so instead of setting `j = i` you can keep the prevoius value of `j` .

---

<div class="post-metadata">

**Author:** ![Leyonad](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/3bc359/32.png) [@Leyonad](https://forum.olinfo.it/u/Leyonad)\
**Post date:** [16 Gennaio 2021, 11:53pm UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/11 "2021-01-16T23:53:11Z")

</div>

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

```auto
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.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [17 Gennaio 2021, 9:50am UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/12 "2021-01-17T09:50:47Z")

</div>

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`.

---

<div class="post-metadata">

**Author:** ![Leyonad](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/3bc359/32.png) [@Leyonad](https://forum.olinfo.it/u/Leyonad)\
**Post date:** [17 Gennaio 2021, 10:34am UTC](https://forum.olinfo.it/t/problem-do-not-gather/6500/13 "2021-01-17T10:34:37Z")

</div>

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

```auto
    #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;
    }

```