Editorial for Grafo de Intervalos


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: humbertoyusta

Por simplicidad sumemos los pesos de todos los intervalos y a ello restemos los valores los intervalos que quedarán al final.

Subtarea 1:

En esta subtarea como los intervalos son puntos y todos tienen costo 1, simplemente podemos quedarnos con la mayor cantidad de puntos.

Subtarea 2:

En esta subtarea como los intervalos son puntos, para cada posición nos quedamos con el intervalo con mayor peso en cada posición

Subtarea 3:

Como k = 1, y w_i = 1, es simplemente decir la mayor cantidad de intervalos que se pueden tomar tal que no se intersecten, se puede hacer con dp o con greedy ordenando por e_i y cogiendo el primer intervalo posible repetivamente.

Subtarea 4:

Como k = 1 es simplemente decir la mayor suma de pesos de intervalos que se pueden tomar tal que no se intersecten, se puede hacer con dp.

Subtarea 5:

Esta subtarea puede ser resuelta por implementaciones más sencillas de la solución general.

Subtarea 6:

Por conveniencia, llamaremos bueno a un conjunto de intervalos si todos los componentes conectados tienen un tamaño K como máximo. Toma la unión de intervalos en cada componente conexa. Los intervalos representados por cada componente son disjuntos. A partir de esto, usaremos el enfoque DP donde fijamos la unión de intervalos y llenamos cada componente.

Discretice los intervalos para que tengan coordenadas de hasta 2\cdot{N} y defina f (x) como el costo máximo de los intervalos tal que los intervalos elegidos sean buenos, considerando solo los intervalos cuyo punto final más a la derecha es menor o igual a x. La respuesta es por lo tanto \displaystyle\sum_{i=1}^n{w_i} - f(2\cdot{N}).

Si definimos g(a, b) como el costo máximo de los intervalos a tomar tal que, considerando solo los intervalos que se encuentran completamente en [a, b], el conjunto resultante de intervalos pertenece a un solo componente conexo bueno, entonces tenemos que f (x) = \max_{0\le a<x}(f (a) + g(a + 1, x)). Para calcular g(a, b), simplemente podemos encontrar los intervalos que se encuentran completamente dentro del intervalo [a, b] y tomar los k de mayor peso.

Esto puede resultar en no tener el único componente conectado, pero no importa ya que cada componente conectado seguirá siendo bueno de todas formas. Dado que g(a, b) se puede calcular ingenuamente en tiempo O(N^3 \log{N} ), queda por calcular g de manera eficiente. Si barrimos a de 0 a x - 1, con un poco de contabilidad cuidadosa podemos calcular f (x) en tiempo O(x), lo cual nos daría un algoritmo en O(N^2).

Consideraremos todos los intervalos con punto final izquierdo menor o igual que el x activo, y además dividirlos en intervalos que se extienden más allá de x e intervalos que no lo hacen. Cuando barremos a en orden creciente, algunos intervalos se vuelven inactivos. Deseamos mantener la suma de los K intervalos más pesados ​​que no pasan de x, lo que se puede hacer barriéndolos en orden decreciente de peso y asegurándonos de no haber incluido más de K de ellos.


Comments

There are no comments at the moment.