Ordeñando en Orden.

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 32M

Author:

FrankHG

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

Las $N$ ~N~ vacas del granjero Juan $(1 \leq N \leq 100000)$ ~(1 \leq N \leq 100000)~, numeradas $1...N$ ~1...N~ 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 $M$ ~M~ observaciones acerca de la estructura social $(1 \leq M \leq 50000)$ ~(1 \leq M \leq 50000)~. 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 $X$ ~X~ para el cual su orden de ordeño cumpla las condiciones mostradas en las primeras $X$ ~X~ observaciones. Si varios ordenes de ordeño satisfacen esas $X$ ~X~ 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 $x$ ~x~ es lexicográficamente menor que un ordenamiento $y$ ~y~, si para algún $j$ ~j~, $x_i = y_i$ ~x_i = y_i~ para todo $i < j$ ~i < j~ y $x_j < y_j$ ~x_j < y_j~ (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 $N$ ~N~ y $M$ ~M~. Cada una de las siguientes líneas describen una observación. La línea $i+1$ ~i+1~ describe la observación $i$ ~i~ y comienza con el número de vacas $m_i$ ~m_i~ listadas en la observación seguido por la lista de $m_i$ ~m_i~ enteros dando el orden de las vacas en la observación. La suma de los $m_i$ ~m_i~ es a lo más 200000.

Salida

Dé como salida $N$ ~N~ enteros separados por espacio, dando una permutación de $1...N$ ~1...N~ conteniendo el orden en el cual el Granjero Juan debe ordeñar sus vacas.

Ejemplo de Entrada

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

1
karellgz commented on April 4, 2024, 6:13 p.m. ← edit 2 →
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 $(u_i,v_i,m_i)$ ~(u_i,v_i,m_i)~ que representa que $u_i$ ~u_i~ debería ir antes de $v_i$ ~v_i~ por la observación $m_i$ ~m_i~.

Por ejemplo, para $m_5 = \{ 1, 2, 3\}$ ~m_5 = \{ 1, 2, 3\}~ se agrega al grafo las siguientes aristas: $(1,2,5)$ ~(1,2,5)~, $(2,3,5)$ ~(2,3,5)~ (ojo que no es necesaria la arista $(1,3,5)$ ~(1,3,5)~ porque es redundante y podría causar TLE o MLE, solo necesitamos aristas de elementos consecutivos )

Lo primero es encontrar el valor de $X$ ~X~ tal que al unir todas las observaciones $m_1, m_2, ... m_x$ ~m_1, m_2, ... m_x~ 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 $m_1, m_2, ... m_x$ ~m_1, m_2, ... m_x~ (en otras palabras, no consideraremos las aristas cuyo $m_i > x$ ~m_i > x~), la implementación se deja al lector $^{1}$ ~^{1}~.

Observación: No es muy dificil ver que si detect_cycle(x) es Verdadero entonces detect_cycle(x+1) es tambien Verdadero (porque no estamos eliminando aristas, solo agregando nuevas)

Un posible ploteo de la función para $x \in [0,M]$ ~x \in [0,M]~:

0: 0 1: 0 ... t-1: 0 t: 1 t+1: 1 t+2: 1 ... M: 1

Donde $t-1$ ~t-1~ es el valor que necesitamos ( $x$ ~x~)

Con esas condiciones podemos hacer búsqueda binaria para encontrar $t$ ~t~ (ver el siguiente pseudocodigo)

l=0, r=M while l<r: mid = (l+r)/2 if detect_cycle(mid): # actualizamos el rango de búsqueda a: [l;mid] r = mid else: # antes de mid no hubo ningun ciclo, el # rango es ahora: [mid+1; l] l = mid+1 t = l #no se va a usar anyway x = l-1 #el valor X que necesitamos

Ya encontrado el valor de X quedaría realizar un ordenamiento topológico $^{2}$ ~^{2}~ (y obtener la permutacion mas pequeña lexicograficamente $^{3}$ ~^{3}~)

Tiempo: $O(\max(M, N) \log M + N \log N)$ ~O(\max(M, N) \log M + N \log N)~

Bibliografía/referencias:

$^{1}$ ~^{1}~ https://cp-algorithms.com/graph/finding-cycle.html

$^{2}$ ~^{2}~ https://cp-algorithms.com/graph/topological-sort.html

$^{3}$ ~^{3}~ https://www.geeksforgeeks.org/lexicographically-smallest-topological-ordering/

Hope it helps!

(Dejenme subir problemas plis ): )

Edit 1: arreglado el tiempo (DFS * busqueda binaria + ordenamiento topologico) Edit 2: Cambiado condiciones->observaciones

1

linkyless commented on April 4, 2024, 7:26 p.m.

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!

3

karellgz commented on April 4, 2024, 9:48 p.m.

JASKJDSAKJD agradecimientos colega <3

Pero no creo que me dejen crear problemas