Problema agujeros - OIAJ

Hola, estuve viendo el problema agujeros del OIAJ (http://juez.oia.unsam.edu.ar/#/task/agujeros/statement) y no puedo sobrepasar los 65ptos.
Mi idea es la siguiente:

  • Debido a que las coordenadas de los rectángulos son muy grandes, aplico compresión de coordenadas para reducir el tablero a 2\mathrm{N}×2\mathrm{N} siendo \mathrm{N} la cantidad de rectángulos.
  • Utilizo un vector< vector<int> > para representar el plano comprimido. Todas las casillas las pongo en 0 .
    • Para marcar los rectángulos, marco sus esquinas tal que, la esquina superior izquierda y el extremo opuesto, le sumo uno a la casilla (+1). Mientras, en las dos restantes, le quito uno a la casilla (-1).
    • Recorro el plano, en mi caso, por filas. Aplico tablas aditivas. Así entonces tengo un contador al que le sumo el valor en la casilla por la que paso. Esto podrá subir o bajar según previamente haya marcado las esquinas de un rectángulo. De ser dicho contador positivo, lleno las casillas con 1. A su vez, le sumo el valor que encuentre a la casilla de abajo, de estar dentro del límite del plano. Así llenaré todos los rectángulos según corresponda, y de terminar un rectángulo, se cancelará con la otra esquina del mismo al intentar sumar a la de abajo.
  • Recorro el plano y aplico BFS para recorrer por el espacio en el cual no tengo marcado rectángulos, o sea, compuesto de ceros.
    • De ser un llamado agujero como está definido en el enunciado, éste no será adyacente con ninguna casilla que se vaya del plano.
    • Para obtener la superficie del agujero, hago la suma de la superficie de cada una de las casillas individuales. Para cada una lo obtengo a partir de ver, la diferencia en las coordenadas X e Y que guardé de la compresión de coordenadas antes hecha, para la casilla en cuestión y la que le sigue en el eje correspondiente. Así obtengo alto y ancho reales, pudiendo sacar la superficie como x*y siendo cada uno las diferencias dichas.
    • Para ahorrar memoria y tiempo, al pasar por una casilla, la marco también con un 1 para evitar volver a pasar por ella sin necesidad de guardar la información de que pasé aparte.
  • Por cada BFS, determinado que es un agujero bajo lo dicho, guardo la superficie obtenida. Luego mostraré la cantidad de superficies obtenidas seguida de tales.

De todos los casos, dos dan TLE y el resto son respuestas incorrectas (aparte de las respuestas correctas). Curiosamente, uno de los TLEs, a medida que fui mejorando ciertas cosas, apareció cuando reemplacé un vector que usaba para marcar las casillas hechas, por el plano en sí como menciono en mi idea. Dicho, con posteriores mejoras no pude hacer bajar en su tiempo de ejecución, mientras que otros TLEs si (hasta reducirlos a los dos que digo que quedan).

Esta idea la estuve trabajando con mi profe de olimpíadas (Brimix__) y me destacó que hasta el momento el problema no tiene ningún envío correcto. Por eso quería preguntar si hay algo raro con los casos de prueba o si hay algún caso o algo que me esté pasando de largo.

Dejo mi código:

Código
#include <bits/stdc++.h>

#define forn(i,n) for(int i = 0; i < int(n); i++)
#define forsn(i,s,n) for(int i = int(s); i < int(n); i++)
#define dforn(i,n) for (int i = int(n)-1; i >= 0; i--)
#define dforsn(i,s,n) for(int i = int(n)-1; i >= int(s); i--)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fst first
#define snd second
#define FAST_IO ios::sync_with_stdio(false);cin.tie(nullptr);

using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;

#define MAXN 2*N+2
const int tendX[] = {1,0,-1,0};
const int tendY[] = {0,1,0,-1};

struct point {
    ll x,y;
};

struct rectang {
    point a,b;
};

vector<ll> X,Y;
vector< pair<point,int> > P; // pto, id
vector<rectang> rectangulos;
vector< vector<int> > plano;
vector<ll> r;
int N;

int update(int e, vector<ll> E) {
    return lower_bound(all(E),e) - E.begin();
}

void compress() {
    for (auto &i : P) {
        X.push_back(i.fst.x);
        Y.push_back(i.fst.y);
    }

    sort(all(X));
    X.erase(unique(all(X)),X.end());
    sort(all(Y));
    Y.erase(unique(all(Y)),Y.end());

    for (auto &i : P) {
        ll x = i.fst.x, y = i.fst.y;
        i.fst.x = update(i.fst.x,X);
        i.fst.y = update(i.fst.y,Y);

        if (rectangulos[i.snd].a.x == x and rectangulos[i.snd].a.y == y)
            rectangulos[i.snd].a = {i.fst.x,i.fst.y};
        else
            rectangulos[i.snd].b = {i.fst.x,i.fst.y};
    }
}

bool esquina(int &x, int &y);
bool valid(int &x, int &y);

ll bfs (int &x, int &y) {
    queue<point> Q;
    ll totSup = 0;
    plano[y][x] = true;
    bool posib = true;
    Q.push({x,y});

    while (not Q.empty()) {
        auto e = Q.front(); Q.pop();

        totSup += abs(X[e.x]-X[e.x+1])*abs(Y[e.y]-Y[e.y+1]);

        forn (i,4) {
            int actX = e.x+tendX[i];
            int actY = e.y+tendY[i];

            if (!valid(actX,actY)) {posib = false; continue;}
            if (plano[actY][actX]) continue;

            //cerr << actX << ' ' << actY << ' ' << X[actX] << ' ' << Y[actY] << ' ' << X[actX+1] << ' ' << Y[actY+1] << ' ' << X[actX-1] << ' ' << Y[actY-1] << endl;
            plano[actY][actX] = true;
            Q.push({actX,actY});
        }
    }
    if (posib)
        return totSup;
    else return -1;
}

int main() {
    FAST_IO;

    freopen("agujeros.in","r",stdin);
    freopen("agujeros.out","w",stdout);

    cin >> N;

    plano.resize(MAXN,vi(MAXN,false));

    forn(i,N) {
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        P.push_back({{x1,y1},rectangulos.size()});
        P.push_back({{x2,y2},rectangulos.size()});
        rectangulos.push_back({{x1,y1},{x2,y2}});
    }

    compress();

    for (auto &r : rectangulos) {
        /*forsn (j, r.a.y, r.b.y)
            forsn(k, r.a.x, r.b.x)
                plano[j][k] = true;*/

        plano[r.a.y][r.a.x]++;
        plano[r.a.y][r.b.x]--;
        plano[r.b.y][r.a.x]--;
        plano[r.b.y][r.b.x]++;
    }

    forn(y,MAXN) {
        int cnt = 0;
        forn(x,MAXN) {
            int act = plano[y][x];
            cnt+=act;
            if (y+1 < MAXN)
                plano[y+1][x]+=act;
            if (act == -1)
                plano[y][x] = false;
            if (cnt)
                plano[y][x] = true;
        }
    }

    /*forn (i,20) {
        forn (j,20) {
            cout << plano[i][j];
        }
        cout << endl;
    }*/

    forn (y,MAXN)
        forn (x,MAXN) {
            if (plano[y][x]) continue;
            ll result = bfs(x,y);
            if (result != -1)
                r.push_back(result);
        }

    cout << r.size() << '\n';
    sort(all(r));
    for (auto &i : r)
        cout << i << '\n';

    return 0;
}

bool valid(int &x, int &y) {
    if (x < 0 or x >= MAXN) return false;
    if (y < 0 or y >= MAXN) return false;
    return true;
}

1 me gusta

Entiendo que la idea principal es utilizar compresión de coordenadas, es posible que simplemente el límite de tiempo en el juez online haya quedado muy estricto! Vamos a tratar de revisarlo próximamente.

Una sugerencia muy simple para mejorar la eficiencia del código (en cuanto a constante, no el orden asintótico que está bien hacerlo cuadrático para este problema) es cambiar el vector< vector<int> > plano; por un único arreglo int plano[MAX][MAX]; con tamaños prefijados.

Otro mini-tuneo, aunque más molesto, puede ser usar int en lugar de long long para las cosas que no requieren long long. En particular creo que lo único que requiere long long son las áreas, pero los “lados” todos entran en int. Esto implica tener cuidado al computar áreas porque como los lados van a ser int, en lugar de algo como area += lado1 * lado2; habrá que escribir area += ll(lado1) * lado2; para evitar el overflow interno en esa cuenta (acá se ve una ventaja de typedef vs define, ya que la anterior línea no tiene sintaxis válida con #define, pero sí funciona bien al haber hecho typedef long long ll).

Finalmente otra sugerencia para evitar bugs es que en lugar de hacer #define MAXN 2*N+2 directamente lo definas como variable (que puede tener un const), para evitar inconvenientes. Sino, habría que ponerle paréntesis siempre a los #define: #define MAXN (2*(N)+2). Notar que si escribimos algo como 2*MAXN en la versión del código sin los paréntesis, eso no haría lo que cualquier lector esperaría que haga.

2 Me gusta

Ok, gracias! Voy a ver esos detalles que seguro ahorran un poco de memoria y tiempo, al igual que esperaré si pueden revisarlo porque también tenía algunas con sólo respuesta incorrecta (aunque tal vez funciona si arreglo lo de la cota). Además con el problema del juez mi cuenta por el momento no existe más :sweat_smile:. Espero se pueda resolver para que poco a poco el juez sea mejor!

PD: También tenía otra duda sobre el problema ciudad que agregué a un thread que ya había sobre el problema hace mucho, si no molestaría revisarlo, jeje.
1 me gusta

Me dediqué un rato a hacer lo mejor posible para optimizar el código según lo que sugeriste, al igual que saqué otras cosas que vi innecesarias o que podían mejorarse. Si bien los tiempos bajaron considerablemente, no fue lo suficiente como para arreglar los casos con TLE, al igual que también tengo algunos casos incorrectos que no puedo descifrar en qué consisten. Por las dudas menciono, me da TLE en el caso 10 y 16, y WA en el 6, 17-20.

Dejo mi código optimizado:

Código
#include <bits/stdc++.h>

#define forn(i,n) for(int i = 0; i < int(n); i++)
#define forsn(i,s,n) for(int i = int(s); i < int(n); i++)
#define dforn(i,n) for (int i = int(n)-1; i >= 0; i--)
#define dforsn(i,s,n) for(int i = int(n)-1; i >= int(s); i--)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fst first
#define snd second
#define FAST_IO ios::sync_with_stdio(false);cin.tie(nullptr);

using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;

const int MAX = 5002;
const int tendX[] = {1,0,-1,0};
const int tendY[] = {0,1,0,-1};

struct point {
    int x,y;
};

struct rectang {
    point a,b;
};

vi X,Y;
vector< pair<point,int> > P; // pto, id
rectang rectangulos[MAX];
int plano[MAX][MAX];
ll r[MAX/2];
int N, MAXN, rSz = 0;

int update(int &e, vi &E) {
    return lower_bound(all(E),e) - E.begin();
}

void compress() {
    for (auto &i : P) {
        X.push_back(i.fst.x);
        Y.push_back(i.fst.y);
    }

    sort(all(X));
    sort(all(Y));

    for (auto &i : P) {
        int x = i.fst.x, y = i.fst.y;
        i.fst.x = update(i.fst.x,X);
        i.fst.y = update(i.fst.y,Y);

        if (rectangulos[i.snd].a.x == x and rectangulos[i.snd].a.y == y)
            rectangulos[i.snd].a = {i.fst.x,i.fst.y};
        else
            rectangulos[i.snd].b = {i.fst.x,i.fst.y};
    }
}

bool valid(int &x, int &y);

ll bfs (int &x, int &y) {
    queue<point> Q;
    ll totSup = 0;
    plano[y][x] = true;
    bool posib = true;
    Q.push({x,y});

    while (not Q.empty()) {
        point e = Q.front(); Q.pop();

        if (posib)
            totSup += ll(abs(X[e.x]-X[e.x+1]))*abs(Y[e.y]-Y[e.y+1]);

        forn (i,4) {
            int actX = e.x+tendX[i];
            int actY = e.y+tendY[i];

            if (!valid(actX,actY)) {posib = false; break;}
            if (plano[actY][actX]) continue;

            plano[actY][actX] = true;
            Q.push({actX,actY});
        }
    }
    if (posib)
        return totSup;
    else return -1;
}

int main() {
    freopen("agujeros.in","r",stdin);
    freopen("agujeros.out","w",stdout);

    scanf("%d",&N);
    MAXN = (2*N)+2;
    P.reserve(MAXN);

    forn(i,N) {
        int x1,y1,x2,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        P.push_back({{x1,y1},i});
        P.push_back({{x2,y2},i});
        rectangulos[i] = {{x1,y1},{x2,y2}};
    }

    compress();

    for (auto &r : rectangulos) {
        plano[r.a.y][r.a.x]++;
        plano[r.a.y][r.b.x]--;
        plano[r.b.y][r.a.x]--;
        plano[r.b.y][r.b.x]++;
    }

    forn(y,MAXN) {
        int cnt = 0;
        forn(x,MAXN) {
            int act = plano[y][x];
            cnt+=act;
            if (y+1 < MAXN)
                plano[y+1][x]+=act;
            if (act == -1)
                plano[y][x] = false;
            if (cnt > 0)
                plano[y][x] = true;
        }
    }

    forn (y,MAXN)
        forn (x,MAXN) {
            if (plano[y][x]) continue;
            ll result = bfs(x,y);
            if (result != -1)
                r[rSz++] = result;
        }

    printf("%d\n",rSz);
    sort(r,r+rSz);
    forn(i,rSz)
        printf("%lld\n",r[i]);

    return 0;
}

bool valid(int &x, int &y) {
    if (x < 0 or x >= MAXN) return false;
    if (y < 0 or y >= MAXN) return false;
    return true;
}