Ciao, stavo provando a risolvere Board Game (marcel), ma purtroppo ottengo solo 55 punti per TLE. Attualmente la mia soluzione va in O(N^4) e mi chiedevo perché non passa essendo che i Constraints dicono N <= 120. Essendo120^4 = 2*10^8, non dovrebbe dovrebbe andare bene?
Grazie in anticipo.
La complessità è corretta ma il fattore costante è evidentemente troppo alto. 200 milioni è molto al limite quindi serve ottimizzare per bene.
1 Mi Piace
E’ probabile che sia il fatto che io stia usando una unordered_map, che ha un fattore costante abbastanza alto?
2 Mi Piace
Il problema è che se uso una mappa va fuori tempo e se uso una tabella va fuori memoria. Ci ho ragionato un po’ ma non capisco. Qualche consiglio generale? Grazie.
1 Mi Piace
Quanto fai grande la matrice?
Eh sempre N^4. Non so come ridurla
1 Mi Piace
Con quella complessità si riesce a risolvere il task in questione.
Tuttavia non essendo il codice a disposizione un suggerimento sarebbe quello di non utilizzare le map e usare, invece, se stai utilizzando la programmazione dinamica, le prefix sum sulla matrice in questione.
1 Mi Piace
Condividere il tuo codice sarebbe utile per aiutarti ad ottimizzarlo
Certo, ecco il mio codice:
#include <bits/stdc++.h>
using namespace std;
// input data
int N, X;
vector<vector<int>> M, colPrefixSum, rowPrefixSum;
unordered_map<long long, int> memo;
long long MOD = 1e7;
inline long long encodeKey(short rf, short rs, short cf, short cs) {
return ((long long)rf << 36) | ((long long)rs << 24) | ((long long)cf << 12) | cs;
}
/*
(rf, cf) (rf, cs)
(rs, cf) (rs, cs)
*/
long long f(short rf, short rs, short cf, short cs) {
if (rf > rs || cf > cs) {
return 1;
}
long long key = encodeKey(rf, rs, cf, cs);
if (memo.count(key)) return memo[key];
long long res = 1;
int firstRow = rowPrefixSum[rf][cs+1] - rowPrefixSum[rf][cf];
if (firstRow >= X) res = (res + f(rf+1, rs, cf, cs)) % MOD;
int lastRow = rowPrefixSum[rs][cs+1] - rowPrefixSum[rs][cf];
if (lastRow >= X) res = (res + f(rf, rs-1, cf, cs)) % MOD;
int firstCol = colPrefixSum[rs+1][cf] - colPrefixSum[rf][cf];
if (firstCol >= X) res = (res + f(rf, rs, cf+1, cs)) % MOD;
int lastCol = colPrefixSum[rs+1][cs] - colPrefixSum[rf][cs];
if (lastCol >= X) res = (res + f(rf, rs, cf, cs-1)) % MOD;
memo[key] = res;
return res;
}
int main() {
cin >> N >> X;
M.resize(N, vector<int>(N));
rowPrefixSum.resize(N, vector<int>(N+1, 0));
colPrefixSum.resize(N+1, vector<int>(N, 0));
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cin >> M[i][j];
}
}
for(int i = 0; i < N; i++) {
for(int j = 1; j <= N; j++) {
rowPrefixSum[i][j] = rowPrefixSum[i][j-1] + M[i][j-1];
}
}
for(int i = 1; i <= N; i++) {
for(int j = 0; j < N; j++) {
colPrefixSum[i][j] = colPrefixSum[i-1][j] + M[i-1][j];
}
}
cout << f(0, N-1, 0, N-1) << endl;
return 0;
}
l’ho implementato come una dp top-down perché mi veniva facile, però ora non riesco a ottimizzarlo.
1 Mi Piace
Usa una matrice al posto della map così da migliorare i tempi.
Ho provato ma una matrice (quadridimensionale) al posto della mappa mi fa fare ancora meno punti perché supero i limiti di memoria…
Ti faccio presente che la versione ricorsiva di una dp è significativamente più lenta della versione iterativa. Prova a formulare la dp “con dei cicli” al posto che con la ricorsione
1 Mi Piace
Ho dimenticato di aggiungere che devi utilizzare solo int invece di long long in quanto tutte le operazioni rientrano in un int. In questa maniera va in TLE solo il subtask 4 che con la tecnica ricorsiva richiede un approccio leggermente diverso.
Ok grazie a entrambi, provo un po’ a riguardarlo e vedo se riesco a risolvere.
Scusa, ho provato a risolverlo con una funzione a parte:
long long f2(int h, int w) {
if (h == 0 || w == 0) return 1;
if (memo2[h][w] != -1) return memo2[h][w];
memo2[h][w] = (1 + (2 * (f2(h-1, w) % MOD)) % MOD + (2 * (f2(h, w-1) % MOD)) % MOD) % MOD;
return memo2[h][w];
}
che mi sembra abbastanza facile, eppure mi dà tutti i testcase del 4 sbagliati comunque. Il problema è che ho provato a confrontare le soluzioni con la funzione principale e corrispondono… quindi non capisco come possa essere sbagliato.
La tua funzione risulta corretta per risolvere il subtask 4, l’unica cosa che potrebbe non andare è il caso base che dovrebbe forse essere < 0 invece di == 0.
No vabbè non ho parole, sono cucinato, il problema era semplicemente che avevo scritto male il valore del modulo… 
Cambiato quello 100/100.
1 Mi Piace