Algobadge shiftmul 50/100

Ci mette troppo e ho provato di tutto, che altra strategia consigliate?

#include<bits/stdc++.h>
using namespace std;
const long long int mod=1000000007;

long long int power(long long int base, long long int esponente) {
    long long int result = 1;
    base%=mod;
        while (esponente>0) {
        if (esponente%2==1) {
            result=(result*base) % mod;
        }
        base = (base*base)%mod;
        esponente/=2;
    }
    return result;
}

vector<int> execute(int N, int K,int D, vector<int> A) {
    vector<int> B(N,1);
     if(D==0){
			for (int i = 0; i < N; ++i) {	
        			B[i] = power(A[i],K);
        		}
    }else{
     	for (int Q = 0; Q < K; ++Q) {
   			for(int i=0;i<N;i++){
   				B[i] = ((B[i]%mod)*(A[(i+D*Q)%N]%mod))%mod;
	    		}			    		
	}
}
    return B;
}
int main() {
    int N, K, D;
    cin >> N >> K >> D;
int u;
    vector<int> A(N);
    for (int x=0;x<N;x++){
    	    cin >> u;
    	    A[x]=u;
    }
    vector<int> B = execute(N, K, D, A);
    for (size_t i = 0; i < B.size(); ++i) {
        cout << B[i];
        if (i + 1 < B.size()) std::cout << " ";
    }
    cout <<endl;
}

La soluzione che hai mandato ha complessità O(NK) ed esegue pertanto circa 10^{15} operazioni nel caso pessimo. Considerato che alla meglio un computer normale riesce a fare al massimo circa 10^9 operazoni al secondo è facile vedere che questa soluzione non ha la minima possibilità di passare.

Esattamente che cosa hai provato per migliorare la complessitĂ  della tua soluzione?

Ho provato a risolverlo qualche mese fa e lo ho abbandonato poiche’ mi trovavo in un punto di stallo. Onestamente non ricordo cosa provai, ma mi fece combattere un bel po, e questa e’ la soluzione migliore trovata fin’ora, e non ho la minima idea di come farlo altrimenti.

Devi trovare un modo di non calcolare tutti gli stati intermedi, un po’ come fai già per il caso speciale D=0.

Ci avevo pensato ma non riesco a trovare una soluzione, perdonami il disturbo ma hai qualche suggerimento?

Considera il seguente input:
5 10 3
1 2 3 4 5
tralasciando per il momento il calcolo del nuovo vettore B e analizzando il solo spostamento del vettore A = {1, 2, 3, 4, 5} per K = 10 volte con passo D = 3 verso destra, si ottiene il seguente risultato:

1 2 3 4 5					(configurazione iniziale)
3 4 5 1 2		per K = 1
5 1 2 3 4		 "  K = 2
2 3 4 5 1		 "  K = 3
4 5 1 2 3		 "  K = 4
1 2 3 4 5		 "  K = 5 	(configurazione iniziale)
3 4 5 1 2		 "  K = 6
5 1 2 3 4		 "  K = 7
2 3 4 5 1		 "  K = 8
4 5 1 2 3		 "  K = 9
1 2 3 4 5		 "  K = 10	 (configurazione iniziale)

Si formano in questo semplice caso 2 sotto cicli di lunghezza 5 e per ogni sotto ciclo di ogni colonna si ha sempre lo stesso prodotto: 1*2*3*4*5 = 120.
Ora si può calcolare il nuovo vettore B sfruttando il prodotto di ogni sotto ciclo e per K = 10:
B = {120^2, 120^2, 120^2, 120^2, 120^2};
mentre per K = 11 si ha:
B = {120^2*1, 120^2*2, 120^2*3, 120^2*4, 120^2*5};
Devi quindi scrivere un codice che fa questo per qualunque valore di N, K e D.
Attenzione! l’esempio riportato non è esaustivo ma è solo indicativo di una strategia da usare per risolvere il task.

Ho provato con il tuo ragionamento ad implementare un programma che salva tutti i sotto-array, ma risulta essere troppo dispendioso in termini di spazio. Ho quindi optato per il codice che ti scrivo qui sotto, ma il problema del tempo persiste. Come posso ridurre la complessita’ temporale?

#include<bits/stdc++.h>
using namespace std;
const long long int mod=1000000007;

long long int power(long long int base, long long int esponente) {
    long long int result = 1;
    base%=mod;
        while (esponente>0) {
        if (esponente%2==1) {
            result=(result*base) % mod;
        }
        base = (base*base)%mod;
        esponente/=2;
    }
    return result;
}

