# Marathon Training (run) - TLE in 4 testcases

**URL:** <https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734>\
**Category:** Aiuto\
**Created:** [18 Ottobre 2021, 12:09pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734 "2021-10-18T12:09:53Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![guglielmo.boi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/ebca7d/32.png) [@guglielmo.boi](https://forum.olinfo.it/u/guglielmo.boi)\
**Post date:** [18 Ottobre 2021, 12:09pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/1 "2021-10-18T12:09:54Z")

</div>

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.

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [18 Ottobre 2021, 5:37pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/2 "2021-10-18T17:37:03Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [18 Ottobre 2021, 9:57pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/3 "2021-10-18T21:57:06Z")

</div>

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:

```auto
    .......
    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;
    }
  .....

```

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [3 Maggio 2022, 2:54pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/4 "2022-05-03T14:54:21Z")

</div>

Io ho fatto un algoritmo, sbaglia soltanto il testcase 038, che non riesco ancora a capire quale sia. Allego il codice:

```auto
/*

 * NOTE: it is recommended to use this even if you don't

 * understand the following code.

 */

#include <iostream>

#include <vector>

#include <cassert>

#include <algorithm>

using namespace std;

// input data

int N;

vector<int> D;

int main() {

// uncomment the following lines if you want to read/write from files

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

    assert(cin >> N);

    D.resize(N);

    int bigger = -1;

    int fermo = 0;

    int i = -1;

    for (int &d : D) {

        assert(cin >> d);

       

        i++;

       

        fermo = (bigger <= d) ? i : fermo;

        bigger = (d > bigger) ? d : bigger;

       

    }

   

    long long streak = 0;

    long long maxstr = 0;

    int indmin = 0;

    int indmax = 0;

    //cout << bigger << endl;

    for(int i = 1; i < N; i++){

        if(D[indmin] > D[i]){

            maxstr = (maxstr < streak) ? streak : maxstr;

            streak = 0;

            indmin = i;

            indmax = i;    

        } else {

            indmax = (D[indmax] <= D[i]) ? i : indmax;            

        }  

        streak = indmax - indmin;

        maxstr = (streak >= maxstr) ? streak : maxstr;  

        if(fermo == i){

            indmin = i + 1;

            indmax = i + 1;

        }  

    }  

    streak = indmax - indmin;  

    maxstr = (streak > maxstr) ? streak : maxstr;

    maxstr++;  

    cout << maxstr << endl; // print the result

    return 0;

}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [4 Maggio 2022, 10:09am UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/5 "2022-05-04T10:09:32Z")

</div>

Prova con questo input:  
8  
2 8 1 7 2 4 3 6

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.

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [4 Maggio 2022, 11:15am UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/6 "2022-05-04T11:15:43Z")

</div>

perfetto, risolvo il problema

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [4 Maggio 2022, 12:08pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/7 "2022-05-04T12:08:20Z")

</div>

ho risolto anche questo problema, ma il codice continua a sbagliare quel singolo testcase allego il codice adesso

```auto
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;

// input data
int N;
vector<int> D;

int main() {
// uncomment the following lines if you want to read/write from files
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    assert(cin >> N);
    D.resize(N);
    int bigger = -1; 
    int fermo = 0; 
    int i = -1; 
    for (int &d : D) {
        assert(cin >> d);
        
        i++; 
        
        fermo = (bigger <= d) ? i : fermo; 
        bigger = (d > bigger) ? d : bigger; 
        
    }
    
    long long streak = 0; 
    long long maxstr = 0;
    int indmin = 0;
    int indmax = 0;
    //cout << bigger << endl; 
    for(int i = 1; i < N; i++){
        if(D[indmin] > D[i]){
            maxstr = (maxstr < streak) ? streak : maxstr;
            streak = 0;
            indmin = i;
            indmax = i;    
        } else {
            indmax = (D[indmax] <= D[i]) ? i : indmax;             
        }   
        streak = indmax - indmin;
        maxstr = (streak >= maxstr) ? streak : maxstr;  
        if(fermo == i){
            indmin = i + 1; 
            indmax = i + 1; 
            bigger = -1;
            fermo = i + 1; 
            for(int l = N - 1; l > i; l--){
                fermo = (D[l] > bigger) ? l : fermo; 
                bigger = (D[l] > bigger) ? D[l] : bigger; 
            }
        }  
    }  
    streak = indmax - indmin;  
    maxstr = (streak > maxstr) ? streak : maxstr; 
    maxstr++;  
    cout << maxstr << endl; // print the result
    return 0;
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [4 Maggio 2022, 12:52pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/8 "2022-05-04T12:52:40Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [4 Maggio 2022, 1:17pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/9 "2022-05-04T13:17:42Z")

</div>

controllo e ti faccio sapere

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [4 Maggio 2022, 1:20pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/10 "2022-05-04T13:20:16Z")

</div>

ops era una svista avevo fatto partire il for da i = 1 e non da i = 0

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [4 Maggio 2022, 1:21pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/11 "2022-05-04T13:21:56Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [4 Maggio 2022, 2:19pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/12 "2022-05-04T14:19:08Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![GG4Gigadi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/54ee81/32.png) [@GG4Gigadi](https://forum.olinfo.it/u/GG4Gigadi)\
**Post date:** [4 Maggio 2022, 4:12pm UTC](https://forum.olinfo.it/t/marathon-training-run-tle-in-4-testcases/6734/13 "2022-05-04T16:12:45Z")

</div>

sono riuscito a fare 100/100, grazie comunque 🙂  
P.S avevo solo sottoposto per vedere se funzionasse e ho preso 100/100, non pensavo di prenderlo