Resolviendo el #TuentiContest: Problema 15 – The Robot

Con un poco de retraso, aunque cumpliendo con el horario si me dan permiso de tomar los husos horarios latinoamericanos, llegamos al que fue mi problema favorito. El problema 15. Ahora nos piden hacer de robot pintor. Nuestra tarea es pintar rectángulos de varios colores, unos encima de otros, y luego respondes cuál es el área que cubre cada color. La solución la implementé en C++. Recuerda que también puedes ver mis soluciones a los otros problemas de la competición. Me había extrañado que hasta este momento no nos hubiesen preguntado nada relacionado con geometría, un tema obligatorio en cualquier competencia de programación que se respete. Había que esperar hasta el problema 15 para encontrarnos con el tema. Este problema es mi favorito porque no era de libro, a diferencia de varios problemas anteriores, da espacios para poderse resolver de muchas maneras y lo mejor de todo, la solución trivial pegaba la computadora. Análisis del problema Nos indican que el lienzo sobre el que pintamos es rectangular, que los rectángulos serán pintados horizontal o verticalmente (no en diagonal) y nos dan el orden, posición, área y color de cada rectángulo. En vista de que los rectángulos se van tapando entre sí, es de esperar que el color de los primeros vaya siendo cubierto por los últimos. Me llamó la atención el dato inútil de que el origen estaba abajo a la izquierda (al menos para todas las soluciones de las que hablaré aquí). La solución trivial es pensar en el lienzo como una gran matriz de enteros e irla llenando siguiendo los colores y áreas de los rectángulos, sobrescribiendo valores anteriores. Luego de “pintar” todos los rectángulos, la respuesta se obtendría recorriendo la matriz y contando las ocurrencias de cada número. A pesar de que esta implementación resuelve correctamente el problema, los casos de prueba incluían lienzos muy grandes y numerosos rectángulos, con lo cual nuestro programa tardaría demasiado en responder (y con demasiado quiero decir MUCHOS minutos). Así que nos toca pensar. Una mejor aproximación es aplicar matemáticas para simular. Hay pocas fórmulas más fáciles que el área de un rectángulo e intersectar dos rectángulos tampoco es muy difícil. Mi solución también “pinta” los rectángulos en orden, pero a través de intersecciones y áreas lo que hago es “recortar” los rectángulos cada vez que se intersectan con uno posterior y resto el área total que pierden. Para recortar un rectángulo parto de la idea siguiente idea: la resta de dos rectángulos produce cuatro rectángulos más pequeños, algunos posiblemente de área cero. Como siempre, una imagen vale más que mil palabras.

Intersección de Rectángulos

Los cuatro rectángulos resultantes pueden obtenerse con las coordenadas de los dos originales. Los rectángulos de área cero los descarto en la solución, mientras que los trozos restantes seguirán restándose con todos los rectángulos que intersecte. Solución enviada Mi solución en C++ es una traducción literal de la idea que te acabo de contar. Utilizo tres funciones auxiliares fundamentales, intersectar, calcularArea y obtenerRestos. Primero leo todos los rectángulos de forma independiente y calculo el área de cada color. El lienzo lo considero como el primer rectángulo. Una vez leídos todos, voy en orden restando cada rectángulo con los siguientes y quitando el área del color correspondiente, guardando los trozos restantes en cada paso. Para tener control de los trocitos de cada resta, trabajo con una cola llamada restos. Finalmente imprimo solo los colores que queden con área positiva. Lo bueno comienza a partir de la línea 94, luego de leer todos los rectángulos y tener las áreas iniciales. El primer bloque oculto son las tres funciones auxiliares.

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <map>
#include <boost/tokenizer.hpp>

using namespace std;
using namespace boost;

int calcularArea(vector<int>& rect){
  return (rect[2]-rect[0])*(rect[3]-rect[1]);
}

vector<int> intersectar(const vector<int>& r1,
                        const vector<int>& r2){
  vector<int> result(4,0);
  if(((r1[0]<=r2[0] && r2[0] <= r1[2]) ||
      (r1[0]<=r2[2] && r2[2] <= r1[2]) ||
      (r2[0]<=r1[0] && r1[0] <= r2[2]) ||
      (r2[0]<=r1[2] && r1[2] <= r2[2])) &&
    ((r1[1] <= r2[1] && r2[1] <= r1[3]) ||
     (r1[1] <= r2[3] && r2[3] <= r1[3]) ||
     (r2[1] <= r1[1] && r1[1] <= r2[3]) ||
     (r2[1] <= r1[3] && r1[3] <= r2[3]))) {
    result[0] = max(r1[0],r2[0]);
    result[1] = max(r1[1],r2[1]);
    result[2] = min(r1[2],r2[2]);
    result[3] = min(r1[3],r2[3]);
  }
  return result;
}

