Crash su mostra e multicore

Aiuto
1

Provando a risolvere i problemi mostra e multicore (dal sito delle territoriali, con codeblocks) ho ottenuto due soluzioni che mi sono sembrate corrette (ed effettivamente sono corrette per molteplici subtask) ma che dopo un certo numero di subtask crashano.

La seguente soluzione di mostra

#include <iostream>

using namespace std;

int main(){
    freopen("input_14.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int T, N, M;
    cin >> T;
    for (int t = 0; t < T; t++){
        cout << endl;
        cin >> N >> M;
        int V[N], G[M];
        for (int i = 0; i < N; i++){
            cin >> V[i];
        }
        for (int i = 0; i < M; i++){
            cin >> G[i];
        }
        int h, f[N][M], m;
        bool l = 0;
        for (int i = M-1; i >= 0; i--){
            if (V[N-1] < G[i]){
                h = i;
                l = 1;
                break;
            }
        }
        if (l == 0){
            h = -1;
        }
        for (int i = 0; i <= h; i++){
            f[N-1][i] = 2;
        }
        for (int i = h+1; i < M; i++){
            f[N-1][i] = 1;
        }
        for (int i = N-2; i >= 0; i--){
            for (int j = 0; j < M; j++){
                m = f[i+1][j]+1;
                for (int x = j; x < M; x++){
                    if (G[x] > V[i]){
                        if (x == M-1){
                            m = max(m, 1+N-i);
                        }
                        else {
                            m = max(m, f[i+1][x+1]+2);
                        }
                    }
                }
                f[i][j] = m;
            }
        }
        cout << "Case #" << t+1 << ": " << f[0][0];
    }
}

funziona per i primi 13 subtask ma crasha per il 14esimo.

La seguente soluzione di multicore

    #include <iostream>

    using namespace std;

    struct obj {
        int v, w;
    };

    int main(){
        freopen("input_12.txt", "r", stdin);
        freopen("output.txt", "w", stdout);

        int T;
        cin >> T;
        for (int t = 0; t < T; t++){
            cout << endl;
            long long int N, M;
            cin >> N >> M;
            obj O[N];
            for (int i = 0; i < N; i++){
                cin >> O[i].v >> O[i].w;
            }
            int f[M+1][2];
            for (int i = 0; i <= M; i++){
                if (O[0].w <= i){
                    f[i][0] = O[0].v;
                }
                else {
                    f[i][0] = 0;
                }
            }
            for (int i = 1; i < N; i++){
                for (int j = 0; (j < O[i].w)&&(j <= M); j++){
                    f[j][1] = f[j][0];
                }
                for (int r = 0; r <= M-O[i].w; r++){
                    f[r+O[i].w][1] = max(f[r+O[i].w][0], O[i].v + f[r][0]);
                }
                for (int i = 0; i <= M; i++){
                    f[i][0] = f[i][1];
                }
            }
            cout << "Case #" << t+1 << ": " << f[M][0];
        }
    }

funziona per i primi 4 subtask ma crasha per il quinto. Questo crash mi rende particolarmente perplesso in quanto ho usato una soluzione pressoché identica a quella che ho usata per ois_lootboxes sulla piattaforma di allenamento, dove però ho fatto 100/100.

Non riesco a capire perché questi crash avvengono. Qualcuno me lo saprebbe spiegare?
Grazie in anticipo.

2

Il crash è dovuto al fatto che le tue soluzioni sono troppo lente per entrambi i problemi, e, se non sbaglio, almeno in windows, i terminali in cui viene eseguito il programma si chiudono in automatico dopo qualche secondo. Alle territoriali non ci sono limiti di tempo stretti come su training olinfo o su altre gare, anche se i programmi devono comunque finire di eseguire prima della fine della gara, quindi forse in qualche caso potrebbe servirti trovare un modo per disattivare la chiusura automatica( anche se di solito non serve). In ogni caso, per entrambi i problemi esistono soluzioni più efficienti che dovresti cercare di implementare( per multicore c’è la soluzione su wiki olinfo chiodini, l’altro è abbastanza standard, comunque si fa in O(N*M), senza il ciclo più interno per capirsi)

1 Mi Piace
3

Direi che sia questa la soluzione perché, per quanto siano lenti, i miei codici rientrerebbero tranquillamente nei tempi di una gara territoriale e ho notato che crashano dopo solo circa 5 secondi.
Scusatemi se insisto per la mia ignoranza in materia, ma qualcuno sa come disattivare questa chiusura automatica? E per caso questo problema può sussistere nelle vere e proprie gare o l’uso di sistemi operativi diversi lo previene?

4

Attento alle dimensioni degli input. Nel caso di multicore, la tua soluzione ha una complessità pari a O(N*M), dove M corrisponde al B del testo, quindi il numero totale di operazioni massimo è circa 10^11. Considerando che in media si riescono a fare 10^7 operazioni al secondo, il tuo programma potrebbe forse riuscire a fare un solo testcase dei più lunghi nei tempi delle territoriali( 3h). Qualcosa di simile vale anche per mostra( quella forse potrebbe passare, ma comunque sarebbe piuttosto tirata). Il discorso di disattivare o allungare i tempi di spegnimento( prova a guardare nelle impostazioni di codeblocks, prova a eseguire il file direttamente da terminale, io ora non riesco a provare perché non ho codeblocks installato), può tornare utile con un numero di operazioni pari al massimo a 10^9, in modo da stare comunque dentro i tempi delle territoriali.

1 Mi Piace
5

Effettivamente sì, i miei codici sono molto più lenti di quanto credessi. Grazie mille.
Per quanto riguarda il discorso di allungare o disattivare i tempi di spegnimento, c’è qualcuno che fa uso di Windows e codeblocks che mi possa aiutare?

6

Ok, ho risolto il problema! Il fatto è che i miei codici usavano troppa memoria (effettivamente in entrambi avevo creato degli insiemi mastodontici per realizzare dp, ci sarei dovuto arrivare prima…). Con alcune modifiche entrambi i codici hanno funzionato correttamente. Grazie comunque per l’aiuto!