Cómo resolver Codeforces 1586E: “Moment of bloom”
El tutorial oficial explica la solución a este problema, pero en este artículo demostraré formalmente la propiedad que se explota para resolverlo.
Resumen del enunciado
-Entrada: Un grafo conexo no dirigido con $n$ vértices y $m$ aristas, además de $q$ consultas $a$ y $b$, dos vértices distintos del grafo. Ninguno de los valores supera $3 \cdot 10^5$.
-Salida: Determinar si existe un conjunto de $q$ caminos simples, cada uno entre los vértices de una consulta distinta, tal que cada arista haya sido usada un número par de veces (en el enunciado se menciona que cada aparición de la arista en un camino aumenta su peso en $1$, partiendo desde $0$). Si es el caso, entonces imprimir dichos caminos, y en caso contrario, imprimir el número mínimo de consultas adicionales necesarias para poder crear un conjunto de caminos que cumpla con la condición.
Vamos por partes
Lo primero a determinar si es posible escoger $q$ caminos simples tales que cada arista del grafo aparezca en un número par de dichos caminos. Claramente la respuesta es NO si $q = 1$, porque cada arista debe ser usada por al menos $2$ caminos.
Observando los casos de ejemplo, podemos darnos cuenta que en el primero cada vértice aparece un número par de veces en la parte de las consultas y la salida es “YES...”, mientras que en el segundo los vértices $1$, $2$, $3$ y $5$ aparecen un número impar de veces y la salida es NO.
¿Qué nos dice esto?
En cada camino simple, un vértice $v$ tiene tres posibilidades:
-No aparecer en el camino -Aparecer como el primer o último vértice del camino -Aparecer en medio del camino.
El primer caso es despreciable. En el segundo caso la suma de los pesos de todas las aristas incidentes a $v$ aumenta en $1$ (porque necesitamos usar exactamente una de ellas para el camino), y en el tercero aumenta en $2$ (porque necesitamos una arista para entrar al nodo y otra para salir). Notar que si $v$ aparece en una consulta, debe ser el primer o último vértice del camino, y si sale en un número impar de consultas, entonces la suma de los pesos de todas las aristas incidentes a $v$ es impar porque el tercer caso no cambia la paridad de dicha suma. Dado lo anterior, una de esas aristas tiene peso impar porque en caso contrario la suma sería par. Luego, si existe $v$ que aparezca en un número impar de consultas la respuesta es que no se pueden satisfacer las condiciones.
¿Si 'impar $\rightarrow$ NO', entonces 'par $\rightarrow$ YES'?
La suma de los pesos de las aristas incidentes a cada vértice es par, pero falta demostrar que cada uno de esos pesos también es par en caso de que cada vértice aparezca un número par de veces en las consultas (la llamaremos propiedad $P$).
Para hacer las cosas simples, construyamos un árbol recubridor del grafo. Cada arista no perteneciente al árbol tendrá peso nulo. Por lo anterior sólo hay un camino existente entre cada par de vértices del árbol. Entonces el problema se reduce a demostrar que para cualquier árbol de $n$ vértices se cumple la propiedad $P$.
Si $n = 2$ entonces cada consulta consiste en el mismo par de vértices, que aparecen un número par de veces en total (por hipótesis), y el único camino posible para cada consulta ocupa la única arista del árbol. Como el número de consultas es par (consecuencia de la hipótesis), entonces el peso final de la arista es par.
Supongamos que la propiedad $P$ se cumple para todo árbol con $k \leq n$ nodos. Añadiendo un nuevo vértice $v{n+1}$ al árbol (junto con una arista $en$ incidente al nuevo vértice $n+1$) y una lista cualquiera de consultas válidas.
Ok, ¿pero cómo sé que consultas adicionales debo hacer?
Primero hay que darse cuenta que no hay que encontrar las consultas, sólo el número de éstas, por lo que el problema se hace más fácil.