abc_triangoli Execution timed out

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

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. :wink:

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 :sweat:

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?

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?

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

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.

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.

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

1 Mi Piace

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

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

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:

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.