Aiuto oii_incendio in M^2

Stavo provando a risolvere incendio e ho trovato una soluzione in M^2, che però non funziona. Sostanzialmente la mia idea è questa: divido il perimetro della griglia in 2, una metà composta dal lato superiore e a destra, un’altra metà composta dal lato inferiore e a sinistra. Se c’è una zona “a fuoco” continua (per continua intendo che tra due caselle esiste sempre un percorso che va da una all’altra facendo anche “mosse” in diagonale) che va dalla parte del perimetro in alto a destra a quella in basso a sinistra allora non è più possibile andare da (0,0) a (N-1, N-1).

Per far questo in M^2 identifico 2 tipi di eventi fondamentali:

  • una “macchia” di fuoco tocca una delle due parti in cui abbiamo diviso il perimetro che prima non toccava
  • due “macchie” si fondono

Prima di tutto calcolo tutti gli eventi possibili in O(2M + M^2), poi uso una DSU per sapere quanto dista una macchia di fuoco da ciascuna delle 2 parti in cui ho diviso il perimetro man mano che “fondo” le macchie.

Questa idea dovrebbe funzionare - nei miei test è abbondantemente sotto il TL anche se non ho ottimizzato la DSU - ma per qualche motivo si bugga. Nello specifico in alcuni casi calcola tutti gli eventi senza che succeda niente (triggerando l’assert(false)) e in altri mi da semplicemente risposta sbagliata. Sospetto che ci sia qualche problema con la funzione che calcola dopo quanto tempo due “macchie” entrano a contatto, ma anche dopo aver provato diverse versioni nulla ha funzionato. Avete idea di cosa potrebbe essere “rotto”? Grazie mille!!!

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define rb pop_back

typedef long long ll;
typedef long long unsigned llu;
typedef ll num;

const num oo = numeric_limits<num>::max();
typedef pair<int, int> ii;
typedef vector<num> vi;
typedef vector<vi> mi;

#define deb(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl


struct fire{
  ii pos;
  ll dist_1;
  ll dist_2;

  int parent;
  int id;
  
  fire(ii POS, int N, int ID){
    pos = POS;
    dist_1 = min(POS.f, N-1-POS.s); dist_2 = min(N-1-POS.f, POS.s);
    parent = ID; id = ID;
  }

  fire(){};
};

vector<fire> INFERNO;

fire get_repr(fire F){
  while(F.parent  != F.id){
    F = INFERNO[F.parent];
  }
  return F;
}

void join(fire &a, fire &b){
  a = get_repr(a);
  b = get_repr(b);
  
  if(a.id == b.id) return;

  b.parent = a.id;
  a.dist_1 = min(a.dist_1, b.dist_1);
  a.dist_2 = min(a.dist_2, b.dist_2);

  INFERNO[a.id] = a;
  INFERNO[b.id] = b;
}

int alzati(int N, int M, int X[], int Y[]) {
  INFERNO.clear();
  INFERNO.resize(M);

  for(int i=0; i<M; i++){
    INFERNO[i] = fire({X[i], Y[i]}, N, i);
  }
  // {{istante in cui avviene, tipo di evento}, {casella1, casella2}}
  // se il tipo di evento è 0 una macchia di fuoco tocca un lato, se è 1 due macchie di fuoco si fondono
  vector<pair<ii, ii>> events;

  for(int i=0; i<M; i++){
    events.push_back({{INFERNO[i].dist_1, 0}, {i, i}});
    events.push_back({{INFERNO[i].dist_2, 0}, {i, i}});

    for(int j=i+1; j<M; j++){
      ll dist;
      if(INFERNO[i].pos.f == INFERNO[j].pos.f or INFERNO[i].pos.s == INFERNO[j].pos.s){
        dist = (abs(INFERNO[i].pos.f - INFERNO[j].pos.f) + abs(INFERNO[i].pos.s - INFERNO[j].pos.s))/2;
      }else{
        dist = (abs(INFERNO[i].pos.f - INFERNO[j].pos.f) + abs(INFERNO[i].pos.s - INFERNO[j].pos.s)-1)/2;
      }
      events.push_back({{dist, 1}, {i, j}});
    }
  }

  sort(events.begin(), events.end());

  for(auto e: events){
    if(e.f.s == 0){
      fire repr = get_repr(INFERNO[e.s.f]);
      if(repr.dist_1 <= e.f.f and repr.dist_2 <= e.f.f) return e.f.f-1;
    }else{
      join(INFERNO[e.s.f], INFERNO[e.s.s]);
      fire repr = get_repr(INFERNO[e.s.f]);
      if(repr.dist_1 <= e.f.f and repr.dist_2 <= e.f.f) return e.f.f-1;
    }
  }
  assert(false);
}

