Aiuto per Lotteria di quadri (abc_quadri)

Ciao a tutti, ho bisogno di aiuto per risolvere il problema Lotteria di quadri.
output corretti ma molti vanno in time limit exceed, come posso ottimizzare il codice
20/100

Ecco il mio codice:
#include
#include
using namespace std;

int quadri(int N, long long M, int l) {
vectorV(N);
for(int i=0;i<N;i++) {
V[i]=l[i];
}
int B=N;
long long sum=0;
for(int j=0;j<N;j++) {
for(int i=0;i<=j;i++) {
sum=accumulate(V.begin()+i,V.end()-j+i,0);
if(sum>M) {
B–;
break;
}
}
}
return B;
}

Grazie mille in anticipo!

Ciao, questo problema l’ho risolto un po’ di tempo fa e quindi proverò ad aiutarti e se non capisci qualcosa prova ad approfondire su internet.
Come hai notato il tuo codice fa TLE, questo è dovuto alla sua complessità temporale che se non erro è O(N^3): te hai implementato due cicli for annidati (complessità di O(N^2) con al suo interno std::accumulate (O(N)) → O(N ^ 2) * O(N) = O(N ^ 3).

Una complessità cubica con N che può arrivare a 200 000 non è fattibile (se provi a fare 200 000 ^ 3 fa 8.000.000.000.000.000, un numero di operazioni troppo grande: tieni conto che il limite di tempo è 0.3 secondi e in un secondo si eseguono circa 10^8 operazioni…).

tecnica da utilizzare

Se vuoi risolvere questo problema ti consiglio di guardare la tecnica “sliding window” (finestra scorrevole): Tecnica della finestra scorrevole - GeeksforGeeks.

Questa tecnica permette la risoluzione in tempo lineare (O(N)) di molti problemi che richiedono di trovare il massimo / minimo subarray che rispetti determinate condizioni.
Dopo aver risolto quadri puoi allenarti ancora su questa tecnica sul problema Training - Christmas Lights (olinfo.it), che è molto simile.
P.s. per incollare del codice usa l’opzione “testo preformattato” (il simbolo </> )

non riesco lo stesso ho provato a fare la sliding windows come mi hai detto tu e fatto anche un altro controllo, come posso risolvere?

#include <numeric>
#include <vector>
using namespace std;

int quadri(int N, long long M, int l[]) {
   vector<int>V(N);
   for(int i=0;i<N;i++) {
      V[i]=l[i];
   }
   int B=N;
   int temp=0;
   long long sum=0;
   int a=0,b=0;

   for(int j=0;j<N;j++) {
      temp=0;
      sum=accumulate(V.begin(),V.begin()+B,0);
      for(int i=0;i<=j;i++) {
         if(sum>M) {
            B--;
            break;
         }
         sum-=V[i];
         sum+=V[i+B];
         temp++;
      }
      if(temp==j+1)return B;
   }
   return B;
};

ok ho risolto il mio problema , grazie mille :slight_smile:

Ciao, scrivo non per il problema lotteria di quadri ma piuttosto per chiedere aiuto riguardo a come poter scrivere messaggi: è da mezzora che cerco di capire come fare ma non trovo il modo (sono solo riuscito a rispondere a messaggi già esistenti come sto facendo ora), non è che qualcuno potrebbe dirmi come posso fare? grazie mille

Ok, se intendi creare nuovi post per chiedere informazioni, farsi aiutare o condividere qualcosa su un problema, devi solo andare nella homepage del forum e clicchi l’opzione “crea nuovo argomento” e, dopo aver selezionato le varie info del post (se è un aiuto oppure chiarimento o una segnalazione…) scrivi quello che devi scrivere e aspetti per delle risposte…
Spero tu abbia capito


non me lo da il tasto che posso fare?

Riprova ora.

adesso me lo da ti ringrazio!