Ordeñando en Orden.
Las vacas del granjero Juan , numeradas como siempre, pasan mucho tiempo en sus pezuñas. Como resultado de eso, ellas han elaborado una jerarquia social compleja relacionada con el orden en que el Granjero Juan las ordeña cada mañana. Después de semanas de estudio, el Granjero Juan ha hecho observaciones acerca de la estructura social . Cada observación es una lista ordenada de algunas de sus vacas, indicando que esas vacas podrían ser ordeñadas en el mismo orden en que aparecen en esta lista. Por ejemplo, si una de las observaciones del Granjero Juan es la lista 2, 5, 1, el Granjero Juan debe ordeñar la vaca 2 algún tiempo antes de ordeñar la vaca 5, la cual debería ser ordeñanda antes de ordeñar la vaca 1.
Las observaciones del Granjero Juan son priorizadas, de forma que su objetivo es maximizar el valor de para el cual su orden de ordeño cumpla las condiciones mostradas en las primeras observaciones. Si varios ordenes de ordeño satisfacen esas condiciones primeras, el Granjero Juan cree que es una tradición muy viejaque las vacas con números menores están antes de las que tienen números más altos, de tal manera que a él le gustaría ordeñar las vacas con números más pequeños primero. Más formalmente, si hay varios ordenamientos que satisfagan esas condiciones, al Granjero Juan le gustaría usar el menor lexicográficamente. Un ordenamiento es lexicográficamente menor que un ordenamiento , si para algún , para todo y (en otras palabras, los dos ordenamientos son iguales hasta cierto punto, en el cual x es menor que y).
Por favor ayude al Granjero Juan a determinar el mejor ordenamiento en el cual ordeñar a sus vacas.
Entrada
La primera línea contiene y . Cada una de las siguientes líneas describen una observación. La línea describe la observación y comienza con el número de vacas listadas en la observación seguido por la lista de enteros dando el orden de las vacas en la observación. La suma de los es a lo más 200000.
Salida
Dé como salida enteros separados por espacio, dando una permutación de conteniendo el orden en el cual el Granjero Juan debe ordeñar sus vacas.
Ejemplo de Entrada
4 3
3 1 2 3
2 4 2
3 3 4 1
Ejemplo de Salida
1 4 2 3
Aquí el Granjero Juan tiene cuatro vacas y debe ordeñar la vaca 1 antes de la vaca 2 y la vaca 3 antes de la vaca 4 (la primera observación), la vaca 4 antes de la vaca 2 (la segunda observación), y la vaca 3 antes de la vaca 4 y la vaca 4 antes de la 1 (la tercera observación). Las dos primeras observaciones pueden ser satisfechas simultáneamente, pero el Granjero Juan no puede cumplir todos esos criterios al tiempo, para hacerlo as requiere que la vaca 1 venta antes que la vaca 3 y la vaca 3 antes de la vaca 1.
Esto quiere decir que hay dos ordenamientos posibles: 1 4 2 3 y 4 1 2 3, siendo el primero lexicográficamente menor.
Comments
Que guapo el problema, como no tiene editorial comparto mi solución que me pareció interesante:
Importante
Leer solo si has intentado bastante pero aún asi no sabes como resolverlo, un poco de respeto al autor.
End-Importante
Con los datos que nos dan crearemos un grafo, de aristas que representa que debería ir antes de por la observación .
Por ejemplo, para se agrega al grafo las siguientes aristas: , (ojo que no es necesaria la arista porque es redundante y podría causar TLE o MLE, solo necesitamos aristas de elementos consecutivos )
Lo primero es encontrar el valor de tal que al unir todas las observaciones no existe ninguna contradicción, que es equivalente a decir que no existan ciclos en dicho grafo (una contradicción seria por ejemplo la vaca 1 debe ir antes de la vaca 2, y la vaca 2 debe ir antes de la vaca 1).
Sea
detect_cycle(x)
una función que nos dirá si existe en el grafo al menos un ciclo, considerando solamente las observaciones (en otras palabras, no consideraremos las aristas cuyo ), la implementación se deja al lector.Observación: No es muy dificil ver que si
detect_cycle(x)
es Verdadero entoncesdetect_cycle(x+1)
es tambien Verdadero (porque no estamos eliminando aristas, solo agregando nuevas)Un posible ploteo de la función para :
Donde es el valor que necesitamos ()
Con esas condiciones podemos hacer búsqueda binaria para encontrar (ver el siguiente pseudocodigo)
Ya encontrado el valor de X quedaría realizar un ordenamiento topológico (y obtener la permutacion mas pequeña lexicograficamente)
Tiempo:
Bibliografía/referencias:
Hope it helps!
(Dejenme subir problemas plis ): )
Edit 1: arreglado el tiempo (DFS * busqueda binaria + ordenamiento topologico) Edit 2: Cambiado condiciones->observaciones
Si llegas a crear un problema, estaré en primera fila (o columna) para leerlo, y cómo no, hacerlo. Enhorabuena y gracias por los aportes que haces. Grande!
JASKJDSAKJD agradecimientos colega <3
Pero no creo que me dejen crear problemas