Partendo dal presupposto che su questo problema ho fatto 75 punti e quindi non sono di certo l’autorita’ assoluta.

Provando a submittare la tua soluzione, sembra che gli Execution Killed siano dovuti a MLE, non al triggerare gli assert. Ho provato a submittare togliendo l’assert(false) alla fine e sbaglia esattamente gli stessi casi.
Il modo in cui io ho risolto MLE (anche se continuo a fare TLE per ora) e’ grafo funzionale

Visto che la chiedevi allego la funzione che uso per calcolare il tempo dopo il quale due fuochi si incontrano.

using namespace std;

using ll = long long;
using pll = pair<ll,ll>;

pll operator-(pll p1, pll p2) { return {p1.first-p2.first, p1.second-p2.second}; }

ll getdist(pll p1, pll p2) {
  pll bagliettofr = p1 - p2;
  return abs(bagliettofr.first) + abs(bagliettofr.second);
}

// questa e' la funzione che ti interessa
ll getweight(pll p1, pll p2) {
  ll dist = getdist(p1, p2);
  if (p1.first == p2.first || p1.second == p2.second) return dist / 2;
  else return (dist-1) / 2;
}

Continuero’ a provare a fare 100 e ti faro’ sapere se ti ho detto cose sbagliate.

Ok Grazieeeeeeeeeeeeeeeeeeeeeeee 73/100, so far so good

dopo aver dolorosamente “grattato via” bit non necessari da alcune variabili e creato un modo per diminuire gli eventi conservati in memoria da events sono riuscito ad eliminare gli MLE (ops, avrei dovuto controllare la RAM). Così facendo ho dovuto aumentare la complessità computazionale a O(M^2 \log M), che però in effetti manda un sacco di test case in TLE. Ho ottimizzato la DSU per ottenere il tempo costante e prossimamente sostituirò il vettore con una minimum queue per riportare il tempo ad O(M^2). Spero sia sufficiente a fare 100 (o almeno 92)…

p.s. Per quanto riguarda la funzione getweight mi sembra che la mia sia uguale alla tua, quindi non credo sia quella il problema (i WA sono magicamente spariti btw).

Grazie ancora!

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define rb pop_back

typedef long long ll;
typedef long long unsigned llu;
typedef ll num;

const num oo = numeric_limits<num>::max();
typedef pair<int, int> ii;
typedef vector<num> vi;
typedef vector<vi> mi;

#define deb(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl

  struct fire{
  int dist_1;
  int dist_2;

  unsigned short parent;
  unsigned short id;
  unsigned short size;
  
  fire(ii POS, int N, short unsigned ID){
    dist_1 = min(POS.f, N-1-POS.s); dist_2 = min(N-1-POS.f, POS.s);
    parent = ID; id = ID; size = 1;
  }

  void reset(ii POS, int N){
    dist_1 = min(POS.f, N-1-POS.s); dist_2 = min(N-1-POS.f, POS.s);
    parent = id; size = 1;
  }

  fire(){};
};

vector<fire> INFERNO;


fire get_repr(fire F){
  fire X = F;
  while(X.parent  != X.id){
    X = INFERNO[X.parent];
  }
  while(F.parent  != F.id){
    INFERNO[F.id].parent = X.id;
    F = INFERNO[F.parent];
  }
  return X;
}

