2020 - Stray Cat

Explicación

$A = 3$, $B = 0$

Aunque el problema pide resolver esta subtarea en un grafo general, siempre ayuda considerar primero uno más simple. ¡Así que pensemos en resolver este problema sobre una cadena!

Como $B = 0$, sabemos que no podemos permitirnos ni un solo movimiento incorrecto. De esto se sigue de inmediato que si un nodo de nuestra cadena tiene grado 2, sus dos aristas incidentes deben tener marcas distintas.

Además, las marcas de las dos aristas incidentes deben determinar de forma única una dirección para Catherine. Por ejemplo, el siguiente marcado no funciona:

porque para satisfacer $B = 0$, Catherine debe elegir la arista marcada $1$ al empezar en el nodo 1, y la arista marcada $0$ al empezar en el nodo 2, pero esto es imposible ya que desde su perspectiva los dos nodos son idénticos.

De las dos observaciones anteriores se sigue que si cuatro nodos están conectados en secuencia, las marcas de las 3 aristas que los unen deben ser todas distintas. Una forma fácil de hacerlo es asignar a cada arista $(u, v)$ la marca $\min(d(u), d(v)) \mod 3$, donde $d(u)$ denota la distancia del nodo $u$ al nodo $0$.

Para resolver el caso general, podemos notar que este método concreto de marcado en realidad se generaliza a cualquier grafo. La demostración y la estrategia resultante de Catherine se dejan como ejercicios para el lector.

$A = 2$, $B = 6$, $M = N - 1$

De nuevo, consideremos primero resolver este problema sobre una cadena.

Volvamos a nuestra primera observación de la subtarea anterior: que dos aristas incidentes al mismo nodo tenían que tener marcas distintas. Como $B = 6$, esta condición ya no es necesaria. De hecho, podemos mostrar que para la mayoría de los $N$ esta condición es necesariamente falsa.

Así, supongamos que tenemos un nodo $u$ de grado 2 cuyas aristas incidentes tienen ambas marca $0$. Como ambas marcas son iguales, su primer movimiento podría ir en cualquiera de las dos direcciones, así que necesitamos garantizar que Catherine podrá determinar si va en la dirección correcta después de no más de $B/2$ movimientos.

Si Catherine llega a alguno de los extremos de la cadena en $B/2$ movimientos, o bien llegó a su destino o sabe que debe darse la vuelta. Si no llega a ninguno de los extremos, habrá visto una secuencia de exactamente $B/2 + 2 = 5$ marcas, a partir de la cual debe poder deducir su dirección.

Como estamos tratando con una cadena, escribamos los pesos de las aristas como un arreglo (por ejemplo, podemos representar el grafo de arriba como $[1, 0, 1]$). Ahora solo necesitamos un arreglo de longitud $n - 1$ formado por $0$s y $1$s que cumpla la siguiente propiedad:

Para cada subarreglo de longitud 5, su reverso no puede ser también un subarreglo.

Un ejemplo de arreglo que viola esta condición es $[1, 0, 0, 0, 1]$.

Como observamos antes, podemos suponer que hay al menos una ocurrencia del subarreglo $[0, 0]$ en nuestro arreglo, así que intentemos extenderlo a izquierda y derecha de modo que la condición de arriba se siga cumpliendo.

Observemos que nuestra condición impide la existencia de 3 ceros consecutivos, así que podemos extender nuestro subarreglo a $[1, 0, 0, 1]$. Si añadimos un elemento a ambos lados desde aquí, solo quedan dos posibilidades: $[0, 1, 0, 0, 1, 1]$ o $[1, 1, 0, 0, 1, 0]$.

A partir de aquí, para llegar a un arreglo de tamaño $n - 1$, basta repetir este arreglo de tamaño $6$ una y otra vez. ¡Caso de la cadena resuelto!

Resolver el caso general de árbol requiere una observación más crucial. Notemos que cuando un nodo tiene grado mayor que 2, podemos identificar de forma única su arista hacia el padre usando para esa arista una marca distinta a la de todas las demás aristas incidentes. Esto no funciona para nodos de grado 2 porque Catherine vería una de cada marca y no podría distinguirlas. Por suerte, ya resolvimos la situación de grado 2 en el análisis de cadenas de arriba, así que podemos combinar estas dos observaciones para obtener la solución completa.