This question was asked before, but none of them received a definitive answer, and I tried to collect all the information I found here. Feel free to merge / switch to another stackexchange site if necessary.
Here are the questions I found in connection with this:
The problem was originally posted as Sprint Sprinter Sprinter, but now it is listed as a problem with practice . It has also been ported to SPOJ .
Here is a description of the problem:
Here is the N-card shuffling algorithm:
1) Cards are divided into K equal piles.
2) The bottom N / K cards belong to heap 1 in the same order (so the bottom card of the starting heap is the bottom card of heap 1).
3) The following N / K cards from the bottom belong to heap 2, etc.
4) Now the top card of the shuffled heap is the top card of pile 1. The next card is the top card of piles 2, ..., the card Kth of the shuffled heap is the top> card of piles K. Then the (K + 1) -th card is a card , which is now at the top of pile 1, (K + 2) nd is the card that is now at the top of pile 2, etc.
For example, if N = 6 and K = 3, the order of the deck of cards "ABCDEF" (from top to bottom) during shuffling will be changed to "ECAFDB" once.
Given N and K, what is the minimum number of transfers required after the heap is returned to its original order?
Input: the first line contains the number of test cases T. The next T lines contain two integers N and K.
Output: output lines T, one for each test case containing the minimum required amount of shuffling. If the deck never returns to its original order, output -1.
Limitations:
- K is a factor of N.
- T <= 10000
- 2 <= K <= N <= 10 ^ 9
Spoiler warning - do not read below if you want to solve it yourself.
The problem can be translated as:
Find the number of times you need to complete a K-shaped (perfect) in-shuffle to restore a deck of N cards to its original order.
I decided two approaches to solving this problem. The first approach that came to mind was as follows:
- find the formula that, for a given position in the initial order, will create the next map the next position
- use the formula to determine the number of shuffles that each card takes from the first pile (n / k in size) to return to its original position.
- returns the smallest total multiple of the number of shuffles defined previously
The complexity of this solution is O (n / k + max_number_of_suhffles). Here is the actual implementation . The problem is that it exceeds the maximum time, so I started looking for a formula that would allow me to get the number in almost constant time.
The most that I could optimize here (for example, use some cards to cache calculated values in the same permutation cycle, etc.) was to pass the 3/10 interview test.
I found this implementation , which suggests that the amount of shuffling needed to return to its original state is the multiplicative order of K relative to N + 1. From the wiki:
As a consequence of Lagrange theorem, ordn(a) always divides φ(n).
φ (n) is the Euler tolerance function , ordn is the order of the groups - what we are looking for. I found this article that uses φ to calculate the number of shuffles, but this is only for 2-way in-shuffle, not k-way.
Here are the steps for this implementation:
- pre-computed list of primes <100,000
- calculated
φ(N+1) from its simple factors. - defined all factors
φ(N + 1) , combining its prime factors in all possible ways. - tried each factor in turn and got the smallest of them,
x , which checks k ^ x % N + 1 = 1
This implementation is also hosted on GitHub .
This works very fast, but the automatic grader gives me the “wrong answer” for 9 out of 10 tests, both in SPOJ and in the interview.
I tried to compare the result of two implementations, but for the test boxes I entered (known result and random), the two implementations always output the same thing. This is strange, since I am sure that the first algorithm is correct, I assume that the second should also be.
The “incorrect answer” classification may occur due to a code runtime error, but nothing jumps out as a possible reason for this.
I did not take into account the case when no number shuffling can return the deck to its original state - I understand that this is impossible. The final number of perfect shuffles will ultimately restore the original order, although the number of shuffles can be really high.
If you took the time to read this, thanks. :) I'm curious about the problem, I would like it to be resolved.