void join(fire a, fire b){
  a = get_repr(a);
  b = get_repr(b);
  
  if(a.id == b.id) return;

  if(a.size < b.size) swap(a, b);

  b.parent = a.id;
  a.dist_1 = min(a.dist_1, b.dist_1);
  a.dist_2 = min(a.dist_2, b.dist_2);
  a.size += b.size;

  INFERNO[a.id] = a;
  INFERNO[b.id] = b;
}

int alzati(int N, int M, int X[], int Y[]) {
  INFERNO.clear();
  INFERNO.resize(M);

  for(int i=0; i<M; i++){
    INFERNO[i] = fire({X[i], Y[i]}, N, i);
  }

  vector<pair<pair<int, bool>, pair<short, short>>> events;
  int dist;

  for(int i=0; i<M; i++){
    vector<pair<pair<int, bool>, pair<short, short>>> cache;
    cache.push_back({{INFERNO[i].dist_1, 0}, {i, -1}});
    cache.push_back({{INFERNO[i].dist_2, 0}, {-1, i}});

    for(int j=i+1; j<M; j++){
      if(X[INFERNO[i].id] == X[INFERNO[j].id] or Y[INFERNO[i].id] == Y[INFERNO[j].id]){
        dist = (abs(X[INFERNO[i].id] - X[INFERNO[j].id]) + abs(Y[INFERNO[i].id] - Y[INFERNO[j].id]))/2;
      }else{
        dist = (abs(X[INFERNO[i].id] - X[INFERNO[j].id]) + abs(Y[INFERNO[i].id] - Y[INFERNO[j].id]) - 1)/2;
      }
      cache.push_back({{dist, 1}, {i, j}});
    }

    sort(cache.begin(), cache.end());
    for(auto e: cache){
      if(e.f.s == 1 and get_repr(INFERNO[e.s.f]).id != get_repr(INFERNO[e.s.s]).id){
        events.push_back(e);
        join(INFERNO[e.s.f], INFERNO[e.s.s]);
      }else if(e.f.s == 0 and e.s.f == -1){
        if(get_repr(INFERNO[e.s.s]).dist_2 == e.f.f) events.push_back(e);

      }else if(e.f.s == 0 and e.s.s == -1){
        if(get_repr(INFERNO[e.s.f]).dist_1 == e.f.f) events.push_back(e);
      }
    }

    for(int i=0; i<M; i++){
      INFERNO[i].reset({X[i], Y[i]}, N);
    }
    cache.clear();
  }

  sort(events.begin(), events.end());

  fire repr;

  for(auto e: events){
    if(e.f.s == 0){
      repr = get_repr(INFERNO[max(e.s.f, e.s.s)]);
      if(repr.dist_1 <= e.f.f and repr.dist_2 <= e.f.f) return e.f.f-1;
    }else{
      join(INFERNO[e.s.f], INFERNO[e.s.s]);
      repr = get_repr(INFERNO[e.s.f]);
      if(repr.dist_1 <= e.f.f and repr.dist_2 <= e.f.f) return e.f.f-1;
    }
  }

  assert(false);
}

Comunque dopo qualche ricerca ho scoperto che il modo intended i fare questa cosa è Dijkstra su grafi densi.

Sources
1 Mi Piace

Alla fine sono riuscito a portarlo a O(M^2 + M\log M) \approx O(M^2) mantenendo l’algoritmo senza Dijkstra. La complessità asintottica dovrebbe andare bene(da quello che ho capito la sol di vercellesi va in O(M^2)), però temo che ci sia un fattore costante che non si riesce a togliere… (fa ancora 73/100)Va beh, non credo che si riesca a rimuovere il fattore costante senza combiare completamente l’algoritmo. Grazie ancora per il tuo aiuto!

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define rb pop_back

typedef long long ll;
typedef long long unsigned llu;
typedef ll num;

