SPOJ:Card Shuffling

Question

Recently I started solving questions on online judges. I am stuck in this question in SPOJ:

Here is an algorithm for shuffling N cards:

1. The cards are divided into K equal piles, where K is a factor of N.
2. The bottom N / K cards belong to pile 1 in the same order (so the bottom card of the .initial pile is the bottom card of pile 1).
3. The next N / K cards from the bottom belong to pile 2, and so on.
4. Now the top card of the shuffled pile is the top card of pile 1. The next card is the top card of pile 2,..., the Kth card of the shuffled pile is the top card of pile K. Then (K + 1)th card is the card which is now at the top of pile 1, the (K + 2)nd is the card which is now at the top of pile 2 and so on.

For example, if N = 6 and K = 3, the order of a deck of cards "ABCDEF" (top to bottom) when shuffled once would change to "ECAFDB".

Given N and K, what is the least number of shuffles needed after which the pile is restored to its original order?

---

I tried simulating but it exceeds time limit. Is there any mathematical equation?

Answer 1

Yes, there is a mathematical solution for this problem.

First let me start with some tips on how to approach such problems and then I will give some tips on the actual solution. I will not quite finish it so that there is still some challenge left.

So: how to approach such problems? What you did is actually a good start. Write a simulation and run it against some small cases. The simulation should be fairly fast there. Now you have some more values. Write them down on a piece of paper and start staring at them. You have fro instance if K = x₁ and N = y₁ then the result is z₁ and a lot more such pairs. Try to figure some formula. Focus on triples that have a fixed value for x, for y or for z. What do they have in common? And so on. You stare and usually you get a bright idea after some time :)

Now: some tips on this particular problem. Do a single iteration of the shuffling and note where each card goes. For instance card 1 goes in position 3 card 3 goes in position 2 and so on. Note that some chains will be formed this way - for instance in the example n=6, k=3, we have a chain of length 6: 1->3->2->6->4->5->1. Now compute the lengths of all the chains(each card will belong to exactly one chain) and try to find how does the answer depend on these lengths.

Hope this is enough to help you solve the problem.

EDIT: taking a look at the constraints simulating even a single iteration might be very slow. If that is the case, after you have done what I advice in my second tip try calculating the lengths of chains without actually having to simulate one shuffle