Ciao a tutti,
Ieri sera ho provato a sviluppare l’algoritmo risolutivo del problema “ois_potenze”…
Nel test prendo 10/100 solo perché in ogni subtask tranne nel primo, ottengo un Execution Timed Out con quasi 2 sec…
La complessità è O(N2) e il mio codice lo potete trovare qui (https://pastebin.com/dv2epPAX).
Ciao,
la prima osservazione che puoi fare è che non esistono potenze con base maggiore di \sqrt N, in questo modo dovresti ridurre la complessità a \mathcal O(\sqrt N^2) ovvero \mathcal O(N).
Se ancora non basta puoi fermare il ciclo interno quando la potenza supera N e dovresti arrivare (credo) a \mathcal O(\sqrt N\log\sqrt N).
In questo esercizio è facile ed efficiente da usare una array di bool (o una map), partendo dal presupposto che tu devi generare tutte le potenza minori o uguali di N, il primo grande miglioramento che si può fare è appunto questo [quote=“Borto, post:2, topic:4743”]
la prima osservazione che puoi fare è che non esistono potenze con base maggiore di N−−√N\sqrt N
[/quote]
Infatti mi sembra abbastanza ovvio che essendo una funzione esponenziale con x>0 l’esponente minore che abbiamo, e quindi quello che con una stessa base a genera una numero minore è proprio il 2, e naturalmente un numero maggiore di sqrt(n) elevato al quadrato avrà come risultato un numero maggiore di n
Successivamente si può evitare di calcolare moltissime potenze che tu calcoli, prendiamo infatti come esempio n=81
supponendo l’implementazione della limitazione fino a sqrt(n) tu andrai a calcolare le potenze di 2,3,4,5,6,7,8,9, anche se evidentemente molte di queste sono inutili, infatti se b=a^x i valori prodotti da b^i con b^i<=n saranno già stati calcolati da a^i con a^i<=n, ricordando che b è una potenza di a, è abbastanza facile osservare che il 2 produce 2,4,8,16,32,64 , il $4$e l’$8$producono rispettivamente 4,16,64 e 8 , 64 che sono già state calcolate in precedenza.
Questa modifica non credo abbia un grandissimo impatto in quanto se b=a^x soprattutto con x molto elevati i le potenze di b^i con b^i<=n saranno poche analizzando il worst_case quindi n=100000 il risparmio maggiore con questa implementazione si ha con le potenze di 2 che produrranno:
2=2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536
verranno risparmiati 7 valori per il a=4, $4$valori con a=8, $4$valori con a=16, $2$valori con a=32, e poi il numero di valori continua a diminuire, quindi il risparmio non è altissimo ma contando ogni base a con a<sqrt(n) sono un bel po’
Io ho usato questa parte di codice per implementare questo piccolo miglioramento:
for (i=2;i<=sqrt(N);i++){
if (vis[i])
continue;
Spero di essere stato d’aiuto 
Fabio.
Ho modificato il ciclo così :
for(int i=0; i<sqrt(N); i++) { for(int j=1, a=1; j<N; j++) { a = my_pow(i,j); if(a<=N) P.push_back(a); else break; } }
Ottengo il 50/100 per via di 5 Excution Timed Out, un Execution killed with signal 11 e 2 Output non corretti.
Gli output non corretti molto probabilmente sono dati da: i<sqrt(N) che invece dovrebbe essere i<=sqrt(N).
Gli altri errori sono dati dal vettore, ma è veramente necessario tenersi un vettore?
Oppure basta una semplice variabile massimo?
Modificando il sottoprogramma così:
int alloca(int N) { int Max=0; for(int i=0; i<=sqrt(N); i++) { for(int j=1, a=1; j<N; j++) { a = my_pow(i,j); if(a<=N && a>Max) Max = a; else break; } } return Max; }
Ottengo tranne nel primo subtask, 1 output non corretto in ogni subtask…
Credo che il problema sia qua:
if(a<=N && a>Max) Max = a;
else break;
Prova così:
if (a<=N) Max = std::max(Max,a);
else break;
Probabilmente l’errore è li… ma nell’ultimo subtask ottengo 5 Execution Timed Out
Mi sembra strano, prova a postare il codice con tutte le modifice.
#include <stdio.h>
#include <math.h>
#include <algorithm>
int my_pow(int a, int b)
{
int i = 0;
int c = a;
while(i<b)
{
c*=a;
i++;
}
return c;
}
int alloca(int N)
{
int Max=0;
for(int i=0; i<=sqrt(N); i++)
{
for(int j=1, a=1; j<N; j++)
{
a = my_pow(i,j);
if (a<=N) Max = std::max(Max,a);
else break;
}
}
return Max;
}
int main()
{
FILE *fr, *fw;
int N;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
fscanf(fr, "%d", &N);
fprintf(fw, "%d\n", alloca(N));
fclose(fr);
fclose(fw);
return 0;
} `Gli errori sono davvero banali, ma ho fatto fatica a trovarli:
-
int Max=0->int Max=1 -
for(int i=0; i<=sqrt(N); i++)
Il for parte da 0, ma tutte le potenze con base 0 e 1 danno come risultato rispettivamente 0 e 1, che non superavano mai N e perciò, considerando che la funzionemy_powha complessità pari all’esponente, venivano eseguite N^2 operazioni inutili che portavano la soluzione fuori tempo. Ti basta quindi sostituire conint i=2per ottenere 100/100.
Ciao, ho provato personalmente a risolvere il problema e ho ottenuto 100/100, ma ci ho messo un bel po per scovare un errore che come dice @bortoz sta nella variabile Max che invece di essere inizializzata a 0 andrebbe inizializzata a 1, in quanto 1^D ti da come risultato 1 (mi ha fregato il fatto che venga imposta una limitazione su D ( D >= 2 ), mentre non esiste alcuna limitazione su M!).
Per quanto riguarda l’execution timed out, credo sia causato dal fatto che tu per N^2 volte vai a richiamare la funzione my_pow, che quindi ti calcola N^2 potenze… Poiché la base della potenza non cambia ad ogni iterazione del ciclo più interno, e l’esponente cresce in modo lineare (di 1 per volta) c’è un modo migliore per calcolare tutte le potenze senza ricorrere alla funzione my_pow ;).
Se ti dovesse servire lascio il mio codice qui.
La tua osservazione è giusta ma prova a ragionare un po’ su quante volte chiami la funzione my_pow.
Prima di tutto considero l’intervallo [2,\sqrt N] e per ognuno di questi numeri chiamo la funzione my_pow fino a quando la potenza supera N, ovvero \log_2 N volte al massimo. Poi bisogna considerare che il massimo esponente non è N, ma bensì \sqrt N, quindi la complessità finale diventa \mathcal O(\sqrt N \cdot \sqrt N \log N) ovvero \mathcal O(N\log N) che con N\le 10^5 sta nei tempi (worst case 0,004s). La tua soluzione (come la mia) invece è \mathcal O(\sqrt N\log N). Se ti interessa io l’ho risolto così:
ll potenza = 1;
for (int i=2; i<=sqrt(N); i++)
for (ll j=i*i; j<=N; j*=i)
potenza = max(potenza,j);
P.S.: la potenza può essere calcolata anche in tempo logaritmico.
Si in sostanza l’algoritmo è lo stesso, solo che non capisco come mai se nel caso di una complessità O(N log N) il worst case è di 0,004s (come hai detto) anche il mio algoritmo con complessità O(√N log N) impiega 0,004s in diversi testcase.
Il tempo indica non è preciso al millesimo di secondo, quindi semplicemente entrambi i tempi si troveranno in un intervallo di 0,004 sec. (esempio: 0.003 e 0.005), la differenza si troverebbe con un valore di n molto maggiore, se vuoi toglierti lo sfizio puoi provare a vedere i tempi con un n<=1000000 , per farlo puoi, nel caso in cui il compilatore che usi in locale ti dice il tempo di esecuzione puoi usare quello, usando ovviamente lo stesso numero per entrambi.
Nel caso in cui non riesci a vedere il tempo di esecuzione online potresti sfruttare i server di cms , e scegliere un esercizio in cui il limite di tempo è alto(anche 8 sec) e sottoporre il codice , guardando poi i tempi.
2 Mi Piace
Io consideravo la complessità della funzione my_pow nel caso peggiore \mathcal O(\sqrt N) ma riguardando è inferiore, se vuoi avere un’idea dell’effettiva complessità è (potrei sbagliare) qualcosa tipo:
$$\mathcal O \Biggl( \sum_{i=2}^{\sqrt N}\frac{\log_i^2 N}{2}\Biggr)=\mathcal O\Bigl(\sqrt N\log^2N\Bigr)$$
Considera che il fattore \log N è difficile da distinguere, infatti con input \le 10^5 soluzioni in \mathcal O(N) e \mathcal O(N\log N) hanno praticamente gli stessi tempi.
Giusto per rendere l’idea, con il mio algoritmo:
long long int N=100000000
Ha come tempo massimo 0.040 sec. e come minimo 0,16 sec questo per dire che la complessità teorica non coincide perfettamente con il effettivo tempo di esecuzione.
Prova il tuo codice con lo stesso valore di N e guarda se esiste una differenza
1 Mi Piace
Ho capito, grazie mille.