# Numeri anticipati, tag binary search?

**URL:** <https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315>\
**Category:** Chiarimenti\
**Created:** [15 Gennaio 2017, 6:18pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315 "2017-01-15T18:18:57Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![doublechar14](https://forum.olinfo.it/user_avatar/forum.olinfo.it/doublechar14/32/426_2.png) [@doublechar14](https://forum.olinfo.it/u/doublechar14)\
**Post date:** [15 Gennaio 2017, 6:18pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/1 "2017-01-15T18:18:57Z")

</div>

Stavo risolvendo “numeri” e sono arrivato ad una soluzione 100/100 che però non usa la ricerca binaria,  
fa questo:

scorre l’array con le piante tenendo la somma, sottraendo da sinistra e aggiungendo da destra

Quindi quale sarebbe la soluzione che usa la ricerca binaria?

O forse il tag è errato?

---

<div class="post-metadata">

**Author:** ![arna1998](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/ea5d25/32.png) [@arna1998](https://forum.olinfo.it/u/arna1998)\
**Post date:** [15 Gennaio 2017, 7:22pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/2 "2017-01-15T19:22:12Z")

</div>

Il tag ricerca binaria l’ho messo io, quindi ti posso spiegare la mia soluzione che però è meno efficiente della tua:

Creo un vector V che contiene all’indice i la somma del valore delle prime i piante. Esiste una sequenza valida che termina con l’i-esima pianta solo se esiste un valore j\<i tale che V[i]-V[j]=M. Dato che le piante hanno solo valori non negativi allora il vector V è ordinato, quindi posso usare la ricerca binaria per trovare j valido, se esiste.

---

<div class="post-metadata">

**Author:** ![doublechar14](https://forum.olinfo.it/user_avatar/forum.olinfo.it/doublechar14/32/426_2.png) [@doublechar14](https://forum.olinfo.it/u/doublechar14)\
**Post date:** [15 Gennaio 2017, 8:13pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/3 "2017-01-15T20:13:36Z")

</div>

Ah capito, grazie della spiegazione 🙂

---

<div class="post-metadata">

**Author:** ![Spippolino01](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/a88e4f/32.png) [@Spippolino01](https://forum.olinfo.it/u/Spippolino01)\
**Post date:** [5 Agosto 2017, 11:37am UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/4 "2017-08-05T11:37:43Z")

</div>

Anch’io avevo pensato a questa soluzione, ma… la complessità nel caso peggiore non sarebbe NLog(N)? Se non sbaglio con N= 10^6 va fuori tempo.

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [5 Agosto 2017, 12:16pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/5 "2017-08-05T12:16:09Z")

</div>

Una soluzione in \mathcal O(N\log N) dovrebbe funzionare, tuttavia per input di queste dimensioni solitamente si usa [fast I/O](https://forum.olinfo.it/t/cottarelle-in-classe/4730/15).

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [5 Agosto 2017, 1:02pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/6 "2017-08-05T13:02:30Z")

</div>

Un algoritmo in \mathcal O(NlogN) con N \leq 10^6 può entrare comunque nei limiti di tempo se ha costanti piccole, come è il caso nella ricerca binaria. Se l’algoritmo utilizzasse strutture dati più complesse molto probabilmente andrebbe fuori tempo anche con la stessa complessità asintotica.  
In questo caso poi le operazioni sono leggermente di meno di \mathcal O(NlogN), \sum\_{i=1}^{N}{log\_2(i)} \approx 1,85\cdot10^7, che si riesce a far andare in un tempo decente, magari usando il fastin.  
Nei problemi più recenti spesso quando si vuole una soluzione lineare si mette N \approx 10^7, dove solo Chen riesce a nascondere fattori logaritmici.

---

<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:** [5 Agosto 2017, 7:38pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/7 "2017-08-05T19:38:24Z")

</div>

> [@dp\_1](#):
>
> dove solo Chen riesce a nascondere fattori logaritmici

Cosa vorrebbe dire?per nascondere intendi evitarli?

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [5 Agosto 2017, 8:24pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/8 "2017-08-05T20:24:22Z")

</div>

Intendo ottimizzare, forte.  
Se non sbaglio alle ultime nazionali ha risolto lungomare in \mathcal O(NlogN) con N \leq 10^7, col piccolo dettaglio che la binaria che faceva non era in log\_2N ma in log\_{22}N, riuscendo a farla stare nei tempi.  
Io neanche dopo un sacrificio a Tarjan e una seduta spiritica con Turing riesco a fare queste cose.

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [5 Agosto 2017, 8:56pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/9 "2017-08-05T20:56:10Z")

</div>

Come ha fatto a fare la ricerca binaria in \log\_{22}N?  
Sono troppo curioso ☹

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [5 Agosto 2017, 9:05pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/10 "2017-08-05T21:05:06Z")

</div>

Magia nera. Pura magia nera.

Mi pare prendesse il pivot non a metà dell’intervallo ma a un ventiduesimo, come complessità non è veramente log\_{22}N ma per quel problema velocizzava la soluzione.

---

<div class="post-metadata">

**Author:** ![Spippolino01](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/a88e4f/32.png) [@Spippolino01](https://forum.olinfo.it/u/Spippolino01)\
**Post date:** [7 Agosto 2017, 1:25pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/11 "2017-08-07T13:25:47Z")

</div>

Ho provato a scrivere una soluzione in O(Nlog(N)) ma totalizzo solamente 55/100. In 4 casi va fuori tempo di al massimo 0.160, e in 5 casi sbaglia l’output (può darsi che vada in overflow?)

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [8 Agosto 2017, 9:24am UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/12 "2017-08-08T09:24:15Z")

</div>

Hai provato con il fast I/O?  
Per i casi sbagliati dubito che sia overflow, se leggi bene la assunzioni noterai che la soluzione è inferiore a 2^{31}.

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [8 Agosto 2017, 10:20am UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/13 "2017-08-08T10:20:19Z")

</div>

Puoi postare il codice?

---

<div class="post-metadata">

**Author:** ![Spippolino01](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/a88e4f/32.png) [@Spippolino01](https://forum.olinfo.it/u/Spippolino01)\
**Post date:** [9 Agosto 2017, 9:54am UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/14 "2017-08-09T09:54:47Z")

</div>

ecco la soluzione che totalizza 55/100:

```
 #include <bits/stdc++.h>
 #define mp make_pair

```

using namespace std;

typedef long long ll;

ll tot = 0;  
int somma, n;  
unordered\_map \<ll, bool\> mappa;  
vector \<pair \<ll, int\> \> v;

int readInt()  
{  
int res = 0;  
char ch = 0;  
while(ch \< ‘0’) ch = getchar\_unlocked();  
for(; ch \>= ‘0’; ch = getchar\_unlocked()) res = res \* 10 + ch - ‘0’;  
return res;  
}

int cerca(ll numero){

```
int lb = -1,
    ub = v.size();
while(lb+1 < ub)
{
    int m = (lb+ub)/2;
    if(v[m].first == numero)
        return m;
    else if(v[m].first > numero)
        ub = m;
    else
        lb = m;
}
return ub;

```

}  
int main(){

```
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
somma = readInt();
n = readInt();
v.push_back(mp(0, 1)); mappa[0] = true;
for(int i=0; i<n; i++)
{
    int a;
    a = readInt();
    int ultimo = v.size()-1; int New = v[ultimo].first+a;
    mappa[New]=true;
    if(a!=0)
        v.push_back(mp(New, 1));
    else
        v[ultimo].second++;
}
if(v.size() == 1) // tutti zero
{
    cout << n*(n+1)/2;
    return 0;
}
for(int i=v.size()-1; i>=0; i--)
{
    ll q= v[i].first-somma;
    if(!mappa[q])
        continue;
    if(q < 0)
        break;
    tot += (v[i].second * v[cerca(q)].second);
}
cout << tot;

```

}

creo un vector di pair di somme prefisse in cui tengo la frequenza: v[i].first contiene la somma prefissa, mentre v[i].second contiene quante volte quel valore compare (che equivale al numero di zeri dopo quel numero); inoltre tengo in un unordered map i valori presente nel vector di somme prefisse. Poi faccio un ricerca binaria per trovare i numeri “complementari”.  
Spero di essere stato chiaro.

P.S.: non riesco a postare il codice tutto intero: me lo spezza in due prima del main 😅😂

---

<div class="post-metadata">

**Author:** ![Spippolino01](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/a88e4f/32.png) [@Spippolino01](https://forum.olinfo.it/u/Spippolino01)\
**Post date:** [9 Agosto 2017, 10:08am UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/15 "2017-08-09T10:08:49Z")

</div>

Ho provato a togliere la unordered\_map e non va più fuori tempo. Ora però faccio 75/100 perchè mi sbaglia degli output (testacase 11, 12, 17, 18, 19) 😞

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [9 Agosto 2017, 11:03am UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/16 "2017-08-09T11:03:42Z")

</div>

Per incollare il codice senza che lo tagli basta mettere tre accenti gravi all’inizio e alla fine:

```auto

```

//codice

```auto

```

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [9 Agosto 2017, 1:35pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/17 "2017-08-09T13:35:05Z")

</div>

Ho guardato il tuo codice, in particolare questa parte:

```auto
if(v.size() == 1) // tutti zero
{
    cout << n*(n+1)/2;
    return 0;
}

```

Oltre che inutile, mi sembra anche sbagliata, prova questo input:

```auto
0 2
5 5

```

Tuttavia non è questa la causa degli output sbagliati, la causa è l’overflow:

```auto
int New = v[ultimo].first+a;

```

sostituisci `int` con `ll` e otterrai 100/100.

---

<div class="post-metadata">

**Author:** ![Spippolino01](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/a88e4f/32.png) [@Spippolino01](https://forum.olinfo.it/u/Spippolino01)\
**Post date:** [10 Agosto 2017, 10:46am UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/18 "2017-08-10T10:46:37Z")

</div>

> [@bortoz](#):
>
> Oltre che inutile, mi sembra anche sbagliata, prova questo input:
> 
> 0 2  
> 5 5

in questo caso non entra neanche in questa if [quote=“bortoz, post:17, topic:4315”]  
if(v.size() == 1) // tutti zero  
{  
cout \<\< n\*(n+1)/2;  
return 0;  
}  
[/quote]  
perchè nel vector v all’inizio pusho sempre uno 0.

> [@bortoz](#):
>
> la causa è l’overflow:

immaginavo, solo che non trovavo dove potesse essere.  
Grazie mille dell’ aiuto!  
P.S.: ho trovato anche una soluzione molto più veloce (direi con una complessità lineare).

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [10 Agosto 2017, 11:01am UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/19 "2017-08-10T11:01:10Z")

</div>

> [@Spippolino01](#):
>
> in questo caso non entra neanche in questa if

Chiedo venia, comunque il secondo d’esempio è piuttosto ingannante e complica solamente la soluzione, io non l’ho neanche considerato eppure la mia soluzione fa 100/100.

La soluzione lineare non è troppo difficile, io l’ho risolto così:

l’idea è quella di tenersi due indici i e j e calcolarsi la somma da V\_i a V\_j, se tale somma è inferiore a M, incremento j, se è maggiore di M, incremento i e infine se è uguale conto gli zeri all’inizio e alla fine e li moltiplico tra di loro incrementando il risultato.

---

<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:** [10 Agosto 2017, 1:26pm UTC](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315/20 "2017-08-10T13:26:46Z")

</div>

Piccola curiosità, Quali sono i tempi della vostra soluzione?

[Pagina seguente](https://forum.olinfo.it/t/numeri-anticipati-tag-binary-search/4315.md?page=2)