vector<vector<int> > obtenerRestos(vector<int>& original,
                                   vector<int>& diferencia){
  vector<vector<int> > resultado;
  vector<int> posibilidad(4,0);

  posibilidad[0] = original[0];
  posibilidad[1] = original[1];
  posibilidad[2] = original[2];
  posibilidad[3] = diferencia[1];
  if(calcularArea(posibilidad)>0)
    resultado.push_back(posibilidad);

  posibilidad[0] = original[0];
  posibilidad[1] = diferencia[1];
  posibilidad[2] = diferencia[0];
  posibilidad[3] = diferencia[3];
  if(calcularArea(posibilidad)>0)
   resultado.push_back(posibilidad);

  posibilidad[0] = diferencia[2];
  posibilidad[1] = diferencia[1];
  posibilidad[2] = original[2];
  posibilidad[3] = diferencia[3];
  if(calcularArea(posibilidad)>0)
   resultado.push_back(posibilidad);

  posibilidad[0] = original[0];
  posibilidad[1] = diferencia[3];
  posibilidad[2] = original[2];
  posibilidad[3] = original[3];
  if(calcularArea(posibilidad)>0)
   resultado.push_back(posibilidad);

  return resultado;
}
int main() {
  string query;
  while(getline(cin,query)){
    tokenizer<> tok(query);
    tokenizer<>::iterator it = tok.begin();
    int W = atoi((*it).c_str());it++;
    int L = atoi((*it).c_str());it++;
    int N = atoi((*it).c_str());it++;

    vector<vector<int> > rectangulos;
    int canva[5] = {0,0,W-1,L-1,1};
    rectangulos.push_back(vector<int>(canva,canva+5));
    map<int,int> totales;

    totales[1] = W*L;
    for(int i=0;i<N;i++){
      vector<int> info;
      for(int j=0;j<5;j++,it++) {
        info.push_back(atoi(it->c_str())); // lx ly ux uy color
      }
      rectangulos.push_back(info);
      totales[info[4]] = calcularArea(info);
    }

    for(size_t i=0;i<rectangulos.size();i++){
      deque<vector<int> > restos;
      restos.push_back(rectangulos[i]);
      for(size_t j=i+1;j<rectangulos.size();j++){
        vector<vector<int> > nuevosRestos;
        while(restos.size()>0){
          vector<int> r = restos.front(); restos.pop_front();
          vector<int> interseccion =
                      intersectar(r,rectangulos[j]);
          int area = calcularArea(interseccion);
          if(area > 0) {
            totales[rectangulos[i][4]] -= area;
            vector<vector<int> > pedazos =
                                 obtenerRestos(r,interseccion);
            nuevosRestos.insert(nuevosRestos.begin(),
                                pedazos.begin(),
                                pedazos.end());
          }else{
            nuevosRestos.push_back(r);
          }
        }
        restos.insert(restos.begin(),nuevosRestos.begin(),
                      nuevosRestos.end());
      }
    }

    map<int,int>::iterator t=totales.begin();
    while(t->second <= 0) t++;

    int color = t->first;
    int cant = t->second;

    cout << color << " " << cant;
    for(t++; t!=totales.end();t++){
      color = t->first;
      cant = t->second;
      if (cant>0) cout << " " << color << " " << cant;
    }
    cout << endl;
  }
  return 0;
}

Solución mejorada La función de intersección no está implementada de la mejor manera. Sabía que para detectar una intersección no hacían falta tantas verificaciones pero en el momento de la competencia no me di cuenta cuáles eran las mínimas necesarias y suficientes. El trauma me duró hasta la mañana siguiente, cuando viendo por la ventana del autobús recordé la solución. Solo es necesario hacer dos comparaciones para determinar si hay intersección. Veámoslo con una imagen.

El punto azul del rectángulo inferior debe estar arriba y a la izquierda del punto azul del superior. El punto rojo del rectángulo superior debe estar arriba y a la izquierda del punto rojo del inferior. Por lo tanto, la función puede rescribirse como:

