# Do not gather 60 punti

**URL:** <https://forum.olinfo.it/t/do-not-gather-60-punti/7355>\
**Category:** Aiuto\
**Created:** [23 Maggio 2022, 7:03am UTC](https://forum.olinfo.it/t/do-not-gather-60-punti/7355 "2022-05-23T07:03:02Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![Simone04](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone04/32/1274_2.png) [@Simone04](https://forum.olinfo.it/u/Simone04)\
**Post date:** [23 Maggio 2022, 7:03am UTC](https://forum.olinfo.it/t/do-not-gather-60-punti/7355/1 "2022-05-23T07:03:02Z")

</div>

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

#define MAXN 100000

int n, d, i, j, co = 0;
int A[MAXN];

int main() {

    assert(2 == scanf("%d %d", &n, &d));
    for(i=0;i<n;i++)
        {
            assert(1 == scanf("%d", &A[i]));
        }

        for(i=n-1;i>=0;i--)
        {
            for(j=i-1;j>=0;j--)
            {
                if(A[i]-A[j]>=d)
                {
                    i--;
                    j = i-1;
                }
                if(A[i]-A[j]<d)
                {
                    co++;
                }

            }

        }

printf("%d", co);

}

```

---

<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:** [23 Maggio 2022, 12:24pm UTC](https://forum.olinfo.it/t/do-not-gather-60-punti/7355/2 "2022-05-23T12:24:06Z")

</div>

La tua soluzione ha complessità temporale O(N^2), per rimanere nel limite di tempo devi abbassarla a O(NlogN) oppure O(N).

---

<div class="post-metadata">

**Author:** ![Simone04](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone04/32/1274_2.png) [@Simone04](https://forum.olinfo.it/u/Simone04)\
**Post date:** [24 Maggio 2022, 6:27am UTC](https://forum.olinfo.it/t/do-not-gather-60-punti/7355/3 "2022-05-24T06:27:31Z")

</div>

Si lo so che devo portare i tempi sotto O n^2 ma non riesco a risparmiare tempo nel caso in cui tutti i casi sono sbagliati e quindi ti devi confrontare tutti gli elementi

---

<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:** [24 Maggio 2022, 6:53am UTC](https://forum.olinfo.it/t/do-not-gather-60-punti/7355/4 "2022-05-24T06:53:07Z")

</div>

Ti consiglio di dare un’occhiata a [questo](https://forum.olinfo.it/t/problem-do-not-gather/6500) thread.

---

<div class="post-metadata">

**Author:** ![Simone04](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone04/32/1274_2.png) [@Simone04](https://forum.olinfo.it/u/Simone04)\
**Post date:** [26 Maggio 2022, 7:23am UTC](https://forum.olinfo.it/t/do-not-gather-60-punti/7355/5 "2022-05-26T07:23:30Z")

</div>

Ciao scusa ma credo di non aver capito la soluzione che mi hai proposto, come posso fare per cambiare il tempo di esecuzione da quadratico a lineare? Il problema è che la mia soluzione riesce a risparmiare tempo solo quando ci sono dei casi in cui la differenza tra due numeri è maggiore o uguale a d

---

<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:** [26 Maggio 2022, 7:54am UTC](https://forum.olinfo.it/t/do-not-gather-60-punti/7355/6 "2022-05-26T07:54:16Z")

</div>

Il ragionamento è spiegato in quel post, posso provare a fare un esempio per chiarire. Se tu hai N persone devi trovare per ogni i \< N l’indice j che sarebbe l’indice della persona più a destra di i tale che risultano essere troppo vicini. Quindi se con i=3 trovi j=5 allora sai che ci sono j-i = 5-3=2 coppie per i = 3 che non vanno vene (3,4), (3,5), ripetendo il ragionamento per ogni i e sommando i risultati trovati trovi la risposta a questo problema.

Per farlo velocemente supponi che all’iterazione precedente i valeva 35 e avevi trovato j = 70, ora incrementando i a 36 sai che il nuovo j deve valere almeno 70 perché se la persona in posizione 70 era troppo vicino a quella in posizione 35 allora sarà sicuramente troppo vicina anche a quella in posizione 36. Quindi per trovare il nuovo j inizi a controllare partendo dalla posizione 70. Facendo in questo modo hai gli indici i e j che vengono entrambi incrementati N volte durante tutta l’esecuzione e quindi hai che la complessità finale è lineare