Sto cercando di risolvere Campi da Calcio che e’ un problema DS del percorso sul algobadge ma si trova su terry. Qualcuno saprebbe consigliarmi una struttura dati per risolverlo? o consigliare magari un algoritmo famoso gia esistente che potrebbe essere implementato con qualche accorgimento?
Ciao, calcio necessita di ottimizzazione più che di algoritmi famosi/strutture dati.
Per rappresentare i dati io userei una matrice, per cui fissati x e y, il valore in (x, y) sia il numero di alberi all’interno di quella casella. In questo modo, il problema si può tranquillamente risolvere con la tecnica chiamata sliding window.
L’unico inconveniente è che per risolvere tutti i testcase ci mette ore, motivo per cui bisogna ricorrere a un’ottimizzazione: usare una matrice delle somme prefisse. Per saperne di più su questo argomento, ti consiglio di leggere la dispensa proposta da AlgoBadge per quel “badge”. In più, su internet si trovano molte indicazioni utili.
Se ti serve altro, chiedi pure 
Grazie per la risposta immediata. Fino allo sliding window ti ho seguito poi pero non riesco a capire come poter usare una matrice di somme prefisse, dato che dovrei fare una differenza per ogni riga del rettangolo piu piccolo, per ogni rettangolo che si puo disegnare nella foresta; questo non rende il codice lento?
Certo, c’è sempre una componente che rallenta il codice. Però con una matrice di somme prefisse puoi ottenere la somma dei numeri contenuti in un “rettangolo” prendendo solo quattro punti della matrice.
La costruzione è leggermente diversa rispetto a un vettore di somme prefisse, però l’idea dietro è la stessa: per calcolare un rettangolo x \times y al posto di calcolare xy somme ne bastano 4. Questa pagina contiene un’interessante spiegazione riguardo alle matrici di somme prefisse (e peraltro l’esempio fornito è molto simile a quello che ti serve nel problema!)
Spero di essermi espresso bene
grazie mille ora e’ chiaro 
, ora provo a mettere in pratica tutto quanto
Ho scritto il codice è funziona 
ma c’è un problema; quando le matrici superano tipo 1000x1000 il programma non capisce piu niente. Ho provato a fare vector di vector ma nulla, il problema persiste, esistono modi per allargare la memoria disponibile?
Le due cause che mi vengono in mente sono:
-
La dimensione massima della matrice è troppo piccola (considera che la massima grandezza è 7000 \times 7000)
-
I valori sono troppo grandi
Potresti inviare il codice, in modo da capire meglio?
#include <iostream>
using namespace std;
void solve(int t) {
int N, M, K, A, B, i, j;
int x, y;
cin >> N >> M >> K >> A >> B;
int forest[N][M];
int tree_pref[N][M];
for (i = 0; i < N; i++){
for (j = 0; j < M; j++)
forest[i][j] = 0;
}
for (i = 0; i < K; i++){
cin >> x >> y;
forest[x][y]++;
}
//imposto le cornici della matrice prefix
tree_pref[0][0] = forest[0][0];
for (j = 1; j < M; j++){
tree_pref[0][j] = tree_pref[0][j-1] + forest[0][j];
}
for (i = 1; i < N; i++){
tree_pref[i][0] = tree_pref[i-1][0] + forest[i][0];
}
// costruiamo la matrix prefix del tutto
for (i = 1; i < N; i++){
for (j = 1; j < M; j++){
tree_pref[i][j] = forest[i][j] + tree_pref[i - 1][j] + tree_pref[i][j - 1] - tree_pref[i - 1][j - 1];
}
}
int fromRow, fromCol, toRow, toCol, treeMin = 1000000000, rettangolo;
fromRow = 0;
toRow = fromRow+A-1;
while (toRow < N){
fromCol = 0;
toCol = fromCol+B-1;
while (toCol < M){
if (fromRow == 0 && fromCol == 0)
rettangolo = tree_pref[toRow][toCol];
else if (fromRow == 0)
rettangolo = tree_pref[toRow][toCol] - tree_pref[toRow][fromCol-1];
else if (fromCol == 0)
rettangolo = tree_pref[toRow][toCol] - tree_pref[fromRow-1][toCol];
else
rettangolo = tree_pref[toRow][toCol] - tree_pref[fromRow-1][toCol] - tree_pref[toRow][fromCol-1] + tree_pref[fromRow-1][fromCol-1];
if (rettangolo < treeMin)
treeMin = rettangolo;
fromCol++;
toCol++;
}
fromRow++;
toRow++;
}
cout << "Case #" << t << ": " << treeMin << endl;
}
int main() {
// se preferisci leggere e scrivere da file
// ti basta decommentare le seguenti due righe:
freopen("calcio_input_1.txt", "r", stdin);
freopen("calcio_output_1.txt", "w", stdout);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
solve(t);
}
return 0;
}
il punto e’ che non faccio neanche delle matrici globali, ma per ogni test ne creo una grande NxM
hai già provato a creare le matrici globalmente? potrebbe essere uno stack overflow
Ecco cosa era, accidenti a me. Grazie mille a entrambi per tutto