Cicla e moltiplica (shiftmul) 40/100 - TLE e Memory Limit

Salve a tutti, questo è il primo topic che apro (fino ad ora ne avevo sempre trovati altri già scritti in cui riuscivo a trovare la soluzione, ma su questo non ci sono riuscito).
Sto provando a fare questo problema da 3 giorni, ma non riesco a capire come ridurne la complessità.
Inoltre, mi dà anche problemi sulla memoria occupata, ma di quello sono meno preoccupato, di solito è per colpa di qualche variabile non necessaria o qualcosa di simile.

(se è poco comprensibile qualche passaggio chiedete pure, ho cercato di mettere commenti per ogni operazione, ma non so se bastano)

#include <iostream>
#include <vector>

#define MODULO 1000000007

using namespace std;

// struttura per poter ciclare il vettore in tempo costante (ha un indice che si riduce di D a ogni ciclo)
struct vettoreConIndice {
    vector<int> dati;
    int indice = 0;
    int elementi = 0;

    vettoreConIndice() {}

    vettoreConIndice(vector<int> A, int N) { // O(1)
        dati = A;
        elementi = N;
    }

    void cicla(int x) { // O(1)
        indice -= x;
        if (indice < 0) {
            indice += elementi;
        }
    }

    void impostaIndice(int x) { // O(1)
        indice = x;
    }

    int valore(int x) { // O(1)
        int pos = (x + indice) % elementi;
        return dati[pos];
    }
};

// algoritmo fast modular exponentiation in O(log e)
int potenzaVeloceModulare(int n, int e) {
    int ris;

    if (e == 0) {
        return 1;
    }
    else if (e == 1) {
        return n;
    }
    else if (e % 2 == 0) {
        ris = potenzaVeloceModulare(n, e / 2);
        return ((long long)ris * ris) % MODULO;
    }
    else{
        ris = potenzaVeloceModulare(n, e / 2);
        return ((((long long)ris * ris) % MODULO) * n) % MODULO;
    }
    
}

int MCD(int a, int b) { // O(log(a*b)
    if (b == 0) {
        return a;
    }

    return MCD(b, a % b);
}

int mcm(int a, int b) { // O(1) solo la funzione mcm, con le funzioni che richiama diventa O(log(a*b) + log(MODULO))
    return ((((long long)a * b) % MODULO) * potenzaVeloceModulare(MCD(a, b), MODULO - 2)) % MODULO;
}

vettoreConIndice ciclo;
int N;
int D;

int executePos_rec(int pos, int K, int indice) { // O(K)
    ciclo.impostaIndice(indice);
    if (K == 1) {
        return ciclo.valore(pos);
    }
    else {
        ciclo.cicla(D);
        return ((long long)executePos_rec(pos, K - 1, ciclo.indice) * ciclo.valore(pos+D)) % MODULO;
    }
}

vector<int> execute(int N_temp, int K, int D_temp, vector<int> A) {
    N = N_temp;
    D = D_temp;
    ciclo = vettoreConIndice(A, N);
    vector<int> B(N);

    if (D == 0) {
        for (int i = 0; i < N; i++) { // O(N) * O(log K) = O(N*log(K))
            B[i] = ciclo.valore(i);
            B[i] = potenzaVeloceModulare(B[i], K);
        }
    }
    else {
        long long N_totale = mcm(N, D); // O(log(N*D)), N_totale trova il numero minimo che dovrebbe essere N per fare un giro completo
        int K_perCiclo = N_totale / D; // moltiplicazioni per ciclo
        int esponente = K / K_perCiclo; // volte in cui si ripete il ciclo

        if (K_perCiclo <= K){

            int numeriSeparati = N / K_perCiclo; // quante posizioni devono avere risultati diversi
            vector<int> valoriNumeriSeparati(numeriSeparati);
            
            for (int i = 0; i < numeriSeparati; i++) { // O(N*K_perCiclo*log(esponente))
                valoriNumeriSeparati[i] = potenzaVeloceModulare(executePos_rec(i, K_perCiclo, 0), esponente);
                for (int j = i; j < N; j += numeriSeparati) {
                    B[j] = ((long long)valoriNumeriSeparati[i] * executePos_rec(j, K % K_perCiclo, 0)) % MODULO;
                }
            }
        }
        else {
            // O(N*K), se il ciclo ha più moltiplicazioni di quante richieste
            // (es: per completare un ciclo ci vogliono 10 moltiplicazioni, ma sono richieste 2)
            // calcola il risultato normalmente
            for (int i = 0; i < N; i++) {
                B[i] = executePos_rec(i, K, 0);
            }
        }
    }

    return B;
}


