Saltar a contenido

14 de noviembre · Refuerzo PUJ

Planteamiento e invariantes de ciclo. Las tres horas de programación muestran cómo se plantea la solución de un problema antes de escribir código: la bisección sobre la respuesta para repartir textos entre empleados, el recorrido en amplitud sobre una rejilla con zonas prohibidas y el recorrido en profundidad que pinta un grafo con dos colores. La profundidad se completa con los tipos de arista que encuentra en un grafo dirigido y en uno no dirigido, y la amplitud con dos usos más: detectar ciclos con los grados de entrada y recorrer sin usar caminos cerrados. La hora de lógica trabaja los invariantes de ciclo de UVa 11078 y el ejercicio en papel de UVa 507.

Sesión

Diapositivas

Programación

Soluciones de programación

Cada uno de los tres problemas resuelto paso a paso, con su traza y su costo.

Recorridos: tipos de arista, ciclos y caminos cerrados

Soluciones de recorridos

El código de cada recorrido en Python y en C++, con sus bordes, su costo y la traza del ejercicio de los caminos cerrados.

Los tipos de arista en un recorrido en profundidad

Cuando la profundidad mira una arista \(u \to v\), el estado de \(v\) dice qué clase de arista es. Si \(v\) está blanco, es de árbol y el recorrido baja a \(v\). Si está gris, \(v\) es un ancestro de \(u\) en el camino actual: es de retroceso, y esa arista cierra un ciclo. Si está negro, ya terminó: es de avance cuando \(u.d < v.d\) y cruzada cuando \(u.d > v.d\). En un grafo dirigido aparecen los cuatro tipos y hay ciclo exactamente cuando aparece una de retroceso.

En un grafo no dirigido cada arista está en las dos listas, y solo aparecen aristas de árbol y de retroceso. La arista de vuelta al padre no cuenta: sin el parámetro padre, cada arista de árbol se confundiría con un ciclo. Y cuando un nodo encuentra a un vecino negro, es la misma arista de retroceso vista desde el otro extremo.

Costo: cada nodo se visita una vez y cada lista se recorre una vez, \(O(V + A)\).

Ciclos con amplitud: los grados de entrada

Se cuenta cuántas aristas llegan a cada nodo y se ponen en una cola los que no tienen ninguna. Al sacar un nodo se baja en uno el grado de sus vecinos, y entra a la cola el que llega a cero. Si salen todos los nodos, no hay ciclo; si no, los que se quedan son los del ciclo y los que dependen de él, porque un nodo de un ciclo siempre conserva la arista que le llega desde el anterior.

Costo: contar los grados y vaciar la cola recorren cada arista una vez, \(O(V + A)\).

En el computador: UVa 10305, Ordering Tasks

Tareas con relaciones de precedencia, sin ciclos: se imprime cualquier orden en que se puedan hacer. Es Kahn tal cual, y el orden en que las tareas salen de la cola es la respuesta. El grado de entrada se cuenta al leer: con cada relación i j se suma 1 a entrada[j]. Con la muestra sale 1 4 2 5 3, la del enunciado.

Costo: \(O(n + m)\) por caso.

En el computador: UVa 11686, Pick up sticks, con Kahn

El mismo problema de los tres estados, ahora con amplitud. Un palito se recoge cuando ya se recogieron los que tiene encima, así que su grado de entrada es cuántos lo tapan. El orden en que salen de la cola es la respuesta, y si no salen los \(n\) palitos hay un ciclo y se imprime IMPOSSIBLE. Sin recursión no hay pila que reviente: la cadena de un millón de palitos tarda 0,3 s en C++ y 2,0 s en Python. El orden que da no es el de la profundidad, y el juez acepta cualquiera que respete los pares.

Costo: \(O(n + m)\) por caso.

Para el computador: recorrer sin usar caminos cerrados

Hay lugares con nombre unidos por caminos de sentido único, algunos cerrados, y un lugar de partida. Se pide la lista de lugares a los que se llega sin usar un camino cerrado, cada uno una vez. Los nombres pasan a índices con un diccionario, los caminos cerrados se guardan como pares en un conjunto, y el recorrido no toma una arista cuyo par esté ahí. La trampa: cerrar el camino de A a B no cierra el de B a A.