vector<int> intersectar(const vector<int>& r1,
                        const vector<int>& r2){
  vector<int> result(4,0);
  if(r1[0]<=r2[2] && r1[1] <= r2[3] &&
     r2[0]<=r1[2] && r2[1] <= r1[3]) {
    result[0] = max(r1[0],r2[0]);
    result[1] = max(r1[1],r2[1]);
    result[2] = min(r1[2],r2[2]);
    result[3] = min(r1[3],r2[3]);
  }
  return result;
}

Las otras dos funciones sí son correctas. Para escribir obtenerRestos tuve que dibujar varias veces y armarme de paciencia, porque me despistaba rápido con tantas coordenadas y escribía los puntos que no debía. Finalmente la lectura de datos. Otro dolor de cabeza, aunque este no me tomó tantas líneas. Sin embargo, utilizando el scanf de toda la vida pude haberla hecho mejor. Por primera vez, luego de tantas lecturas feas en C++, les dejo una versión mejorada de la lectura de datos.

int main() {
  int W, L, N;
  while(scanf("%d %d %d", &W, &L, &N) == 3) {
    vector<vector<int> > rectangulos;
    int canva[5] = {0,0,W-1,L-1,1};
    rectangulos.push_back(vector<int>(canva,canva+5));
    map<int,int> totales;

    totales[1] = W*L;
    for(int i=0;i<N;i++){
      int info[5];
      scanf("%d %d %d %d %d", &info[0], &info[1], &info[2],
                              &info[3], &info[4]);
      vector<int> rect(info, info+5);
      rectangulos.push_back(rect);
      totales[info[4]] = calcularArea(rect);
    }

En general, la solución me gustó. Incluso con esa intersección tan fea que escribí en ese momento. Como ves, siempre se puede mejorar. Y tú, ¿cómo lo resolviste?

5 thoughts on “Resolviendo el #TuentiContest: Problema 15 – The Robot

  1. Yo hice algo así. Pero añadí dos cosas: la primera, fue que ordené los rectángulos de mayor a menor en una lista ordenada. La ordenación la hacía de izquierda a derecha y desempatando con la ordenación de arriba a abajo en el lienzo. Cuando quería empezar a recorrer los rectángulos, comenzaba en el rectángulo que más se acercara por la derecha al borde derecho del rectángulo a incluir, posteriormente, recorría la lista de rectángulos hasta encontrar al primero o a un rectángulo.
    Con pocos rectángulos a pintar no se nota, pero es una optimización.

    La segunda cosa que hice diferente fue el conteo. Yo mantengo todos los rectángulos recortados en esa lista. Para saber el número total de puntos de cada color, recorro la lista, y sumo el área del elemento actual (en la componente del color del elemento actual) de un diccionario de colores temporal. Por último, muestro los valores de menor a menor del diccionario.

    1. Interesante idea la de ordenar para ir cortando los trozos más grandes de una. Después de todo, para qué trabajar con un trozo pequeño que igual será tapado al final.
      Lo de contar sí es cuestión de paráfrasis. Es igual restar del total que esperar al final y sumar los parciales que quedan.

      Por eso este problema fue mi favorito pues daba la oportunidad de resolverlo de muchas formas distintas.

  2. Yo directamente tiré a pintar todo en un buffer y luego a contar. Sé que no es lo más óptimo pero los tests no eran tan grandes como para tardar minutos, es más el tiempo es aproximadamente 1 segundo en mi portátil (800MHz); y en la fase de submit tampoco eran nada del otro mundo. No eran pruebas como las de los emirps :)

    1. ¿Te parecieron más fuerte las pruebas de emirps? Bueno, la verdad no podría comparar porque fui directamente con la criba en aquel caso y todo pasó rápido. Pero aquí sí que implementé la versión lienzo/matriz y tardó un montón en hacer submit. De hecho, fue más de un minuto (y para mi más de 10 segundos ya es mucho en una competencia de programación) y maté la ejecución para reimplementarlo como expliqué aquí. Entonces sí se pudo enviar en segundos.
      Capaz fue una combinación de casos grandes con problemas de red, porque varias personas reportaron problemas de envío durante la semana.

      1. En los emirps, sí que debí implementar la criba, porque sí que me tiré tiempo haciendo el submit, y al final en el caso del submit se desbordó el int que utilicé. Pero las pruebas de este reto me parecieron más bien pequeñas.

Deja un comentario