int main() {
    // TEST 1
    vector<int> tmp = execute(4, 5, 0, {
        2, 1, 10, 3
        });
    for (int i = 0; i < 4; i++) {
        cout << tmp[i] << " ";
    }
    cout << "\n";

    // TEST 2
    tmp = execute(5, 2, 2, {
        3, 1, 5, 1, 2
        });
    for (int i = 0; i < 5; i++) {
        cout << tmp[i] << " ";
    }
}

Come è scritto nel codice, la complessità attuale di questo algoritmo nel peggiore dei casi è O(N⋅K) o (non so quale dei due è peggio, a me sembrano uguali) O(N⋅(K_perCicli+log(esponente))) in cui, però, più ‘K_perCicli’ aumenta, più ‘esponente’ diminuisce.

Sono consapevole che queste complessità sono troppo grandi per le assunzioni del problema, ma non ho idea di come migliorarle, potete darmi una mano? Grazie in anticipo

C’è qualcosa che non torna perché nel terzo caso d’esempio:

5 8 2
3 1 5 1 2

il codice mi restituisce:

80 1600 720 160 6000

invece di:

90 300 450 60 900

È vero, questo è quello che succede quando esegui solo 2 casi di test su 3 durante il debug…
La funzione ciclo.valore(pos+D) restituiva un risultato errato che cambiava tutti i dati successivi, ora dovrebbe essere corretto:

#include <iostream>
#include <vector>

#define MODULO 1000000007

using namespace std;

// struttura per poter ciclare il vettore in tempo costante (ha un indice che si riduce di D a ogni ciclo)
struct vettoreConIndice {
    vector<int> dati;
    int indice = 0;
    int elementi = 0;

    vettoreConIndice() {}

    vettoreConIndice(vector<int> A, int N) { // O(1)
        dati = A;
        elementi = N;
    }

    void cicla(int x) { // O(1)
        indice -= x;
        if (indice < 0) {
            indice += elementi;
        }
    }

    void impostaIndice(int x) { // O(1)
        indice = x;
    }

    int valore(int x) { // O(1)
        int pos = (x + indice) % elementi;
        return dati[pos];
    }

    int valore(int x, int indice_passato) { // O(1)
        int pos = (x + indice_passato) % elementi;
        return dati[pos];
    }
};

// algoritmo fast modular exponentiation in O(log N)
int potenzaVeloceModulare(int n, int e) {
    int ris;

    if (e == 0) {
        return 1;
    }
    else if (e == 1) {
        return n;
    }
    else if (e % 2 == 0) {
        ris = potenzaVeloceModulare(n, e / 2);
        return ((long long)ris * ris) % MODULO;
    }
    else{
        ris = potenzaVeloceModulare(n, e / 2);
        return ((((long long)ris * ris) % MODULO) * n) % MODULO;
    }
    
}

int MCD(int a, int b) { // O(log(a*b)
    if (b == 0) {
        return a;
    }

    return MCD(b, a % b);
}

int mcm(int a, int b) { // O(1) solo la funzione mcm, con le funzioni che richiama diventa O(log(a*b) + log(MODULO))
    return ((((long long)a * b) % MODULO) * potenzaVeloceModulare(MCD(a, b), MODULO - 2)) % MODULO;
}

vettoreConIndice ciclo;
int N;
int D;

int executePos_rec(int pos, int K, int indice) { // O(K)
    ciclo.impostaIndice(indice);
    if (K == 1) {
        return ciclo.valore(pos);
    }
    else {
        ciclo.cicla(D);
        return ((long long)executePos_rec(pos, K - 1, ciclo.indice) * ciclo.valore(pos, indice)) % MODULO;
    }
}