Costo: \(O(V + A)\) del recorrido, más la consulta al conjunto por cada arista.

Lógica

Soluciones de lógica

Los invariantes del ejercicio de UVa 507 con su traza y sus tres pasos.

Problemas en clase

El código de los tres, en Python y en C++, está en la carpeta codigo/. Cada problema cierra con su costo.

Hora 1. Bisección sobre la respuesta: transcribir textos

Hay que repartir textos en orden entre k empleados, cada uno con un tramo seguido de textos, de modo que el más cargado lleve el menor número posible de páginas. En vez de buscar el reparto óptimo se pregunta si alcanza con un tope de t páginas por empleado, y una pasada por los textos lo responde: el empleado actual recibe el texto siguiente mientras quepa, y si no cabe entra otro empleado. Si t alcanza, cualquier tope mayor también, y esa monotonía permite bisecar entre el texto más largo y la suma de todos. La trampa está en la cota inferior: si lo arranca por debajo del texto más largo, el programa responde un tope que ningún reparto cumple.

Costo: con \(n\) textos que suman \(S\) páginas, cada comprobación da \(n\) pasos y la bisección corre \(O(\log S)\) veces, así que el total es \(O(n \log S)\).

Hora 2. Amplitud sobre una rejilla con zonas prohibidas: el bosque

Se pide el menor número de pasos para cruzar una rejilla de la esquina superior izquierda a la inferior derecha. Hay casillas bloqueadas y criaturas, cada una con una posición y un radio, y no se puede pisar ninguna casilla dentro del radio de una criatura. El peligro depende solo de las criaturas y no del camino, así que se marca una vez antes del recorrido, y el recorrido en amplitud queda igual al de un tablero con paredes. La trampa está en la zona: el enunciado dice en cualquier dirección, y medir la distancia de una forma o de otra cambia qué casillas quedan prohibidas y, con ellas, la respuesta.

Costo: con una rejilla de \(R \times C\), el recorrido visita cada casilla una vez y mira cuatro vecinas, \(O(RC)\). Marcar una criatura de radio \(r\) revisa a lo más \((2r + 1)^2\) casillas.

Hora 3. Profundidad modificada: dos colores

Se decide si los nodos de un grafo se pueden pintar con dos colores de modo que ninguna arista una dos nodos del mismo color. El recorrido en profundidad lleva el color además de la marca de visitado: pintado el primer nodo, el color de cada vecino queda forzado, y basta recorrer una vez y anotar si alguna arista une dos nodos iguales. La trampa es que el grafo puede venir en varios pedazos, así que el recorrido arranca desde cada nodo que siga sin color.

Costo: con \(V\) nodos y \(A\) aristas, cada nodo se pinta una vez y cada lista de vecinos se revisa una vez, \(O(V + A)\).

En el computador: UVa 10004, Bicoloring

Es el mismo problema de dos colores con la entrada de un juez: varios casos, cada uno con \(n\) nodos y \(l\) aristas, hasta un \(n = 0\), y la salida BICOLORABLE. o NOT BICOLORABLE. El grafo es conexo, así que un solo recorrido desde 0 pinta todos los nodos. La trampa es crear de nuevo los colores y las listas en cada caso.

Costo: \(O(n + l)\) por caso.

Lógica

Invariantes de ciclo escritos como fórmula y demostrados en tres pasos: inicialización, estabilidad y terminación. El ciclo de partida es el de UVa 11078, con las variables mayor y mejor, y el ejercicio en papel es el ciclo de UVa 507 sin el desempate. Las diapositivas y sus soluciones están arriba.

Para seguir

Problemas propuestos para trabajar por cuenta propia. Cada solución va con su costo y se envía al juez.

Archivos de lectura

UVa 1203, UVa 10341, UVa 11413, UVa 10810 y UVa 11080 tienen un fragmento con la lectura de la entrada y un comentario donde va el algoritmo. Están en la carpeta codigo de esta sesión:

