Problema B: Adding New Machine
Les comparto un problema con su explicación del concurso de Dalian en China.
Descripción
Increíble loca
Compañía progresista ( ICPC por sus siglas en ingles), sufre demasiado por su
lenta producción. Después de una investigación, ellos encontraron que el
embotellamiento estaba en el Absulutely Crowded Manufactory (ACM). Para acelerar
el procedimiento, ellos compraron otra maquina para el ACM. Pero un nuevo
problema apareció, ¿como poner esta nueva maquina en el ACM?.
ACM es un complejo
rectangular, que esta dividido en W*H celdas. Existen N viejas maquinas
rectangulares, y la nueva maquina no
puede ocupar ninguna celda donde existan maquinas viejas. La nueva maquina
necesita M celdas consecutivas. Celdas consecutivas significan una línea de
celdas adyacentes. Tu tarea es calcular el numero de formas diferentes en las
que se pueden colocar la nueva maquina.
Entrada
Hay múltiples casos
de prueba ( no mas de 50). La primera línea de cada caso de prueba contiene 4
enteros W, H, N , M ( 1 <= W, H <=
10^7 , 0 <= N <= 50000, 1 <= M <= 1000), indicando el ancho y el
largo de el ACM , el numero de maquinas viejas
y el tamaño de la nueva maquina. Las siguientes N líneas, cada una
contiene 4 enteros Xi1, Yi1 , Xi2 y Yi2 ( 1 <= Xi1 <= Xi2 <= W, 1
<= Yi1 <= Yi2 <= H), indicando las coordenadas de la i-e sima maquina
vieja. Se garantiza que no hay celdas ocupadas por dos maquinas viejas.
Salida
Imprimir el numero de formas de colocar la nueva maquina en
el ACM.
Entrada Ejemplo
|
Salida Ejemplo
|
3 3 1 2
2 2 2 2
3 3 1 3
2 2 2 2
2 3 2 2
1 1 1 1
2 3 2 3
|
8
4
3
|
Solución:
La primera solución
que se nos presenta a simple vista es colocar en todas las posiciones vacías la
nueva maquina, y contar cuantas veces se puede colocar esta maquina, el único
problema es que W y H son muy grandes, y el costo de hacer esto es W*H*M (
10^17 ), por lo tanto no es una solución viable, pero de esta solución podemos sacar algunos
conclusiones que nos pueden ser útiles, por ejemplo cuando exploramos todas las
posibilidades solo existen dos maneras de colocar una maquina iniciando en
una posiciones (fila, columna), una es colocándola horizontalmente y la otra es
verticalmente.
Para resolver un problema complicado primero hay que irnos a
lo particular, y de ahí movernos a lo general y es por eso que vamos a
resolverlo parte por parte de este problema.
Primero supongamos que solo es una línea sin obstáculos, si
la línea es de tamaño H y la longitud de la maquina es M, el numero de formas
que podemos colocar M es H – M + 1 , siempre y cuando M sea menor a H.
Si todas las celdas de la matriz estuvieran libres de
obstáculos entonces podríamos contar con
facilidad de cuantas maneras podemos colocar esta nueva maquina en toda la
matriz. Suponiendo que la colocamos de
manera vertical, podemos calcular cada columna en 10^7 operaciones ( bueno pero
como todos es lo mismo podría ser con tan solo una multiplicación para todas las
columnas), para en este caso nos conviene realizar columna por columna, en el
caso de las filas cuando la maquina se coloca horizontalmente también se puede
contar fila por fila, en a lo mas 10^7 operaciones.
Esto es para el caso en que toda están vacías, con una sola
resta funciona, pero ¿que pasa cuando existen maquina ya colocadas y cuando son
50000 de ellas?. Para ese caso debemos primero observar un ejemplo, vean la
imagen siguiente:
Como pueden ver, ningún rectángulo se empalma, si nosotros vamos
de izquierda a derecha, por cada columna vemos que en el a primera columna no
hay nada que nos limite, nosotros calculamos cuantas maquinas nuevas podemos
colocar en esta columna con una simple resta, pero en la segunda existe dos
rectángulos, cuando inician los rectángulos nosotros debemos calcular
exactamente los intervalos vacíos para calcular el numero de maquinas a
colocar, existen dos intervalos de 1 y 2, como nuestras maquina es de tamaño 2
, entonces podemos colocar 0 y 1
maquinas nuevas, si nosotros nos movemos a la tercera columna el numero de
maquina que vamos a colocar es la misma que en la segunda, ya que no hay ningún
rectángulo que termine o inicie, pero en la cuarta columna nos encontramos que
uno de los rectángulos se termina, y hay que calcular de nuevo la cantidad de
maquinas a colocar. En este caso quedaría un intervalo de 5, la cantidad de
maquinas que debemos colocar en esta columna es de 4.
¿Que es lo que
podemos rescatar de esta parte?
Nosotros podemos ver
que solamente hay que calcular las posiciones donde exista un cambio, donde se
agregue un nuevo rectángulo o donde se termine uno, en total el máximo numero
de posiciones donde pudiera ocurrir es esto son 100,000 ( ya que hay 50,000
rectángulos por dos ya que es donde
inicia un rectángulo y donde termina).
¿Pero como podemos calcular cada columna el numero de nuevas
maquina que debemos colocar? La respuesta es utilizar una estructura de datos
para contarlas.
¿Qué estructura de datos utilizaríamos para contar los
segmentos unidos y restara M a cada uno de ellos?
Un Árbol de
Intervalos nos serviría para nuestros propósitos,(Véase el capítulo de
estructura de datos avanzadas), el Árbol
de Intervalos nos puede ayudar al conteo de estos segmentos, ya que para
cada nodo podemos guardar:
1 – numero de maquinas que podemos contar sin contar la de
los extremos.
2 – numero de posiciones no marcadas pegadas a la izquierda .
3 – numero de posiciones no marcadas a la derecha.
Supongamos que tenemos una maquina de tamaño 1x2, este es el
tamaño de la maquina que queremos insertar, la siguiente figura muestra una
fila vacía, sin ningún rectángulo en ella.
Si nosotros queremos insertar una maquina que va de la
columna 2 a la columna 6 y otra maquina de la 8 a la 10 quedaría de esta manera.
En nuestro árbol de intervalos, quedaría de la siguiente
manera:
Cado nodo padre puede sacar la información de sus hijos, por
ejemplo en el nodo que tiene la información del segmento [1, 8] , puede calcularlo
con sus dos hijos, el [1,4] y el [5,8], para calcular la información se sigue
los siguientes pasos.
·
Cuadros izquierdos : Son los cuadros izquierdos
del hijo izquierdo.
·
Cuadros derechos: Son los cuadros derechos del
hijo derecho.
·
Numero de maquinas: La suma del numero de maquinas de los dos
hijos mas la suma de los cuadros
derechos del hijo izquierdo y los cuadros izquierdo del hijo derecho menos M (
M es el tamaño de la nueva maquina), si el resultado es negativo entonces
colocar 0.
¿Que pasa cuando uno de los dos hijos nodos esta
completamente lleno?
En ese caso el calculo es distinto, el hijo que tiene todos
los cuadros llenos, no tiene un lado izquierdo o derecho con cuadros , si no
todo el segmento esta completo y tanto el lado izquierdo como derecho son los
mismos cuadros.
Para el caso especifico del nodo que representa el segmento
[1,4] del ejemplo anterior, que se muestra en la siguiente figura:
Se calcula de la siguiente manera
·
Cuadros izquierdos: cuadros izquierdos del hijo izquierdo.
·
Cuadros derechos: la suma de los cuadros del
hijo derecho mas los cuados derecho del hijo izquierdo.
·
Numero de maquinas: El numero de maquinas del
lado izquierdo.
Como pueden ver se tiene que validar si esta completo alguno
de sus hijos o si los dos están llenos, en el caso de que alguno este vacío
aplica los mismo que en el primer escenario.
¿Pero por que es tan rápido un árbol de intervalos en este
problema?
Cuando agregamos un nuevo cuadrado al árbol, iniciamos de la
raíz el nodo que representa a todo el intervalo [1,N], y nos movemos por sus hijos, ya en los hijos
nos vamos recursivamente por todos las ramas del árbol hasta el final. Con las
siguiente condiciones:
1.
Si el nodo donde estamos su intervalo ya no esta
dentro del que queremos hacer una modificación , no seguimos exploras.
2.
Si el nodo donde estamos su intervalo queda
absorbido por el intervalo donde vamos a modificar entonces solo modificamos
ese nodo, y dejamos una bandera ahí, diciendo que todos los cuadros de este
segmento o están usados o están libres, y ya no seguimos con los demás.
3.
Si no pasa ninguna de las anteriores, entramos a
los hijos del nodo actual y realizamos el paso 1 y 2.
Y como pueden ver no se explora todo el árbol en cada
modificación si no solo una parte de el, que seria dos veces el largo de las
ramas y dependiendo del la longitud del segmento seria la longitud de la rama
igual a log( longitud del segmento ).
Para saber después de nuestras inserciones y eliminaciones
cuantas maquinas caben en la fila o columna procesando, seria de la siguiente
manera:
El numero de maquinas es igual a el numero de maquinas de la
raíz mas max( 0, los cuadros del lado
izquierdo – M) + max( 0, los cuadros del lado derecho – M ) , donde M es el
tamaño de la maquina.
Nuestra bandera seria un nuevo elemento del árbol.
Nota: Uno debe
notar que cuando M es 1 solo hay que explorándolo vertical o horizontalmente,
ya que su rotación vertical u horizontal es la misma, y solo contaríamos el
doble.
Código
#
include <stdio.h>
#
include <string.h>
#define
MAXRECTANGLES 50002
int
W, H, N, M, nbreakp, memtree;
typedef
struct { int X[2], Y[2];} RECTANGLE;
typedef
struct { int izq, der, countL, countR, count, delete, fill; } INTERVALTREE;
typedef
struct { int coorden, position, accion; } BREAKPOINT;
INTERVALTREE
MEM[ MAXRECTANGLES * 30 ];
RECTANGLE
R[MAXRECTANGLES + 1];
BREAKPOINT
BP[ (MAXRECTANGLES + 1) * 2];
int
comparebp( BREAKPOINT *A, BREAKPOINT *B ){
if(A->coorden != B->coorden ) return
A->coorden - B->coorden;
return B->accion - A->accion;
}
int
min(int a, int b ){ return a < b ? a : b; }
int
max(int a, int b ){ return a > b ? a : b; }
INTERVALTREE
getNode(int punter, int A, int B){
INTERVALTREE tmp;
tmp.countL = 0;
tmp.countR = 0;
tmp.count = 0;
tmp.fill = 0;
tmp.delete = 0;
if( punter != -1 &&
MEM[punter].delete == 0 ) return MEM[ punter ];
if( punter == -1 || MEM[punter].delete == 2
){
tmp.countL = B - A + 1;
tmp.fill = 1;
}
return tmp;
}
void
insert( int *punter, int A, int B, int a, int b, int type){
int med = (A + B ) / 2;
INTERVALTREE left, rigth;
if( B < a || b < A ) return;
if(*punter == -1 ){
*punter = memtree++;
MEM[*punter].izq = -1;
MEM[*punter].der = -1;
MEM[*punter].count = 0;
MEM[*punter].countR = 0;
MEM[*punter].fill = 1;
MEM[*punter].countL = ( B - A + 1);
MEM[*punter ].delete = 0;
}else
if( MEM[*punter ].delete >= 1){
if( MEM[*punter].izq != -1)
MEM[MEM[*punter].izq].delete = MEM[*punter ].delete;
if( MEM[*punter].der != -1)
MEM[MEM[*punter].der].delete = MEM[*punter ].delete;
MEM[*punter ].delete = 0;
}
if( a <= A && B <= b ){
MEM[*punter].countL = ( type == 0 ? 0 : B - A + 1);
MEM[*punter].fill = type;
MEM[*punter].countR = 0;
MEM[*punter].count = 0;
if( MEM[*punter].izq != -1)
MEM[MEM[*punter].izq].delete = 1 + type;
if( MEM[*punter].der != -1)
MEM[MEM[*punter].der].delete = 1 + type;
return;
}
insert(&MEM[*punter].izq, A, med, a, b,
type);
insert(&MEM[*punter].der, med+1, B, a, b,
type);
/* Calcular */
left = getNode(MEM[*punter].izq , A, med);
rigth = getNode(MEM[*punter].der, med +1 , B
);
if( left.fill == 1 && rigth.fill == 1
){
MEM[*punter].fill = 1;
MEM[*punter].countL = B - A + 1;
MEM[*punter].countR = 0;
MEM[*punter].count = 0;
}else if( left.fill == 1 ){
MEM[ *punter].fill = 0;
MEM[*punter].countL = left.countL +
rigth.countL;
MEM[*punter].countR = rigth.countR;
MEM[*punter].count= rigth.count;
}else if( rigth.fill == 1 ){
MEM[ *punter].fill = 0;
MEM[*punter].countR = left.countR +
rigth.countL;
MEM[*punter].countL = left.countL;
MEM[*punter].count= left.count;
}else{
MEM[*punter].fill = 0;
MEM[*punter].countL = left.countL;
MEM[*punter].countR = rigth.countR;
MEM[*punter].count = left.count+ rigth.count+
max( 0, left.countR
+ rigth.countL - M + 1) ;
}
}
int
count( int punter, int A, int B){
if( punter == -1 ) return ( B - A + 1 ) - M +
1;
if( MEM[punter].delete == 2 ) return ( B - A
+ 1 ) - M + 1;
if( MEM[punter].delete == 1 ) return 0;
return MEM[punter].count + max( 0 , MEM[punter].countL
- M + 1) + max( 0, MEM[punter].countR - M + 1);
}
long
long process( int axis , int width, int length){
int lastpos = 1, cpos, indice = -1, A, B,
pos;
long long currentCont, response = 0;
memtree = 0;
for( pos = 0; pos < nbreakp; pos++){
if( lastpos != BP[pos].coorden ){
currentCont = (long long)count( indice,
1, length);
response += currentCont * (long long)(
BP[ pos ].coorden - lastpos);
}
cpos = BP[ pos ].coorden;
A = ( axis == 0 ) ? R[ BP[ pos ].position ].Y[
0 ] : R[ BP[ pos ].position ].X[ 0 ];
B = ( axis == 0 ) ? R[ BP[ pos ].position ].Y[
1 ] : R[ BP[ pos ].position ].X[ 1 ];
insert( &indice , 1, length, A, B, BP[ pos
].accion );
lastpos = cpos;
}
currentCont = (long long)count( indice, 1,
length);
response += currentCont * (long long)( width
- lastpos + 1);
return response;
}
main(){
int rec, nc;
long long cont;
while( scanf("%d %d %d %d", &W,
&H, &N, &M) != EOF ){
for( rec = 0; rec < N; rec++)
scanf("%d %d %d %d", &R[
rec ].X[0], &R[ rec ].Y[0], &R[ rec ].X[1], &R[ rec ].Y[1]);
for( nbreakp = rec = 0; rec < N; rec++){
for(nc = 0; nc < 2; nc++){
BP[ nbreakp ].position = rec;
BP[ nbreakp ].accion = nc;
BP[ nbreakp++].coorden = R[rec].X[ nc
] + nc;
}
}
qsort(BP, nbreakp, sizeof( BREAKPOINT ),
comparebp );
cont = process( 0, W , H);
for( nbreakp = rec = 0; rec < N; rec++){
for(nc = 0; nc < 2; nc++){
BP[ nbreakp ].position = rec;
BP[ nbreakp ].accion = nc;
BP[ nbreakp++].coorden = R[rec].Y[ nc
] + nc;
}
}
qsort(BP, nbreakp, sizeof( BREAKPOINT ),
comparebp );
if( M > 1 )
cont
+= process( 1, H, W);
printf("%lld\n", cont);
}
return 0;
}
Cualquier duda o sugerencia escribirme a rodrigo.burgos@gmail.com
No hay comentarios:
Publicar un comentario