ShufflingCardsDiv1 | Topcoder Archive

Problem Statement

Fox Ciel likes shuffling cards. She uses a deck with 2N cards, numbered 1 through 2N. Initially, this deck is sorted: the cards are in the order 1,2,3,...,2N from top to bottom.
Ciel always uses the same procedure when shuffling. One round of shuffling looks as follows:

She splits the deck into two piles: the top N cards will be pile A, the bottom N cards pile B.
She takes pile A and rearranges the cards it contains arbitrarily.
She takes pile B and rearranges the cards it contains arbitrarily.
She interleaves the cards from the two piles, producing a single deck again. More precisely, if pile A has cards A1,A2,...,AN and pile B has cards B1,B2,...,BN then the new deck will be A1,B1,A2,B2,...,AN,BN. (Note that the first card must be from pile A.)

For example, let N=2 and suppose that Ciel starts with the sorted deck 1,2,3,4. After the first round of shuffling, she can produce one of the following four decks:

1,3,2,4
1,4,2,3
2,3,1,4
2,4,1,3

You are given a int[] permutation which contains a permutation of the 2N cards. Ciel wants to produce this permutation of her deck. Compute and return the smallest number of rounds of shuffling she has to perform. (When rearranging a pile during the shuffling, she can always pick the best possible order of those cards.) If Ciel cannot reach the given permutation by shuffling, return -1 instead.

Definition

Class:: ShufflingCardsDiv1
Method:: shuffle
Parameters:: int[]
Returns:: int
Method signature:: int shuffle(int[] permutation)
(be sure your method is public)

Constraints

permutation will contain between 4 and 2000 elements, inclusive.
The number of elements in permutation will be even.
The elements of permutation will form a permutation of the numbers 1 through 2N, where 2N is the number of elements in permutation.

Examples

```
{1,2,3,4}
```
```
Returns: 0
```
There's no need to shuffle the deck at all.
```
{1,4,3,2}
```
```
Returns: 2
```
One optimal solution: In the first round, pile A will be 1,2 and pile B will be 3,4. She then merges them to produce the deck 1,3,2,4. In the second round, pile A will be 1,3 and pile B will be 2,4. She rearranges pile B to 4,2 and then merges the two piles to produce the desired deck 1,4,3,2.
```
{6,3,5,2,4,1}
```
```
Returns: 4
```
```
{8,5,4,9,1,7,6,10,3,2}
```
```
Returns: 2
```
```
{9,1,7,2,10,3,6,4,8,5}
```
```
Returns: 4
```

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.