Problema Python C++
UVa 1203 lectura_1203.py lectura_1203.cpp
UVa 10341 lectura_10341.py lectura_10341.cpp
UVa 11413 lectura_11413.py lectura_11413.cpp
UVa 10810 lectura_10810.py lectura_10810.cpp
UVa 11080 lectura_11080.py lectura_11080.cpp

El fragmento se copia dentro de un programa con sus #include y su main en C++, o con import sys en Python, y se completa con la solución. La muestra del enunciado va en 1.in y su salida en 1.out, y diff compara:

g++ -std=c++17 -Wall -Wextra solucion.cpp -o solucion
./solucion < 1.in > salida.out
diff salida.out 1.out

Propuesto. UVa 11080, Place the Guards

Se ponen guardias en los cruces de modo que cada cruce y cada calle queden vigilados, sin dos guardias en los extremos de una misma calle, y se pide el menor número de guardias, o -1 si no se puede. Los guardias de un pedazo del grafo son justamente uno de los dos colores, así que en cada pedazo se pinta con dos colores y se suma el color menos usado. Las trampas: el grafo puede venir en varios pedazos, así que el coloreo arranca desde cada nodo sin color; si un pedazo choca la respuesta es -1; y un cruce sin calles necesita su propio guardia.

Costo: \(O(v + e)\) por caso.

Propuesto. UVa 1203, Argus

Cada consulta registrada responde a los \(P\) segundos de registrarse y después cada \(P\) segundos, y se piden las primeras \(K\) respuestas. La cola de prioridad guarda un par por consulta, el instante de su próxima respuesta y su número. Sale el menor par, y la consulta vuelve a entrar con el instante aumentado en su periodo. El orden de los pares resuelve el desempate que pide el enunciado: si dos consultas responden en el mismo instante, sale primero la de número menor. Las trampas son de lectura. La primera respuesta llega a los \(P\) segundos y no en el instante 0, el registro termina en una línea con #, y \(K\) llega a 10 000 con a lo más 1000 consultas.

La entrada se lee así en C++:

char palabra[10];
int num, p;
while (scanf("%s", palabra) == 1 && palabra[0] != '#') {
  scanf("%d %d", &num, &p);
  /* aquí va la inserción en la cola de prioridad */
}
int k;
scanf("%d", &k);

Costo: con \(q\) consultas la cola nunca pasa de \(q\) pares. Llenarla son \(q\) inserciones, y el ciclo de salida corre \(K\) veces con una extracción y una inserción, de modo que el total es \(O((q + K) \log q)\).

Propuesto. UVa 10341, Solve It

Dados seis enteros con \(0 \leq p, r \leq 20\) y \(-20 \leq q, s, t \leq 0\), se busca \(x\) en \([0,1]\) con \(p e^{-x} + q \sin x + r \cos x + s \tan x + t x^2 + u = 0\), con cuatro decimales, o No solution si no hay.

