SPOJ: barajamiento de cartas

Question

Recientemente comencé a resolver preguntas sobre jueces en línea. Estoy atascado en this question in SPOJ:

Aquí es un algoritmo para barajar cartas N:

1. Las tarjetas se dividen en pilas iguales K, donde K es un factor de N.
2. La parte inferior N/Las cartas K pertenecen a la pila 1 en el mismo orden (por lo que la carta inferior de la pila inicial es la carta inferior de la pila 1).
3. Las siguientes cartas N/K de la parte inferior pertenecen al montón 2, y así sucesivamente.
4. Ahora la primera carta de la pila mezclada es la carta superior de la pila 1. La siguiente carta es la carta superior de la pila 2, ..., la carta K de la pila mezclada es la carta superior de la pila K. Luego (K + 1) es la carta que está ahora en la parte superior de la pila 1, la (K + 2) nd es la carta que ahora está en la parte superior de la pila 2, y así sucesivamente.

Por ejemplo, si N = 6 y K = 3, el orden de una baraja de cartas "ABCDEF" (de arriba a abajo) cuando se baraja una vez cambiará a "ECAFDB".

Dados N y K, ¿cuál es el menor número de barajados necesarios después de los cuales la pila se restaura a su orden original?

---

He intentado simular pero excede el límite de tiempo. ¿Hay alguna ecuación matemática?

Answer 1

Sí, hay una solución matemática para este problema.

Primero permítanme comenzar con algunos consejos sobre cómo abordar estos problemas y luego daré algunos consejos sobre la solución real. No terminaré del todo, de modo que todavía queda algo de desafío.

Entonces: ¿cómo abordar estos problemas? Lo que hiciste es realmente un buen comienzo. Escribe una simulación y compárala contra algunos casos pequeños. La simulación debería ser bastante rápida allí. Ahora tienes más valores. Anótelos en un pedazo de papel y comience a mirarlos. Debe tener una instancia si K = x y N = y , entonces el resultado es z y muchos más pares. Intenta encontrar alguna fórmula. Concéntrese en triples que tienen un valor fijo para x, para y o para z. ¿Qué tienen en común? Y así. Tú miras y usualmente obtienes una idea brillante después de un tiempo :)

Ahora: algunos consejos sobre este problema en particular. Haz una sola iteración de la barajadura y anota dónde va cada carta. Por ejemplo, la tarjeta 1 va en la posición 3, la tarjeta 3 va en la posición 2 y así sucesivamente. Tenga en cuenta que algunas cadenas se formarán de esta manera; por ejemplo, en el ejemplo n = 6, k = 3, tenemos una cadena de longitud 6: 1-> 3-> 2-> 6-> 4-> 5-> 1 . Ahora calcule las longitudes de todas las cadenas (cada tarjeta pertenecerá exactamente a una cadena) e intente encontrar cómo depende la respuesta de estas longitudes.

Espero que esto sea suficiente para ayudarlo a resolver el problema.

EDITAR: echar un vistazo a las restricciones que simulan que incluso una sola iteración puede ser muy lenta. Si ese es el caso, después de haber hecho lo que le aconsejo en mi segundo consejo, intente calcular las longitudes de las cadenas sin tener que simular una mezcla