Sto provando a risolvere il problema Marathon Training (run), ma il codice che ho scritto prende TLE in 4 casi (005, 009, 010, 036).
L’idea è che per ogni D[i], itero da D[i + 1] a D[N - 1]: quando trovo un valore che è più grande di tutti i precedenti fino a D[i] compreso, ho trovato una sequenza valida e aggiorno il risultato; se, invece, trovo un valore che è più piccolo di D[i], torno al ciclo esterno.
Il ciclo esterno si interrompe se non è più possibile, partendo da i, trovare una sequenza più lunga dell’attuale risultato.
#include <bits/stdc++.h>
int main()
{
std::ifstream ifs("input.txt");
std::ofstream ofs("output.txt");
std::ios::sync_with_stdio(false);
ifs.tie(0);
int N = 0;
ifs >> N;
std::vector<int> distances;
for(int i = 0, D; i < N; ++i) {
ifs >> D;
distances.push_back(D);
}
int ret = 1;
for(int i = 0; N - i > ret; ++i) {
int mx = 0;
for(int j = i + 1; j < N; ++j) {
if(distances[j] < distances[i]) break;
if(distances[j] >= mx) {
mx = distances[j];
if(j - i + 1 > ret) {
ret = j - i + 1;
}
}
}
}
ofs << ret;
return 0;
}
L’ho risolto tempo fa e non ricordo tutto chiaramente ma, a grandi linee, ho lavorato trovando inizialmente i valori minimi mini[i] dove mini[i] è il valore sotto il quale non scende nessuno dei D che vengono prima di D[i] i compreso. Poi ho creato le coppie {D[i],i]} e le ho ordinate decrescenti (occhio ai valori uguali di D).
Infine per ogni massimo ho trovato il minimo che lo precede, trovato la lunghezza, marcato come visitata l’intera gamma in modo da scartare l’elaborazione di massimi che cadono in gamme già visitate. termino quando la somma dei buchi liberi è inferiore uguale alla gamma già trovata.
In ogni caso i primi 3 test case che ti danno TLE appartengono al subtask con D<=1 e possono essere gestiti rapidamente in maniera diversa.
Ci possono essere accorgimenti per velocizzare il tutto tipo scartare una sequenza iniziale decrescente. (comunque direi che le streaks non si sovrappongono)
Comunque con una piccola modifica il tuo codice fa 100 (in 60ms circa) basta che dopo aver trovato uno streak che va da i fino a j riparti da j+1 e non da i+1:
.......
int ret = 1;
int k;
for(int i = 0; N - i > ret; ++i) {
int mx = 0;
k=i;
for(int j = i + 1; j < N; ++j) {
if(distances[j] < distances[i]) break;
if(distances[j] >= mx) {
mx = distances[j];
k=j;
if(j - i + 1 > ret) {
ret = j - i + 1;
}
}
}
i=k;
}
.....
Il tuo codice dà come streak max l’intervallo [2.3] mentre quello corretto è [4,7].
Considerare il bigger in assoluto per determinare lo streak max funziona probabilmente in quasi tutti i testcase tranne, forse, per il 038 e nell’esempio dato. Devi, quindi, cercare il bigger che ti consente di ottenere lo streak max.
Deve essere l’approccio al task che non va per superare il testcase 038 perché modificando leggermente l’esempio dato con il seguente:
8
9 8 1 7 2 4 3 6
il codice dà sempre la stessa soluzione sbagliata [2,3] invece di [4,7].
continua a sbagliare anzi ora dà time limit exceeded in un altro caso, mi sta venendo in mente un altra soluzione, vedo se funziona oppure no.
Aggiornamento:
Non funziona, quindi proverò con la programmazione dinamica
Se può essere utile alla risoluzione del task, modificare la riga:
indmin = i;
con:
indmin = i - 1;
risolve il testcase 038 ma poi ne sbaglia altri compreso quello d’esempio.