Aquí la función viene dada y lo que queda es comprobarle dos cosas. La monotonía sale de derivar: cada sumando de \(f'(x) = -p e^{-x} + q \cos x - r \sin x + s \sec^2 x + 2tx\) es menor o igual que cero en \([0,1]\) por los rangos del enunciado, así que \(f\) no crece y hay a lo sumo una raíz. Y los extremos deciden si existe: hay raíz exactamente cuando \(f(0) \geq 0 \geq f(1)\). Esa es la trampa, porque sin esa comprobación el ciclo igual termina y devuelve un número que no es raíz de nada. Cien vueltas dejan el intervalo en \(2^{-100}\) del original.

La entrada se lee así en C++, y comparar contra seis detecta el fin del archivo:

int p, q, r, s, t, u;
while (scanf("%d %d %d %d %d %d", &p, &q, &r, &s, &t, &u) == 6) {
  /* resolver este caso */
}

Costo: cien evaluaciones por caso, o sea constante; con hasta 2100 líneas de entrada el total es lineal en la cantidad de casos.

Propuesto. UVa 11413, Fill the Containers

Los recipientes de la banda se vacían en orden en \(m\) contenedores, cada recipiente entero en uno solo, y se pide la menor capacidad posible del contenedor más grande. Aquí la función hay que encontrarla: en vez de buscar el óptimo se pregunta si alcanza con capacidad \(t\). Un recorrido voraz lo responde. Llena el contenedor actual mientras quepa el recipiente siguiente, abre otro cuando no cabe, y \(t\) alcanza si usa a lo más \(m\). Si \(t\) alcanza, cualquier capacidad mayor también, y esa monotonía permite bisecar entre el recipiente más grande y la suma de todos. La trampa está en los rangos: \(m\) llega a \(10^6\) con a lo más 1000 recipientes, así que pueden sobrar contenedores, y la cota inferior es el recipiente más grande porque ninguno se divide.

La entrada trae varios casos hasta el fin del archivo:

int n, m;
while (scanf("%d %d", &n, &m) == 2) {
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &c[i]);
  }
  /* aquí va la bisección */
}

Costo: con \(n\) recipientes que suman \(S\), el recorrido voraz da \(n\) pasos y la bisección sobre \([\max, S]\) corre \(O(\log S)\) veces, así que el total es \(O(n \log S)\) y no depende de \(m\).

Propuesto. UVa 10810, Ultra-QuickSort

Dada una lista de \(n < 500\,000\) enteros distintos, se pide cuántos intercambios de elementos vecinos hacen falta para dejarla ordenada. Como cada intercambio arregla exactamente una pareja fuera de orden, lo que se pide es el número de parejas \((i,j)\) con \(i<j\) y \(a_i > a_j\), y contarlas una por una cuesta \(\Theta(n^2)\).

Las parejas de un tramo se reparten en tres clases: las dos puntas en la mitad izquierda, las dos en la derecha, y una en cada mitad. Las dos primeras son el mismo problema sobre la mitad del tamaño, y ahí está la recursión; el caso base es un tramo de un elemento. La tercera se cuenta mientras se mezclan las dos mitades ya ordenadas: cuando sale un elemento de la derecha, todos los que siguen pendientes en la izquierda son mayores que él. Que las mitades queden ordenadas es lo que permite contar esa clase en una sola pasada.

La entrada se lee así en C++, con el auxiliar reservado una vez por caso:

int n;
while (scanf("%d", &n) == 1 && n != 0) {
  vector<int> a(n), aux(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
}

Costo: hay \(\log_2 n\) niveles de llamadas y en cada uno la mezcla mueve los \(n\) elementos una vez, de modo que el total es \(\Theta(n \log n)\). El contador va en long long, porque en el peor caso la respuesta llega al orden de \(10^{11}\). Medido con \(n = 499\,999\), la versión de C++ tarda 0,20 s y la de Python 5,1 s, así que al juez se envía la de C++.

Propuesto. UVa 10954, Add All

Cada suma cuesta lo que suman sus dos operandos, así que conviene sumar siempre los dos menores. La cola de prioridad entrega esos dos en tiempo logarítmico y recibe de vuelta el resultado, que vuelve a competir con los demás; por eso ordenar una vez y sumar en fila no alcanza. La trampa es el acumulado: con \(N = 5000\) números iguales a 99 999 el costo mínimo pasa de \(6 \times 10^9\), más de lo que cabe en 32 bits.

int n;
while (scanf("%d", &n) == 1 && n != 0) {
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
  }
}

Costo: el ciclo corre \(N - 1\) veces, con dos extracciones y una inserción en \(O(\log N)\) cada una, \(O(N \log N)\).

Propuesto. UVa 10611, The Playboy Chimp

Las \(N\) alturas llegan en orden no decreciente, y para cada consulta \(q\) se pide la más alta menor que \(q\) y la más baja mayor que \(q\). Dos búsquedas binarias dan los bordes: la primera posición con altura \(\geq q\) y la primera con altura \(> q\). Cada condición es falsa en un prefijo del arreglo y verdadera en el resto, y eso es lo que permite buscar así. La trampa son los repetidos y los bordes: una altura igual a \(q\) no sirve para ninguna de las dos, y cuando una de las dos no existe se imprime una X mayúscula en su lugar. La entrada trae un solo caso.

