# abc\_triangoli Execution timed out

**URL:** <https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191>\
**Category:** Aiuto\
**Created:** [28 Luglio 2015, 7:51am UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191 "2015-07-28T07:51:55Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![D\_Lore](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/74df32/32.png) [@D\_Lore](https://forum.olinfo.it/u/D_Lore)\
**Post date:** [28 Luglio 2015, 7:51am UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/1 "2015-07-28T07:51:55Z")

</div>

Avrei bisogno di una mano per ottimizzare il mio programma:

```
int i,n,s,j,k;
int V[10000000];
int main()
{
  in=fopen("input.txt","r");
  out=fopen("output.txt","w");
  fscanf(in,"%d\n",&n);
for(i=0;i<n;i++)
fscanf(in,"%d\n",&V[i]);
sort(V,V+n);
for(i=0;i<n-2;i++)
    {
        j=i+1;
        while(j<n-1)
           {
              k=j+1;
                   while(V[i]+V[j]>=V[k] && k<n) k++;
           s=s+(n-k);
           j++;
        }
   }
  fprintf(out,"%d",s);
  return 0;
}
```

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [28 Luglio 2015, 10:05am UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/2 "2015-07-28T10:05:24Z")

</div>

Ciao,  
il codice che hai messo è incompleto (forse Discourse se ne è mangiato un pezzo). Prova a rimetterlo all’interno del tag apposito (attivabile dalla barra degli strumenti mentre si sta scrivendo) in modo che risulti leggibile.

Inoltre, se non è il codice in senso stretto ad avere problemi, è meglio che tu descriva a parole l’idea risolutiva che hai seguito. 😉

---

<div class="post-metadata">

**Author:** ![D\_Lore](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/74df32/32.png) [@D\_Lore](https://forum.olinfo.it/u/D_Lore)\
**Post date:** [28 Luglio 2015, 1:13pm UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/3 "2015-07-28T13:13:48Z")

</div>

L’idea era quella di ordinare le lunghezze dei lati e iniziare a sommare i primi due poi il primo e il terzo ecct. finchè non trovavi che con uno dei lati successivi formava un triangolo impossibile e quindi tutti i successivi erano a loro volta impossibili dopodichè reiterare sommando secondo e terzo secondo e quarto e così via.  
Spero di essere stato più chiaro possibile 😓

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [29 Luglio 2015, 9:19am UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/4 "2015-07-29T09:19:54Z")

</div>

Provo a spiegare formalmente quanto hai scritto (correggimi se ho interpretato male):  
per ogni coppia (i, j) provi tutti i k finché una terna (i, j, k) non può formare un triangolo.  
A quel punto hai notato correttamente (osservazione fondamentale) che se (i, j, k) non forma un triangolo allora nessuna terna (i, j, k') con k' \> k può formare un triangolo.

Stimiamo la complessità computazionale del tuo algoritmo:

- ordinamento NlogN
- ricerca lineare del k più piccolo che non forma un triangolo (per ogni coppia): N \cdot N^2 = N^3

Come vedi, la complessità del tuo algoritmo è ancora N^3, insufficiente per risolvere gli ultimi subtask.  
Puoi immaginare di riuscire a trovare il k più piccolo, data una coppia, con una complessità inferiore a N?

---

<div class="post-metadata">

**Author:** ![D\_Lore](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/74df32/32.png) [@D\_Lore](https://forum.olinfo.it/u/D_Lore)\
**Post date:** [29 Luglio 2015, 4:05pm UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/5 "2015-07-29T16:05:58Z")

</div>

L’idea che mi è venuta è quella di partire dalla metà del vettore delle lunghezze in modo da ridurre la complessità in alcuni casi a N/2 ma i subtask continuano a darmi Execution timed out, documentandomi ho trovato la possibilità di usare la funzione binary\_search per trovare un numero in un vettore, è possibile utilizzarla anche per confrontare?

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [30 Luglio 2015, 9:05am UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/6 "2015-07-30T09:05:48Z")

</div>

Non direttamente, ma è possibile fare qualcosa di simile con `lower_bound` e `upper_bound`.  
Sei sulla strada giusta 😉

---

<div class="post-metadata">

**Author:** ![D\_Lore](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/74df32/32.png) [@D\_Lore](https://forum.olinfo.it/u/D_Lore)\
**Post date:** [31 Luglio 2015, 7:59am UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/7 "2015-07-31T07:59:18Z")

</div>

Utilizzando upper\_bound i subtask 3 (gli ultimi 3) in cui mi dava Execution timed out ora mi da Output isn’t correct mentre la subtask 4 continua ad andare fuori tempo.

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [31 Luglio 2015, 9:33am UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/8 "2015-07-31T09:33:09Z")

</div>

Risolvere il subtask 4 richiede un algoritmo N^2 mentre adesso stiamo progettando un algoritmo N^2logN, quindi è corretto che sia fuori tempo.  
Per il subtask 3 ti ricordo che per ogni coppia (i, j) devi cercare il più **piccolo** k per cui (i, j, k) **non** forma un triangolo. Se ti sembra di aver fatto ciò, puoi mettere il codice e vediamo cosa non va.

---

<div class="post-metadata">

**Author:** ![D\_Lore](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/74df32/32.png) [@D\_Lore](https://forum.olinfo.it/u/D_Lore)\
**Post date:** [31 Luglio 2015, 12:18pm UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/9 "2015-07-31T12:18:10Z")

</div>

> **[abc\_triangoli.cpp](https://www.dropbox.com/s/l5yk2blxecf9cz5/abc_triangoli.cpp?dl=0)**
>
> Shared with Dropbox

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [1 Agosto 2015, 2:08pm UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/10 "2015-08-01T14:08:40Z")

</div>

Il contatore s può eccedre 2^{31}-1. Usa un intero lungo al posto di un intero semplice.

---

<div class="post-metadata">

**Author:** ![D\_Lore](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/74df32/32.png) [@D\_Lore](https://forum.olinfo.it/u/D_Lore)\
**Post date:** [1 Agosto 2015, 4:45pm UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/11 "2015-08-01T16:45:19Z")

</div>

Perfetto dopo tanta fatica il subtask 3 è finalmente corretto ora però visto che sei così gentile ti chiedo un suggerimento per impostare la risoluzione del problema con complessità **N²**.

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [2 Agosto 2015, 12:48pm UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/12 "2015-08-02T12:48:17Z")

</div>

La base del ragionamento è sempre la stessa: supponendo che i numeri siano ordinati, per ogni (i, j) devi trovare il più piccolo k per cui (i, j, k) non forma un triangolo.

Considera due coppie (i, j\_1) e (i, j\_2) con j\_1 \< j\_2. È semplice osservare che k\_2 (inteso come il k di cui sopra per la terna (i, j\_2, k\_2)) sarà sicuramente maggiore di k\_1 (in (i, j\_1, k\_1)).

Ciò significa che se iteri su j devi solo controllare i numeri a partire dal k precedente che hai trovato.

Dal punto di vista della complessità computazione, per ogni i non impieghiamo mai più di N passaggi, il che ci porta a un algoritmo O(N^2).

---

<div class="post-metadata">

**Author:** ![D\_Lore](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/74df32/32.png) [@D\_Lore](https://forum.olinfo.it/u/D_Lore)\
**Post date:** [3 Agosto 2015, 8:50am UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/13 "2015-08-03T08:50:29Z")

</div>

Ora solo l’ultimo dei casi del subtask 4 va fuori tempo massimo ma questo credo che sia un mio problema. Ti lascio il link del nuovo programma così puoi controllarlo:

> **[abc\_triangoli.cpp](https://www.dropbox.com/s/l5yk2blxecf9cz5/abc_triangoli.cpp?dl=0)**
>
> Shared with Dropbox

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [3 Agosto 2015, 12:09pm UTC](https://forum.olinfo.it/t/abc-triangoli-execution-timed-out/191/14 "2015-08-03T12:09:45Z")

</div>

Il tuo codice mi pare esegua ancora N^2 volte una ricerca binaria con `upper_bound`…  
Resta quindi una complessità di N^2logN.

La soluzione N^2 non prevede l’uso della ricerca binaria.