const num oo = numeric_limits<num>::max();
typedef pair<int, int> ii;
typedef vector<num> vi;
typedef vector<vi> mi;

#define deb(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl

struct fire{
  int dist_1;
  int dist_2;

  unsigned short parent;
  unsigned short id;
  unsigned short size;

  fire(ii POS, int N, short unsigned ID){
    dist_1 = min(POS.f, N-1-POS.s); dist_2 = min(N-1-POS.f, POS.s);
    parent = ID; id = ID; size = 1;
  }

  void reset(ii POS, int N){
    dist_1 = min(POS.f, N-1-POS.s); dist_2 = min(N-1-POS.f, POS.s);
    parent = id; size = 1;
  }

  fire(){};
};

vector<fire> INFERNO;


fire get_repr(fire F){
  fire X = F;
  while(X.parent  != X.id){
    X = INFERNO[X.parent];
  }
  while(F.parent  != F.id){
    INFERNO[F.id].parent = X.id;
    F = INFERNO[F.parent];
  }
  return X;
}

void join(fire a, fire b){
  a = get_repr(a);
  b = get_repr(b);

  if(a.id == b.id) return;

  if(a.size < b.size) swap(a, b);

  b.parent = a.id;
  a.dist_1 = min(a.dist_1, b.dist_1);
  a.dist_2 = min(a.dist_2, b.dist_2);
  a.size += b.size;

  INFERNO[a.id] = a;
  INFERNO[b.id] = b;
}

int alzati(int N, int M, int X[], int Y[]) {
  INFERNO.clear();
  INFERNO.resize(M);

  for(int i=0; i<M; i++){
    INFERNO[i] = fire({X[i], Y[i]}, N, i);
  }

  vector<pair<pair<int, bool>, pair<short, short>>> events;
  int dist;

  int block_size = 1 + M/5;

  vector<pair<pair<int, bool>, pair<short, short>>> cache;
  for(int i=0; i<M; i++){
    events.push_back({{INFERNO[i].dist_1, 0}, {i, -1}});
    events.push_back({{INFERNO[i].dist_2, 0}, {-1, i}});

    for(int j=i+1; j<M; j++){
      if(X[INFERNO[i].id] == X[INFERNO[j].id] or Y[INFERNO[i].id] == Y[INFERNO[j].id]){
        dist = (abs(X[INFERNO[i].id] - X[INFERNO[j].id]) + abs(Y[INFERNO[i].id] - Y[INFERNO[j].id]))/2;
      }else{
        dist = (abs(X[INFERNO[i].id] - X[INFERNO[j].id]) + abs(Y[INFERNO[i].id] - Y[INFERNO[j].id]) - 1)/2;
      }
      cache.push_back({{dist, 1}, {i, j}});
    }

    if(i % block_size == 0 or i == M-1){
      sort(cache.begin(), cache.end());
      for(auto e: cache){
        if(get_repr(INFERNO[e.s.f]).id != get_repr(INFERNO[e.s.s]).id){
          events.push_back(e);
          join(INFERNO[e.s.f], INFERNO[e.s.s]);
        }
      }

      for(int i=0; i<M; i++){
        INFERNO[i].reset({X[i], Y[i]}, N);
      }
      cache.clear();

    }

  }

  sort(events.begin(), events.end());

  fire repr;

  for(auto e: events){
    if(e.f.s == 0){
      repr = get_repr(INFERNO[max(e.s.f, e.s.s)]);
      if(repr.dist_1 <= e.f.f and repr.dist_2 <= e.f.f) return e.f.f-1;
    }else{
      join(INFERNO[e.s.f], INFERNO[e.s.s]);
      repr = get_repr(INFERNO[e.s.f]);
      if(repr.dist_1 <= e.f.f and repr.dist_2 <= e.f.f) return e.f.f-1;
    }
  }

  assert(false);
}

Sicuro che questa cosa non sia M^2 \log(M^2)?

Hai ragione, ho sparato una cavolata, skill issue