Aiuto implementazione Sliding Window lotteria quadri 60/100 Execution Timed Out

Aiuto
1

Buongiorno, é da ieri sera che provo a risolvere quadri con questo codice:

struct window {
    int wStart;
    int wEnd;
    long long wSum = 0;
};

// Modifica la somma della sliding window
void calculate_sum(window& sw, int V[]) {
    long long sum = 0;

    for (int i = sw.wStart; i < sw.wEnd; ++i)
        sum += V[i];

    sw.wSum = sum;
}

// N: numero quadri, M: massimale somma sliding window, V: array di quadri
int quadri(int N, long long M, int V[]) {
    if (N == 1) return (V[0] <= M); // 1 o 0

    // Subtest 2
    window sub2 = {0, N, 0};
    calculate_sum(sub2, V);
    if (M > sub2.wSum) return N;

    // Controlliamo che B = 1 sia possibile, altrimenti ritorna 0
    for(int i = 0; i < N; ++i)
        if (V[i] > M) return 0;

    // Troviamo il massimo locale per il primo window e settiamo il bound massimo, da qui puo solo scendere
    int B = N;

    window w = {0, 1, 0};

    while (w.wSum <= M) {
        w.wEnd += 1;
        calculate_sum(w, V);
    }

    w.wEnd -= 1;
    calculate_sum(w, V);

    if (w.wEnd-w.wStart < B) B = w.wEnd-w.wStart;

    // Ripetiamo il procedimento per ogni altra window
    for(int i = 1; i < N-B+1; ++i) {
        w = {i, i+B, 0};
        calculate_sum(w, V);

        if (w.wSum > M) B--;
    }

    return B;
}

image

Il codice mi da tutto corretto tranne il subtask 5 dove va in Execution time out. L’idea di come migliorarlo l’ho giá in mente, ovvero anziché ricalcolarmi la somma di ogni window potrei semplicemente sottrarre l’inizio della window precedente e sommare il nuovo valore di fine della window.

Il problema é che quando l’ho provato ad implementare in questo modo:

// Meccanismo di sliding window
for(int i = 1; i < N-B; ++i){
    sum = sum - V[i-1] + V[i+B-1];
    if (sum > M) {
        B--;
        sum -= V[i+B-1];
    }
}

Mi vengono assegnati solo 15/100 punti perché alcuni output sono errati ed alcuni test mi dicono ‘Execution killed (could be triggered by violating memory limits)’

Grazie in anticipo per l’aiuto…

2

Se aggiungi questo anche se lo correggi sei sicuro che il codice non vada in TLE (Execution timed out)?

Esiste un modo per risolvere il problema in tempo lineare, scorrendo tutto l’array una sola volta.
Per capire meglio puoi andarti a cercare questo argomento: “Two pointers method”

1 Mi Piace
3

Buon pomeriggio, grazie per la risposta! Ho avuto tempo di guardarmi il two pointers method solo ora, ho riscritto il codice ed é uscito cosí finora:

int quadri(int N, long long M, int V[]) {
    if (N == 1) return (V[0] <= M); // 1 o 0

    int B = N;

    int p1 = 0, p2 = 0;

    int sum = V[p1];

    int tempB = 0;
    while (true) {
        if (sum > M) {
            tempB = p2 - p1; // ??
            if (tempB < B) {
                B = tempB;
                tempB = 0;
            }

            sum -= V[p1];
            p1++;
        } else {
            if (tempB > B) {
                sum -= V[p1];
                p1++;
                tempB = p2 - p1;
            } else {
                p2++;
                if (p2 >= N) break;

                tempB = p2 - p1;
                sum += V[p2];
            }
        }
    }

    return (B >= 0) ? B : 0;
}

Il problema é che prendo ancora 60/100, ma stavolta nell’ultimo subtask mi dice “Output is not correct”.
Devo dire che peró la complessitá computazionale é scesa drasticamente (0.4s → 0.007s).

Cosa sto sbagliando secondo voi? (Secondo me in qualche caso speciale c’é un overlapse tra p1 e p2)

4

… ok mi sono appena accorto che sono sciocco io, visto che le somme di Vi possono essere parecchio grandi serve usare long long int anziché int per la variabile sum