vector<int> execute(int N_temp, int K, int D_temp, vector<int> A) {
    N = N_temp;
    D = D_temp;
    ciclo = vettoreConIndice(A, N);
    vector<int> B(N);

    if (D == 0) {
        for (int i = 0; i < N; i++) { // O(N) * O(log K) = O(N*log(K))
            B[i] = ciclo.valore(i);
            B[i] = potenzaVeloceModulare(B[i], K);
        }
    }
    else {
        long long N_totale = mcm(N, D); // O(log(N*D)), N_totale trova il numero minimo che dovrebbe essere N per fare un giro completo
        int K_perCiclo = N_totale / D; // moltiplicazioni per ciclo

        if (K_perCiclo <= K){
            int esponente = K / K_perCiclo; // volte in cui si ripete il ciclo
            int numeriSeparati = N / K_perCiclo; // quante posizioni devono avere risultati diversi
            vector<int> valoriNumeriSeparati(numeriSeparati);
            
            for (int i = 0; i < numeriSeparati; i++) { // O(N*K_perCiclo*log(esponente))
                valoriNumeriSeparati[i] = potenzaVeloceModulare(executePos_rec(i, K_perCiclo, 0), esponente);
                for (int j = i; j < N; j += numeriSeparati) {
                    B[j] = ((long long)valoriNumeriSeparati[i] * executePos_rec(j, K % K_perCiclo, 0)) % MODULO;
                }
            }
        }
        else {
            // O(K*N), se il ciclo ha più moltiplicazioni di quante richieste
            // (es: per completare un ciclo ci vogliono 10 moltiplicazioni, ma sono richieste 2)
            // calcola il risultato normalmente
            for (int i = 0; i < N; i++) {
                B[i] = executePos_rec(i, K, 0);
            }
        }
    }
    
    return B;
}


int main() {
    // TEST 1
    vector<int> tmp = execute(4, 5, 0, {
        2, 1, 10, 3
        });
    for (int i = 0; i < 4; i++) {
        cout << tmp[i] << " ";
    }
    cout << "\n";

    // TEST 2
    tmp = execute(5, 2, 2, {
        3, 1, 5, 1, 2
        });
    for (int i = 0; i < 5; i++) {
        cout << tmp[i] << " ";
    }
    cout << "\n";

    // TEST 3
    tmp = execute(5, 8, 2, {
        3, 1, 5, 1, 2
        });
    for (int i = 0; i < 5; i++) {
        cout << tmp[i] << " ";
    }
}

Comunque rimane il problema della complessità a livello di tempo, sai come risolverlo?

Ad ogni modo la tua complessità è O(K*N) che non ti evita di andare in TLE. Devi rivedere un po’ la strategia del tuo algoritmo perché la complessità dovrebbe risultare O(N).
Prova a considerare il problema con questi 2 esempi:

5 6 1
1 2 3 4 5
5 9 1
1 2 3 4 5

Ci ho pensato un po’, ma continuo a non capire quale soluzione può avere quella complessità.
Cioè, per farti capire, la mia soluzione in questi 2 casi farebbe:

  1. Inserire in tutte le posizioni del vettore B l’elemento 1*5*4*3*2 (in questo ordine) elevato al numero di volte in cui si ripete (che qui è uguale a 1), quindi 120^1

  2. Per ogni elemento (e per ogni K rimasta), continuare le moltiplicazioni singolarmente, quindi ogni elemento diventerebbe 120*1, 120*2, 120*3, 120*4, 120*5 (in questo caso la K rimasta era 1, K%K_perCiclo = 6%5).
    Nel secondo caso sarebbe stato 120*1*5*4*3, 120*2*1*5*4, ecc. (qui K%K_perCiclo = 9%5)

So che non puoi darmi la soluzione direttamente, ma neanche un aiuto su come arrivarci?

Aggiornamento: ho risolto il problema del memory limit, come avevo detto nel primo messaggio era solo un problema di distrazione in un if, questo:

doveva essere uguale a questo:

    ciclo.impostaIndice(indice);
    if (K < 1) {
        return 1;
    }
    else if (K == 1) {
        return ciclo.valore(pos);
    }

perché ovviamente se deve fare 0 moltiplicazioni deve ritornare 1, non andare all’infinito con i numeri negativi e sforare il limite di ricorsioni.

La situazione attuale è questa (sono solo questi che danno errore):
Screenshot 2024-06-13 221430

Modifica: forse ci sono, credo di essere riuscito a trovare una soluzione con complessità O(N*log(K)) che è estremamente più efficiente di quella attuale (per ora è solo a livello di logica, domani la scrivo in codice). Non so come si possa scendere a O(N), ma se domani funziona questa non mi interessa più, dovrebbe comunque riuscire a passare i TLE

PROBLEMA RISOLTO


Screenshot 2024-06-14 122502

Continuo a non avere idea di come si sarebbe potuto fare in O(N), ma per ora questa soluzione in O(N*log(K)) è accettabile sia per il tempo sia per la memoria occupata, quindi non mi interessa più (se qualcuno vuole dirmela la accetto volentieri, ma non ci ragionerò più su per conto mio).

Se qualcuno invece fosse ancora in difficoltà, provate a ragionare a come trovare in tempo costante la soluzione (di una posizione) quando K è uguale a una potenza di 2 (es. 2, 4, 8, 16) e poi a come si potrebbero combinare tra loro (es. quando K = 10 bisogna combinare la soluzione di 8 e di 2)