vector<int> execute(int N, int K,int D, vector<int> A) {
    vector<int> B(N,1);
     if(D==0){
			for (int i = 0; i < N; ++i) {	
        			B[i] = power(A[i],K);
        		}
    }else{
    	     int passi=1;
		
		while(0!=(0+(D*passi))%N || passi<K){
			passi+=1;
		}
		
		int giricompletati=K/passi;
		int giriparziali=K%passi;
		int lavoro;

		for(int i=0;i<N;i++){
			for(int j=0;j<passi;j++){
   				lavoro = A[(i+(D*j))%N];
   				if(giricompletati>0) B[i]=((B[i]%mod)*(lavoro%mod))%mod;
   				if(j<giriparziali) B[i]=((B[i]%mod)*(lavoro%mod))%mod;
			}
			if(giricompletati>0) B[i]=((B[i]%mod)*(giricompletati%mod))%mod;
		}	
}
    return B;
}
`

Il codice che hai mandato prende sbaglia 2 casi d’esempio su 3. TI consiglio prima di tutto di trovare il bug (non è difficile) e ottenere una soluzione perlomeno funzionante.

Detto questo migliorare la complessità non è difficile se hai bene in mente la complessità della tua soluzione attuale, ti lascio dunque con alcune domande:

  1. Qual è la complessità della tua attuale soluzione?
  2. C’è qualcosa che stai ricalcolando tante volte ma è sempre uguale?
  3. Come puoi evitare di ricalcolare quel qualcosa?

Inizialmente i 2 casi d’esempio errati mi creavano confusione, ma osservando bene c’e’ una contraddizione della spiegazione del problema e nella dimostrazione, poiche’ nella spiegazione dice di shiftarlo a destra, e nell’esempio lo shifta a sinistra. In ogni caso il resto dei casi li da corretti con questa strategia. Provero’ a farlo seguendo comunque i tuoi consigli, la traccia mi confonde abbastanza ahah, grazie per l’aiuto.

Ignora il messaggio precedente, il contenuto è pressoché lo stesso di questo ma alcuni dettagli sono diversi (non mi ero accorto di uno dei tanti problemi del tuo codice).

A meno di essere @MatteoArcari tendenzialmente non farai 100 su un problema con una soluzione che sbaglia i casi d’esempio, visto che le loro soluzioni sono generate usando la soluzione ufficiale. Quindi anche ammesso che ci fosse una discrepanza tra testo ed esempio, la soluzione non è ignorarla e procedere.

Detto questo, ti garantisco che il testo è corretto, e che l’array viene shiftato verso destra esattamente come c’è scritto. Ma per di più, pensi che un problema che, oltre a essere da parecchio tempo sulla piattaforma, è anche abbastanza importante (visto che fa parte di algobadge) abbia errori così grossolani nel testo?

Ora, se il tuo codice calcolasse effettivamente correttamente la variabile passi, varrebbero le cose che ho detto prima nel messaggio eliminato, cioè che la soluzione è completamente rotta se fai più di un giro completo.

La cosa divertente è che, poiché la condizione nel ciclo while è sbagliata, tutti quei problemi non riescono neppure a manifestarsi, poiché la variabile passi avrà come valore il primo x\ge K tale che xD sia multiplo di N.

Esempio: N=10, \, K=1048, \, D= 4 e il tuo codice trova passi=1053

A questo punto si verificano 2 casi:

  1. se passi>K allora giricompletati=0 e giriparziali=K e siamo tornati a una soluzione identica a quella iniziale.
  2. se passi==K allora giricompletati=1 e giriparziali=0 e di nuovo siamo tornati a una soluzione identica a quella iniziale.

Dunque l’unico motivo per cui il codice rotto non si rompe è che c’è dell’altro codice rotto prima che ne impedisce l’esecuzione (ah l’informatica).

Visto che di nuovo non voglio darti la soluzione in mano:

  1. Gira nel verso giusto e correggi il modo in cui calcoli passi;
  2. Quando l’avrai fatto, il resto del codice sotto sarà ancora rotto, anche se, ti avviso in anticipo, farà i casi d’esempio in quanto in ognuno di essi i cicli completi sono al più 1. Debuggarlo non sarà difficile.
  3. Le 3 domande di qualche messaggio fa.
2 Mi Piace

In poche parole e’ tutto sbagliato AHAHAHAHA. Grazie del tuo tempo, prima o poi risolvero’ questo problema. Spero piu’ prima che poi

Per calcolare il numero di passi per il momento tralascia il valore di K e concentrati su N e D, e trova gli eventuali passi necessari, ad esempio, per N = 10 e D = 1,2,3,4,5,6,7,8,9. Ma per individuare il modo con cui trovare il numero di passi è sufficiente anche solo per D = 1,2,3,4.
Poi puoi considerare le situazioni in cui K \neq N e rispondere correttamente al punto 1 proposto da @fve5.

Capisco quanto possa essere frustrante affrontare un problema che sembra non avere soluzione.