SPOJ: shuffling cards

Question

Recently, I began to address issues of online judges. I am stuck with this question in SPOJ :

Here is the N-card shuffling algorithm:

• Cards are divided into K equal piles, where K is a factor N.
• The bottom N / K cards belong to heap 1 in the same order (so the bottom card of the initial heap is the bottom card of heap 1).
• The following N / K cards below are for heap 2, etc.
• Now the top card of the shuffled heap is the top card of heap 1. The next card is the top card of piles 2, ..., the Kth card of the shuffled heap is the top card of heap K. Then the (K + 1) -th card is the card that now located at the top of heap 1, (K + 2) nd is the map that is now at the top of heap 2, etc.

For example, if N = 6 and K = 3, the order of the deck of cards "ABCDEF" (from top to bottom) will be changed once to "ECAFDB" when shuffling.

Given N and K, what is the minimum number of shifts required after restoring a pile to its original order?

---

I tried to simulate, but it exceeds the time limit. Is there a mathematical equation?

Answer 1

Yes, there is a mathematical solution to this problem.

First, let me start with some tips on how to approach such problems, and then I will give some tips on an actual solution. I can’t finish it so that there is still a problem.

So: how to approach such problems? What you did is actually a good start. Write a simulation and run it in some small cases. The simulation should be pretty quick. You now have a few more meanings. Write them on a piece of paper and start looking at them. You have an example, if K = x ₁ and N = y ₁ , then the result is z ₁ and there are much more such pairs. Try to submit a 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 look and usually get a bright idea after a while :)

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

Hope this is enough to help you solve the problem.

EDIT: looking at constraints that mimic even a single iteration can be very slow. If so, then after you have done what I advise in my second tip, try to calculate the chain lengths without having to simulate a single shuffle