Editorial for Mezclando Árboles

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: dcordb

Primero para cada componente conexa del grafo dado es necesario hallar una bipartición de la misma, esto se puede hacer usando BFS o DFS. Definimos al valor de una componente conexa como el valor absoluto de la diferencia entre la cantidad de nodos de color negro y la cantidad de nodos de color blanco, se puede demostrar que no importa que bipartición se halle esta diferencia se mantiene constante.

Como hay que lograr que el grafo sea conexo hay que añadir, si hay $k$ ~k~ componentes, al menos $k - 1$ ~k - 1~ aristas, nota que solo es necesario añadir exactamente $k - 1$ ~k - 1~ conectando cada componente a la siguiente, por ejemplo. No hacen falta más ya que una vez que sea conexo el grafo la cantidad de nodos blancos y negros no va a variar aunque se añadan más aristas (de tal forma que el grafo al final sea bipartito, claro).

Ahora para unir dos componentes cualesquiera se puede o coger un nodo negro de la primera y unirlo con uno blanco de la segunda o coger un nodo blanco de la primera y unirlo con uno negro de la segunda.

Si nos olvidamos del valor absoluto el problema se convierte en que hay $k$ ~k~ componentes y para cada una se puede elegir uno de los conjuntos a ser blanco y el otro negro y se quiere hacer esto de tal forma que la suma de la cantidad total de nodos blancos menos la suma de la cantidad total de nodos negros sea lo más cercano a $0$ ~0~ posible (podría ser negativo este valor).

Esto es equivalente a tener $k$ ~k~ objetos y el costo de cada uno es la diferencia entre blancos y negros, llamemos a estos costos $c_1, c_2, \ldots, c_k$ ~c_1, c_2, \ldots, c_k~ entonces lo que se puede hacer es coger un subconjunto de estos y cambiarles el signo (esto sería invertir el coloreo en la componente) tal que la suma total de los costos sea lo más cercano a $0$ ~0~.

Esto se puede hacer con DP, que es muy parecido al problema de la mochila. Lo que hay que realizar algunas optimizaciones para que entre en el tiempo límite. Por ejemplo primero se ordenan estos costos y los costos iguales se procesan juntos, ahora si un costo $c_i$ ~c_i~ se repite $m$ ~m~ veces entonces se puede pasar del estado $w$ ~w~ a $w - 2 \cdot c_i, w - 4 \cdot c_i, w - 6 \cdot c_i, \ldots, w - k \cdot 2 \cdot c_i$ , pero además se puede notar que si ya se pudo llegar a un estado $v$ ~v~ (haciendo este proceso) significa que se pudo llegar también a $v - 2 \cdot c_i, v - 4 \cdot c_i, \ldots$ por lo que se pueden parar las transiciones al pasar esto.

Haciendo estas cosas se logra que el problema entre en tiempo.

Complejidad: $O(n \sqrt n)$ ~O(n \sqrt n)~ como jcg demuestra en el comentario de abajo.

Comments

2

jcg commented on Feb. 1, 2018, 2:25 p.m. ← edit 2 →

Bueno, la complejidad de la solución propuesta es de hecho $O(n\sqrt{n})$ ~O(n\sqrt{n})~, en un momento lo voy a demostrar. Mi intento de solución durante el concurso también tenía esta complejidad, pero no pude hacerlo entrar en tiempo. Mi anális fue similar al explicado aca, pero con algunos cambios. Primero por cada componente al encontrar una coloración de este supongamos que la diferencia (con signo) entre los nodos de un color menos los del otro es $k(k<0)$ ~k(k<0)~. Ahora podemos tomar este valor de $k$ ~k~ para adicionar a la solución, o el valor de $-k$ ~-k~. Vamos a tomar $k$ ~k~, pero si en un futuro quisieramos cambiar la selección en este componente, solo tendriamos que adicionar $-2k$ ~-2k~ al resultado. Así que tenemos una diferencia inicial y un conjunto de valores $a_1, a_2, \ldots, a_c$ ~a_1, a_2, \ldots, a_c~ donde $c$ ~c~ es la cantidad de componentes conexas. Supongamos que la suma de los $k$ ~k~ escogidos en $sum<=0$ ~sum<=0~, tendriamos que encontrar el valor más proximo a $-sum$ ~-sum~ que puedo lograr tomando algunos de los $a_i$ ~a_i~ (cada $a_i$ ~a_i~ solo puede ser tomado a lo sumo una vez). Para esto podriamos hacer una mochila $0-1$ ~0-1~ con los $a_i$ ~a_i~ y ver cual es la suma mas proxima a $-sum$ ~-sum~ que puedo alcanzar. Pero esto tiene complejidad $O(nc)$ ~O(nc)~ y como $c=O(n)$ ~c=O(n)~ tendríamos una solucion cuadrática, que no da en tiempo. La idea a explotar que a pesar que pueden existir $O(n)$ ~O(n)~ $a$ ~a~'s entre los valores de estos solo puede haber $O(\sqrt{n})$ ~O(\sqrt{n})~ valores diferentes. Si iteramos por estos valores diferentes y logramos actualizar la respuesta en $O(n)$ ~O(n)~ para cada uno de estos valores tendriamos la complejidad requerida. Entonces hacemos como esta explicado en la editorial, supongamos que tenemos el valor de $A$ ~A~ acurriendo $m$ ~m~ veces, si tenemos un array $can[s]=true$ ~can[s]=true~ si la suma $s$ ~s~ puede ser lograda, entonces para actualizar estos $A$ ~A~, procesamos el array $can$ ~can~ en orden decreciente de $s$ ~s~, y si encontramos que un valor es posible lograrlo entonces procedemos a actualizar a los $s+A,s+2A,\ldots,s+mA$ ~s+A,s+2A,\ldots,s+mA~ en $can$ ~can~ con el valor $true$ ~true~, pero si encontramos que en un paso de esta actualizacion que un valor de estos ya esta actualizado entonces no continuamos a actualizar los siguientes, porque este valor ya habra actualizado los valores que podrian modificarse. Entonces tenemos que el procesado para un valor de $A$ ~A~ no es $O(mn)$ ~O(mn)~ sino que es $O(n)$ ~O(n)~ ya que solo visito a lo sumo $O(n)$ ~O(n)~ valores falsos en $can$ ~can~ y a lo sumo $O(n)$ ~O(n)~ valores true. Es posible lograr la misma complejidad en este paso de la mochila de otras formas, pero parece que la constante es mayor, y en mis intentos durante el concurso no se me occurrio cambiar esta parte. PS: No se como lograr que aparezcan los latex sin que ocurran en una sola linea.

0

josed commented on Feb. 1, 2018, 2:54 p.m. ← edited →

off-topic: las fórmulas deben escribirse entre dos ~. En este caso ya las arreglé para que se muestren correctamente. Saludos.