# Algobadge shiftmul 50/100

**URL:** <https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804>\
**Category:** Aiuto\
**Created:** [28 Marzo 2024, 8:01pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804 "2024-03-28T20:01:15Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Massilla2006](https://forum.olinfo.it/user_avatar/forum.olinfo.it/massilla2006/32/2713_2.png) [@Massilla2006](https://forum.olinfo.it/u/Massilla2006)\
**Post date:** [28 Marzo 2024, 8:01pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/1 "2024-03-28T20:01:15Z")

</div>

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

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

```

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [29 Marzo 2024, 12:39pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/2 "2024-03-29T12:39:24Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![Massilla2006](https://forum.olinfo.it/user_avatar/forum.olinfo.it/massilla2006/32/2713_2.png) [@Massilla2006](https://forum.olinfo.it/u/Massilla2006)\
**Post date:** [29 Marzo 2024, 1:58pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/3 "2024-03-29T13:58:18Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [29 Marzo 2024, 9:48pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/4 "2024-03-29T21:48:08Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Massilla2006](https://forum.olinfo.it/user_avatar/forum.olinfo.it/massilla2006/32/2713_2.png) [@Massilla2006](https://forum.olinfo.it/u/Massilla2006)\
**Post date:** [30 Marzo 2024, 12:04pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/5 "2024-03-30T12:04:20Z")

</div>

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

---

<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:** [30 Marzo 2024, 6:43pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/6 "2024-03-30T18:43:13Z")

</div>

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:

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

---

<div class="post-metadata">

**Author:** ![Massilla2006](https://forum.olinfo.it/user_avatar/forum.olinfo.it/massilla2006/32/2713_2.png) [@Massilla2006](https://forum.olinfo.it/u/Massilla2006)\
**Post date:** [2 Aprile 2024, 3:51pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/8 "2024-04-02T15:51:38Z")

</div>

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?

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

```

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [3 Aprile 2024, 10:15am UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/9 "2024-04-03T10:15:04Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![Massilla2006](https://forum.olinfo.it/user_avatar/forum.olinfo.it/massilla2006/32/2713_2.png) [@Massilla2006](https://forum.olinfo.it/u/Massilla2006)\
**Post date:** [3 Aprile 2024, 1:39pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/10 "2024-04-03T13:39:59Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [3 Aprile 2024, 4:03pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/12 "2024-04-03T16:03:39Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Massilla2006](https://forum.olinfo.it/user_avatar/forum.olinfo.it/massilla2006/32/2713_2.png) [@Massilla2006](https://forum.olinfo.it/u/Massilla2006)\
**Post date:** [3 Aprile 2024, 4:05pm UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/13 "2024-04-03T16:05:00Z")

</div>

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

---

<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 Aprile 2024, 10:02am UTC](https://forum.olinfo.it/t/algobadge-shiftmul-50-100/8804/14 "2024-04-04T10:02:29Z")

</div>

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.