Stavo provando a fare christmas lights usando le sliding window (sono ancora agli inizi di questa tecnica e nn so se il procedimento sia corretto), fatto sta che con questo codice (che sembra corretto) mi dà alcuni testcases corretti mentre gli altri tutti TLE, ma nn so da che punto partire x ridurre il tempo…
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int N, C;
cin >> N >> C;
vector<int> L(N);
bool cond=false;
int posoffirstzero;
for (int i = 0; i < N; i++) {
cin >> L[i];
}
//vector to mark colours' positions:
vector<int> V(C, 0);
int conta=1, n;
int inizio=0, fine=0;
int firstnumber=L[0];
//1st window with every colours:
for(int i=1; i<N; i++)
{
n=L[i];
if(V[n]==0 and n!=firstnumber) //add new colours and increase conta
{
V[n]=i;
conta++;
}
else if(V[n]!=0 or n==firstnumber)
{
V[n]=i; //otherwise(the colour is already in) save the max position of the colour
}
fine++;
if(conta==C)
break;
}
//reduce first window start:
auto it =min_element(V.begin(), V.end());
inizio=*it;
int iniziomin=inizio;
int finemin=fine;
int min=fine-inizio+1; //first window's length (+1 'cause the windows contains the extremes too)
//sliding window
for(int i=inizio; i<N; i++)
{
fine++; //increase the window's range
n=L[fine-1];
V[n]=i;
//double check the window's size:
auto it2 =min_element(V.begin(), V.end());
inizio=*it;
//if it's bigger, do nothing, otherwise modify the minrange:
if(fine-inizio<min)
{
min=fine-inizio+1;
iniziomin=inizio;
finemin=fine;
}
}
cout<<min;
return 0;
}
Ah, su suggerimento di qualcuno vorrei specificare tre cose: l’identazione sbagliata è pk nn riuscivo a caricare il file e copiando e incollando veniva così; poi, i commenti in inglese sono così pk avevo voglia; e il codice sbagliato è pk sono agli inizi…
Cmq ringrazio in anticipo chi mi aiuta
ciao Leonardo, visto che hai ascoltato le mie minacce i miei consigli:
il tuo codice non fa TLE, ma runtime error, nella schermata della submission si vede scritto: “execution killed” questo e’ perche nel tuo codice prova ad accedere ad una cella che non esiste. In particolare la variabile fine in questo pezzo:
fine++; //increase the window's range
n=L[fine-1];
raggiunge il valore N+1, quindi provi ad accedere a L[N], che non esiste (me ne sono accorta mettendo una if e provando ad eseguire sul primo caso di esempio).
Per accorgerti in fretta di queste cose ti consiglierei di smettere di usare DevC++ e installare Linux, su cui si possono usare i sanitizer, che sono sostanzialmente degli strumenti che effettuano dei controlli su questo genere di problemi permettendoti di individuarli molto piu in fretta, per esempio specificandoti a che riga provi ad accedere ad un campo inesistente (quando vuoi installare Linux ovviamente sai dove trovarmi ;)).
Per quanto riguarda l’idea dietro al tuo codice prova a sistemare il problema di cui ti ho parlato poi se c’e’ ancora qualcosa che non funziona manda pure la versione aggiornata.
Allora, come mi hai suggerito ho risolto il problema mettendo un if(fine<N) fine++; e mi dà 100/100, però, stranamente vanno tutti i testcase, tranne il primo esempio (dà ouput 2 al posto di 5);
Non che sia importante, però nn ne capisco il motivo…
