Burza

Análisis oficial 

Explicación

Análisis inicial

Primero intentemos transformar los términos del juego en algo menos arbitrario.

Como Stjepan no puede volver atrás porque marca todos los nodos que visita, solo puede moverse hacia abajo en el árbol, aumentando su profundidad a medida que avanza. Dado esto, podemos hacer una serie de observaciones:

1. Daniel puede “cortar” de forma efectiva un subárbol entero marcando un nodo, porque entonces Stjepan no puede pasar por ese nodo. Observemos que este nodo tiene que estar en un nivel más profundo que el nivel actual de Stjepan.
2. Si no podemos impedir que Stjepan alcance un nodo de profundidad $k$ (siendo la raíz de profundidad $0$), entonces el juego no puede terminar siempre en a lo sumo $k$ movimientos.
3. Como ya “perdimos” si Stjepan alcanza la profundidad $k$, no nos importa nada por debajo de la profundidad $k$. También podemos quitar cualquier nodo que no lleve a una profundidad de al menos $k$. Observemos que a partir de aquí no consideraremos ninguno de estos nodos irrelevantes.

De la primera observación, vemos que una estrategia óptima sería marcar a lo sumo un nodo en cada profundidad (excluyendo la raíz).

Como marcar un nodo de profundidad $d$ deja al menos $k - d + 1$ nodos fuera de alcance y podemos marcar nodos desde la profundidad $1$ hasta $k$, si $\frac{k \cdot (k + 1)}{2} \geq n$, el juego siempre puede terminar en $k$ movimientos.

Eso reduce el valor máximo de $k$ que tenemos que considerar a alrededor de 30, que lamentablemente sigue siendo demasiado grande para una solución de tiempo exponencial. ¡Pero es algo! Veamos si podemos recortar más las cotas: 20 sería un buen punto de corte.

Análisis posterior

Para limitar el número máximo de pasos a un punto en el que la DP con máscaras de bits sea viable, tenemos que demostrar que un juego siempre puede terminar en $k$ movimientos si $k^2 \geq n$.

Como cada movimiento parte un árbol en un montón de árboles más pequeños, podemos hacer una demostración por inducción .

Definimos $n_r$ como el número total de nodos que aún no se han vuelto inválidos después de $r$ movimientos, y $t_r$ como el número de nodos válidos a los que Stjepan puede moverse después de $r$ movimientos (o sea, el número de nodos válidos de profundidad $r+1$).

Por ejemplo, digamos que estábamos a profundidad 1 en el siguiente árbol:

Si cortamos el nodo 2, $n_1$ sería 3 y $t_1$ sería 1, ya que Stjepan solo puede moverse al nodo 3.

Nuestro caso base para la inducción es el siguiente:

Esto es cierto para $r=0$. Ahora, solo tenemos que mostrar que, dado lo anterior,

Si mostramos esto, sabremos que $n_r \leq (k-r)^2$ para $r\lt k$. Sustituyendo $r = k - 1$, obtenemos

Esto garantizaría que después de $k-1$ movimientos, queda a lo sumo un nodo válido al que Stjepan pueda moverse. Como Daniel sería el primero en mover en el turno $k$, pondría su marca final en este único nodo restante. Stjepan se quedaría entonces con cero nodos adyacentes válidos a los que pisar, impidiendo su $k$-ésimo movimiento y asegurando la victoria de Daniel.

Para demostrar el paso inductivo, primero definamos una estrategia más concreta:

En cada nivel, cortar el nodo con el subárbol de mayor tamaño que aún no haya sido cortado. Si hay varios nodos con esta cualidad, cortar cualquiera de ellos.

Si seguimos la estrategia definida antes, en cada turno siempre cortaremos al menos $\frac{n_r}{t_r}$ nodos y también dejaremos atrás $t_r - 1$ nodos, ya que ahora están por encima de nuestra profundidad actual^{El -1 es porque ya contamos el nodo inmediatamente debajo de nosotros en el término de la fracción. Quitarlos resultaría en sobrecontar.}. Esto da la siguiente desigualdad:

Aunque esta es una relación significativa, los términos $t_r$ son un poco molestos. Sería genial si pudiéramos tener solo una relación entre $n_r$ y $n_{r+1}$.

Afortunadamente, mediante manipulación algebraica, es posible obtener la siguiente desigualdad:

