TLE in Calcio (Territoriali)

Aiuto
1

Buongiorno a tutti, sto provando a risolvere “Calcio”, l’approccio è una sliding window, ma è fin troppo lento dopo il quinto testcase. Non ho idee su come approcciare diversamente il problema e scendere di tempo, né ho idea se ci siano altri approcci o se devo ottimizzare l’attuale…

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

//l'idea è usare una sliding window con una matrice 

using namespace std;

void solve(int t) {
  int N, M, K, A, B;
  cin >> N >> M >> K >> A >> B;

  vector<int> X(K), Y(K);
  for (int i = 0; i < K; i++) {
    cin >> X[i] >> Y[i];
  }

  vector<vector<int>> griglia(N, vector<int>(M)); //creazione della griglia

  for(int i = 0; i < K; i++) 
    griglia[X[i]][Y[i]]++; //aumento il numero di alberi che ci sono nella coordinata
  vector<long long> valori; 
  //gira correttamente nella griglia 
  for(int riga = 0; riga + A <= N; riga++){
    for(int colonna = 0; colonna + B <= M; colonna++){
      long long momentanea = 0; 
      for(int c1 = riga; c1 < riga + A; c1++){
        for(int c2 = colonna; c2 < colonna + B; c2++)
          momentanea += griglia[c1][c2]; //se ci sono alberi nella zona del campo li aggiunge 
      }
      valori.push_back(momentanea); 
    }
  }

  cout << "Case #" << t << ": " << *min_element(valori.begin(), valori.end()) << "\n";
}

int main() {
  // se preferisci leggere e scrivere da file
  // ti basta decommentare le seguenti due righe:

  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);

  int T;
  cin >> T;

  for (int t = 1; t <= T; t++) {
    solve(t);
  }

  return 0;
}
2

L’approccio va bene, però il tuo algoritmo ha complessità \mathcal{O}(NMAB) dovuta al fatto che controlli \mathcal{O}(NM) rettangoli e per contare gli alberi in ciascuno ci metti \mathcal{O}(AB).
Sul numero di rettangoli da controllare non puoi farci molto, ma esiste forse una struttura dati che ti permette di contare gli alberi in un rettangolo in \mathcal{O}(1)?

3

Forse una mappa…? Associo a ogni coordinata il suo numero di alberi e poi lo ottengo in O(1)…? Credo possa essere questa la risposta…?
Perché set, stack e queue avrebbero il medesimo tempo di un vector, solo la mappa penso potrebbe essere più veloce, anche se enormemente dispendiosa di memoria.
Però come potrei ottenerlo comunque in O(1)? Devo sempre ottenere il singolo di ogni coordinata e sommarlo…

4

No non parlo di una struttura della STL. Come dici tu il problema è che devi sommare il numero di alberi di ogni coordinata di un rettangolo, quindi bisogna trovare il modo di evitare questo passaggio. La soluzione è tenere una matrice 2D (detta delle somme prefisse) grid tale che grid[x][y] abbia come valore la somma degli alberi nel rettangolo [0, x) \times [0, y). Questa matrice può essere costruita in \mathcal{O}(NM) e poi per contare gli alberi in un rettangolo ti basta controllare solo 4 elementi della matrice grid, qualunque sia la dimensione del rettangolo.

1 Mi Piace
5

Mi hai appena svoltato la situazione. Non ci avevo pensato ad adoperare una matrice come prefix sum, è geniale. Ora tiro fuori un modo di implementarla, anche se non ho ben chiaro perché mi basterebbe controllare solo 4 elementi della matrice…

6

Immagino tu abbia già risolto, ma per chiunque passasse di qui provo a spiegare il perché.

Fondamentalmente tu hai i 4 angoli di questo campo da calcio.
Ottieni quelle coordinate dalle coppie (i, j).

#######
# +--+#
# |  |#
# |  |#
# +--+#
#######

Di fatto la somma prefissa si può utilizzare secondo il seguente ragionamento:

Il numero di alberi nel campo da calcio delimitato dai + è dato dal numero di alberi espressi nella somma prefissa dell’angolo in basso a destra, meno il numero di alberi nell’area riempita di x

#######
#xxxxx#
#x+--+#
#x|  |#
#x|  |#
#x+--+#
#######

Ora basta pensare a come ottenere gli alberi nell’area riempita di x utilizzando solo le somme prefisse degli elementi in corrispondenza dei +, non è difficilissimo [ma forse anche sì, non ho ancora provato a implementare Calcio].

1 Mi Piace