int n, q;
scanf("%d", &n);
vector<int> h(n);
for (int i = 0; i < n; i++) {
  scanf("%d", &h[i]);
}
scanf("%d", &q);
for (int i = 0; i < q; i++) {
  int consulta;
  scanf("%d", &consulta);
}

Costo: cada búsqueda parte el rango a la mitad en cada vuelta, \(O(N + Q \log N)\) con la lectura. Recorrer el arreglo en cada consulta es \(O(NQ)\), unos \(1{,}25 \times 10^9\) pasos con \(N = 50\,000\) y \(Q = 25\,000\).

Propuesto. UVa 11624, Fire!

Joe y el fuego avanzan una casilla por minuto, en vertical o en horizontal, y Joe sale por cualquier casilla del borde. El parámetro son las \(R \times C\) casillas, con \(R, C \leq 1000\). Lo resuelven dos recorridos en amplitud. El primero arranca con todas las casillas F en la cola, con distancia 0, y da el minuto en que el fuego llega a cada casilla. El segundo parte de J y solo entra a una casilla si llega antes que el fuego. La trampa principal es esa comparación, que es estricta: en la segunda muestra Joe y el fuego llegan a la vez a las dos casillas libres, y con \(\leq\) saldría 2 en lugar de IMPOSSIBLE. El enunciado no asegura que haya alguna F, y una casilla a la que el fuego nunca llega sigue libre para Joe, así que la distancia \(-1\) no puede entrar a la comparación sin más. La respuesta cuenta el minuto de salir: es la distancia a la casilla del borde más uno, y Joe parado en el borde responde 1.

int casos;
scanf("%d", &casos);
for (int caso = 0; caso < casos; caso++) {
  int r, c;
  scanf("%d %d", &r, &c);
  vector<vector<char> > mapa(r, vector<char>(c));
  for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
      scanf(" %c", &mapa[i][j]);
    }
  }
}

El espacio antes de %c se salta el salto de línea.

Costo: cada recorrido visita cada casilla una vez y mira cuatro vecinas, \(O(RC)\) por caso, con hasta \(10^6\) casillas.

Propuesto. UVa 924, Spreading the News

Cada empleado cuenta la noticia a sus amigos al día siguiente de enterarse, y se pide el día en que más empleados se enteran por primera vez y cuántos son. El día en que un empleado se entera es su distancia a la fuente en el grafo de amistades, y el recorrido en amplitud asigna esas distancias por niveles: basta contar cuántos quedan en cada nivel. La red se lee una vez y sirve para todos los casos, así que las distancias se reinician con cada fuente. Las trampas son tres: los amigos de la fuente se enteran el día 1, ante un empate en el tamaño gana el primer día, y si nadie más que la fuente se entera la salida es un solo 0.

int e;
scanf("%d", &e);
vector<vector<int> > amigos(e);
for (int i = 0; i < e; i++) {
  int n;
  scanf("%d", &n);
  for (int j = 0; j < n; j++) {
    int a;
    scanf("%d", &a);
    amigos[i].push_back(a);
  }
}
int t;
scanf("%d", &t);
for (int caso = 0; caso < t; caso++) {
  int fuente;
  scanf("%d", &fuente);
  /* aquí va el recorrido en amplitud */
}

Costo: con \(V\) empleados y \(A\) amistades, el recorrido saca de la cola a cada empleado una vez y revisa una vez los amigos de cada uno, \(O(V + A)\) por fuente y \(O(T\,(V + A))\) con \(T\) fuentes.

Material de la sesión

  • Soluciones de UVa 1203, UVa 10341, UVa 11413 y UVa 10810, con la idea, la complejidad y el código en Python y C++.
  • Ejercicios interactivos sobre bisección, recorridos en rejillas y en grafos, colas de prioridad y dividir y vencerás.