Ho già risolto il primo cct, ed ho usato un approccio praticamente uguale per questo.
Ogni volta provo non usando lo strumento, e se posso usandolo, e alla fine prendo la soluzione con risultato minore.
Il mio codice funziona e non da casi sbagliati, ma supera il limite di memoria nell’ultimo subtask (35/100).
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000000 + 1
#define MAXK 50 + 1
int N, K, a, b;
int dp[MAXN][MAXK];
int mod_power(int base, int exp, int mod)
{
int res = 1;
base %= mod;
while (exp > 0)
{
if (exp & 1)
res = res * base % mod;
base = base * base % mod;
exp >>= 1;
}
return res;
}
int cct(int i, int k)
{
if (i == N)
return 0;
if (dp[i][k] != -1)
return dp[i][k];
int notSkipped = mod_power(a, i, 1000) + cct(i + 1, min(K, k + mod_power(b, i, K)));
int skipped = INT_MAX;
if (k == K)
skipped = cct(i + 1, 0);
return dp[i][k] = min(notSkipped, skipped);
}
int speedrunna(int N_, int K_, int a_, int b_)
{
N = N_; K = K_; a = a_; b = b_;
for (int i = 0; i <= N; i++)
for (int j = 0; j <= K; j++)
dp[i][j] = -1;
return cct(0, 0);
}
int main()
{
cin >> N >> K >> a >> b;
cout << speedrunna(N, K, a, b);
}
(ho lasciato il main se qualcuno vuole provarlo, so che va senza).
dp se usato al massimo occupa sizeof(int) * MAXN * MAXK, cioè circa 200MB, 200 volte il limite di memoria che è 1MiB.
Mi rendo conto di avere un evidente skill issue ma non ho la minima idea di come occupare meno memoria.
Vi ringrazio in anticipo se avete consigli o cose simili.
Ciao, per quanto riguardo la programmazione dinamica sei familiare con il concetto di approccio top-down (quello che stai applicando tu in questo caso) vs approccio bottom-up? In caso tu lo sia allora ti consiglio di iniziare a scrivere la versione bottom-up del tuo algoritmo e poi possiamo cercare di capire come ridurre il consumo di memoria, in caso contrario allora ti consiglio di familiarizzare tale concetto (ci sono molte guide come questa online) per poi seguire il consiglio precedente
Notavo inoltre come questo esercizio sia l’unico della rubrica TAI a cui manca ancora l’editorial, per completezza si potrebbe/dovrebbe rimediare, magari una volta chiuso questo thread. Essendo un tuo esercizio @zJack1342 ti lascio gli onori di casa.
Grazie mille, non ho mai provato l’approccio bottom-up perché mi è sempre risultato più logico il top-down.
Questa sarà la volta buona che cercherò di capirlo.
Ho provato in molti modi a riscriverlo bottom-up, però non riesco proprio a rendermelo logico in testa.
(Questo per semplicità è cct1, nel 2 la logica è la stessa quindi ho provato prima con questo)
int cct_bottom_up()
{
int dp[N+1][K+1];
for (int i = 0; i <= N; i++)
{
for (int k = 0; k <= K; k++)
{
if (i == 0)
{
dp[i][k] = 0;
continue;
}
int notSkipped = T[i-1] + dp[i-1][min(K, k + C[i-1])];
int skipped = INT_MAX;
if (k == K)
skipped = dp[i-1][0];
dp[i][k] = min(notSkipped, skipped);
}
}
return dp[N][K];
}
Questo fa alcuni casi giusti ma non capisco cosa ci sia di sbagliato, non riesco ad immaginarmi come trovare la soluzione migliore dato che non sempre posso prenderla, visto che c’è bisogno che k == K.
Ho capito alcuni esempi fra cui 0/1 knapsack, e riesco a capire come funzionano, però in questo caso la k varia e non capisco come usarla nel modo giusto.
Grazie in anticipo.
Partendo dal presupposto che non è chiarissimo il ragionamento che stai facendo. Solitamente è più comodo andare al contrario, quindi iteri i = n-1, n-2, \dots, 0.
In ogni caso il trucco è definire dp_{i,k}, in questo caso potrebbe essere il tempo minimo per finire il gioco partendo dal livello i con k energie rimanenti. Le transizioni sono identiche a quelle della soluzione top-down, devi solo stare attento a computarle nell’ordine giusto. Per computare dp_{i,k} a te servono dp_{i+1,k+C[i]} e potenzialmente dp_{i + 1,0}. Se tu parti a calcolarli come suggerito da i = n-1, n-2, \dots, 0, ti accorgi che hai tutti i valori che ti servono.
Grazie mille .
Avevo completamente sbagliato ad interpretare il senso del bottom-up, ora mi è decisamente molto molto più chiaro.
A questo punto questo codice da 100/100 su cct1
int cct_bottom_up()
{
int dp[N+1][K+1];
for (int i = 0; i <= K; i++) dp[N][i] = 0;
for (int i = N - 1; i >= 0; i--)
{
for (int k = 0; k <= K; k++)
{
int notSkipped = T[i] + dp[i+1][min(K, k + C[i])];
int skipped = INT_MAX;
if (k == K)
skipped = dp[i+1][0];
dp[i][k] = min(notSkipped, skipped);
}
}
return dp[0][0];
}
Ho già provato a pensare a come diminuire l’occupazione di memoria, ed ho pensato che effettivamente io uso ogni volta il blocco i+1 nella tabella.
Dall’array i non uso mai array che non siano sotto i+1.
Pensavo che potrebbe avere senso portarmi su ogni volta l’array singolo al posto di tenere tutta la tabella, però non sono sicuro di quanto possa avere effetti sul tempo di esecuzione.
Può avere senso come idea?
Grazie mille ancora.
Allora, la buona notizia è che ha funzionato.
La cattiva è che ora gli ultimi 3 testcase danno TLE (immagino sia per la copiatura della memoria).
Ho provato a pensare ad altri modi ma neanche sta volta ho idee per sistemarlo.
La funzione che uso per calcolare la potenza penso sia difficile renderla più veloce.
int cct_bottom_up()
{
int base_dp[K+1]; int curr_dp[K+1];
for (int i = 0; i <= K; i++) base_dp[i] = 0;
for (int i = N - 1; i >= 0; i--)
{
for (int k = 0; k <= K; k++)
{
int notSkipped = mod_power(a, i, 1000) + base_dp[min(K, k + mod_power(b, i, K))];
int skipped = INT_MAX;
if (k == K)
skipped = base_dp[0];
curr_dp[k] = min(skipped, notSkipped);
}
memcpy(base_dp, curr_dp, sizeof(curr_dp));
}
return curr_dp[0];
}
In questo caso non mi viene in mente nessuna idea per evitare di copiare memoria, e a quanto so è molto difficile fare più velocemente di memcpy().
Magari mi sto perdendo in un bicchiere d’acqua, non saprei.
Sempre grazie ancora.
In realtà non sei obbligato a copiare da un array all’altro, puoi usarne uno per quando i è dispari e l’altro per quando i è pari. Un altro trucco consiste nel dichiarare un array bidimensionale di dimensione (2, K) e quando devi accedere ai valori dell’iterazione corrente fai dp[i\%2][k] e per accedere a quelli dell’iterazione precedente fai dp[(i + 1) \% 2][k], per ottenere performance leggermente migliori puoi sostuire \%2 con \&1.
Quello che ti fa andare in TLE è soprattutto il calcolo “ripetuto” di mod_power() in notSkipped. Sei sicuro che non si possa fare meglio per evitare inutili calcoli?
Effettivamente hai ragione, ho provato anche senza copiare e da comunque TLE, ero praticamente sicuro che fosse per quello e invece no.
Forse posso sfruttare il fatto che la base e il modulo non cambino mai, però non ne sono sicurissimo.
#include <bits/stdc++.h>
using namespace std;
int N, K, a, b;
int mod_power(int base, int exp, int mod)
{
int res = 1;
base %= mod;
while (exp > 0)
{
if (exp & 1)
res = res * base % mod;
base = base * base % mod;
exp >>= 1;
}
return res;
}
int cct_bottom_up()
{
int dp[2][K+1];
for (int i = 0; i <= K; i++) dp[0][i] = 0;
for (int i = N - 1; i >= 0; i--)
{
for (int k = 0; k <= K; k++)
{
int notSkipped = mod_power(a, i, 1000) + dp[(i+1)&1][min(K, k + mod_power(b, i, K))];
int skipped = INT_MAX;
if (k == K)
skipped = dp[(i+1)&1][0];
dp[i&1][k] = min(skipped, notSkipped);
}
}
return dp[0][0];
}
int speedrunna(int N_, int K_, int a_, int b_)
{
N = N_; K = K_; a = a_; b = b_;
return cct_bottom_up();
}
Devi seguire il consiglio di @qwfwq, tu calcoli mod_power(a, i, 1000) e mod_power(b, i, K) per ogni valore k = 0, 1, \dots, K, ma come vedi tali valori non dipendono da k quindi puoi calcolarli sono una volta per ogni livello. Per intenderci devi fare qualcosa di simile
int cct_bottom_up()
{
int dp[2][K+1];
for (int i = 0; i <= K; i++) dp[0][i] = 0;
for (int i = N - 1; i >= 0; i--)
{
int len = mod_power(a, i, 1000);
int ene = mod_power(b, i, K);
for (int k = 0; k <= K; k++)
{
int notSkipped = len + dp[(i+1)&1][min(K, k + ene)];
int skipped = INT_MAX;
if (k == K)
skipped = dp[(i+1)&1][0];
dp[i&1][k] = min(skipped, notSkipped);
}
}
return dp[0][0];
}
.
, bel problema.