Hola, necesito ayuda en el problema B de la CIIC-2019, La Gran Division (https://omegaup.com/arena/CIIC-2019-Publico/practice/#problems/ciic2019-division), gracias de antemano.
2 Me gusta
En términos de grafos, se pide particionar a los vértices en 2, de manera tal que haya arista entre todo par (v,w) con v en un conjunto y w en el otro.
El problema es mucho más natural si consideramos el grafo complemento: es decir, si ponemos una arista entre dos ciudadanos exactamente cuando no se odian. En ese caso, en la partición lo que tiene que pasar es que no haya ninguna arista que cruce de un conjunto al otro (pues si la hubiera, en el grafo original faltaba).
Es decir, hay que partir al grafo complemento en dos pero sin que queden aristas cruzando de uno a otro. Esto solamente se puede hacer si por cada componente conexa del grafo complemento, la ubicamos completamente de un lado, o completamente del otro. Si la suma de los pesos de los nodos en una componente es S, según de que lado ponemos la componente podemos elegir cambiar la diferencia de pesos en +S o en -S.
El problema tiene naturalmente dos partes:
- Identificar los nodos de las distintas componentes conexas del complemento.
- Con los pesos que surgen de lo anterior, resolver un problema de la partición
Para las subtareas que permiten N^2, para la primera parte se puede armar la matriz de adyacencia del grafo, luego complementarlo (cambiando 0 y 1 salvo en la diagonal), y finalmente calculando las componentes con DFS/BFS/Union Find.
Para calcular esas componentes eficientemente, la clave es simular el BFS (o cualquier recorrido) que se realizaría en el grafo complemento, pero sin construirlo de verdad. En el código de BFS, la única parte cara es iterar todos los vecinos. Pero en realidad, podría cambiarse más precisamente por “iterar todos los vecinos nuevos, nunca antes vistos”. Si se mantiene un set o un arreglo de bool que indique los nodos vistos o no, en cada nodo v, será posible viajar a todos los nodos que no sean vecinos de v en el grafo, y por lo tanto se podría viajar a todos los del conjunto de nunca-vistos-todavía, excepto los vecinos. Se puede entonces directamente en cada nodo, recorrer la lista de todos los pendientes y verificar si son vecinos o no (o cualquier otra implementación equivalente).
Esto no arruina la complejidad porque cada nodo al que es posible moverse es eliminado del conjunto de nunca-vistos, así que eso solamente puede pasar N veces como máximo. Y los nodos que no son eliminados deben ser vecinos, así que la complejidad de recorrerlos suma en total O(M).
3 Me gusta
Gracias por su excelente explicación, la verdad que el problema está muy interesante, por lo que entendí es simplemente sacar todas las componentes conexas del grafo complemento, entonces como obligatoriamente estas componentes tienen que estar en el mismo grupo, puedo quedarme con el poder que aportarán a la división en la que estarán, y luego una especie de mochila para saber cual es la mínima diferencia, lo que me preocupa es cuando todos se odian, entonces la complejidad me quedaría en \mathcal{O}(N \cdot W) donde W = \sum_{i = 1}^{n} P[i] ya que exactamente hay N componentes conexas en el grafo complemento
También si pudieses ayudarme con algún lugar donde pueda enviar este problema, he intentado enviar en omegaup.com y me da el siguiente error:
El problema no es público y está siendo usado en al menos un concurso activo.
2 Me gusta
La clave es que si todos se odian, entonces el grafo es completo y tiene del orden de N^2 aristas, por lo tanto N = O(\sqrt M), que por la cota de M no puede ser demasiado grande.
Por el mismo argumento pero mirando componentes en lugar de nodos, se demuestra que en cualquier grafo la cantidad total de componentes conexas posibles en el complemento (que es lo que importa para luego hacer suma de subconjunto) es O(\sqrt M). Básicamente porque entre todo par de esas componentes, hay aristas en el grafo original.
2 Me gusta
Ya veo, no me había fijado en el límite de M. Muchísimas gracias, me has ayudado mucho
1 me gusta