Encadenando esto con la desigualdad de arriba, obtenemos

Como sabemos que $n_r \leq (k-r)^2$ y por extensión $\sqrt{n_r} \leq k-r$, podemos sustituir esos términos para demostrar la expresión deseada:

¡Y listo! Como mostramos que cualquier caso en el que $k^2 \geq n$ resulta en una victoria, solo tenemos que manejar el caso en el que $k \lt 20$, para el cual basta la DP con máscaras de bits.

DP con máscaras de bits

Observemos que, como un árbol es un grafo planar , cualquier nodo que cortemos cubrirá un segmento continuo de hojas.

Tomemos el siguiente árbol como ejemplo:

Ningún nodo puede cubrir solo, por ejemplo, 3 y 14. Si puede cubrir esos dos entonces también debe cubrir el nodo 1.

Esto nos lleva a nuestro estado de DP. Sea \texttt{max\\_cover}[S] el número máximo de hojas que podemos cubrir desde el inicio dado que tomamos un nodo de cada profundidad especificada en el subconjunto.

Para nuestra transición, intentamos añadir profundidades a todos los subconjuntos previos e iteramos por todos los nodos de esas profundidades.

Por ejemplo, si quitar un nodo podría cubrir de la tercera hoja a la quinta y nuestro subconjunto previo actual puede cubrir hasta la cuarta hoja, entonces juntar esos dos da una configuración que puede cubrir hasta la quinta hoja.

Implementación

Complejidad temporal: $\mathcal{O}(2^{\sqrt{n}} \cdot \sqrt{n})$

#include <functional>
#include <iostream>
#include <map>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int node_num;
	int max_turns;
	std::cin >> node_num >> max_turns;
	vector<vector<int>> neighbors(node_num);
	for (int e = 0; e < node_num - 1; e++) {
		int n1, n2;
		std::cin >> n1 >> n2;
		neighbors[--n1].push_back(--n2);
		neighbors[n2].push_back(n1);
	}
 
	if (max_turns * max_turns >= node_num) {
		cout << "DA" << endl;
		return 0;
	}
 
	std::map<int, int> lost;
	vector<vector<int>> cutoff_cover(node_num);
	vector<vector<int>> depth_nodes(max_turns + 1);
 
	std::function<void(int, int, int)> process_nodes;
	process_nodes = [&](int at, int prev, int depth) {
		depth_nodes[depth].push_back(at);
		if (depth == max_turns) {
			lost[at] = lost.size();
			cutoff_cover[at] = {at};
			return;  // no nos importa nada más allá de esta profundidad
		}
		for (int n : neighbors[at]) {
			if (n != prev) {
				process_nodes(n, at, depth + 1);
				cutoff_cover[at].insert(cutoff_cover[at].end(), cutoff_cover[n].begin(),
				                        cutoff_cover[n].end());
			}
		}
	};
	process_nodes(0, 0, 0);
 
	// intervals[n] el intervalo de hojas que podemos cubrir si cortamos el nodo n
	vector<std::pair<int, int>> intervals;
	for (const vector<int> &cc : cutoff_cover) {
		if (cc.empty()) {
			intervals.push_back({-1, -1});
		} else {
			intervals.push_back({lost[cc.front()] + 1, lost[cc.back()] + 1});
		}
	}
 
	/*
	 * max_cover[ss] contiene el # máx. de hojas que podemos cubrir
	 * desde el inicio dado que
	 * solo cortamos nodos de las profundidades especificadas en los subconjuntos ss
	 */
	vector<int> max_cover(1 << max_turns);
	max_cover[0] = 0;
	for (int ss = 1; ss < (1 << max_turns); ss++) {
		int &curr = max_cover[ss];
		// recorremos cada profundidad previa posible
		for (int to_add = 0; to_add < max_turns; to_add++) {
			if ((ss & (1 << to_add)) != 0) {
				int prev = max_cover[ss & ~(1 << to_add)];
				// y todos los nodos de dicha profundidad
				for (int n : depth_nodes[to_add + 1]) {
					// ver si podemos cubrir más nodos que antes
					if (intervals[n].first <= prev + 1) {
						curr = std::max(curr, intervals[n].second);
					}
				}
			}
		}
 
		if (max_cover[ss] == lost.size()) {
			cout << "DA" << endl;
			return 0;
		}
	}
 
	cout << "NE" << endl;
}