ShuffleMethod | Topcoder Archive

Problem Statement

You will be given a int[] twoShuffle with k elements denoting a method for shuffling a deck of cards. The deck in question will have k cards numbered 1 through k inclusive. Initially, all of the cards in the deck are arranged in ascending order. The ith (1-based) element of twoShuffle describes which card is in position i (1-based) after 2 identical shuffling procedures have completed. You will return a int[] that is exactly like the input, except it describes what a single shuffle would do. A shuffling procedure describes how the relative positions of the cards will change due to the shuffle. More precisely, if element s of a shuffling procedure is p, then the card that was in position p ends up in position s (again, all 1-based). For example,

	twoShuffle = {3,4,1,2}

means that after two shuffles

	the deck   1,2,3,4   would become  3,4,1,2.

You would return {2,3,4,1} since:

	the deck 1,2,3,4  -    after one shuffle  - 2,3,4,1 
		          - after another shuffle - 3,4,1,2.

If there are no possible solutions, return an empty int[]. If there is more than 1 possible solution, return the one that comes first lexicographically. A shuffle X comes lexicographically before a shuffle Y if there is a position j such that, X[i]=Y[i] for all i<j, and X[j]<Y[j].

Definition

Class:: ShuffleMethod
Method:: oneTime
Parameters:: int[]
Returns:: int[]
Method signature:: int[] oneTime(int[] twoShuffle)
(be sure your method is public)

Constraints

twoShuffle will contain between 3 and 50 elements inclusive.
Each element of twoShuffle will be between 1 and k inclusive, where k is the number of elements in twoShuffle.
twoShuffle will contain no duplicate elements.

Examples

```
{3,4,1,2}
```
```
Returns: { 2,  3,  4,  1 }
```
The example from above.
```
{1,2,3,4}
```
```
Returns: { 1,  2,  3,  4 }
```
The cards are unshuffled. Since 1,2,3,4 is a valid solution, and is lexicographically first, it is the return value. 2,1,4,3 is another valid solution, but it does not come before 1,2,3,4 lexicographically.
```
{5,1,2,3,4}
```
```
Returns: { 3,  4,  5,  1,  2 }
```
Using the shuffle 3,4,5,1,2 twice we see that 1 -> 3 -> 5 2 -> 4 -> 1 3 -> 5 -> 2 4 -> 1 -> 3 5 -> 2 -> 4 In other words, the deck is transformed as follows: 1,2,3,4,5 -> 3,4,5,2,3 -> 5,1,2,3,4

{2,4,6,5,1,8,10,9,3,12,11,13,7,15,16,17,14}

Returns: { 3,  6,  2,  8,  9,  4,  14,  5,  1,  15,  11,  16,  17,  10,  12,  13,  7 }

{2,4,6,5,1,8,10,9,3,12,11,13,7}

Returns: { }

{10,9,12,8,13,3,4,1,5,11,6,2,7}

Returns: { 9,  1,  4,  12,  11,  7,  3,  2,  10,  5,  13,  8,  6 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.