PlaylistShuffler | Topcoder Archive

Problem Statement

Recently, Philip bought a new audio player. After toying with it a bit, he noticed that the player was pretty strange. It is only capable of playing N different songs that were pre-loaded by the manufacturer. These songs are arranged in a playlist which contains N positions, numbered 0 to N-1. Each song is in a distinct position of the playlist.

The player has a "Shuffle" button which changes the order of songs in the playlist as follows:

The user is asked to enter an integer K, which must be between K1 and K2, inclusive.
The player generates a random permutation P = (p[0], p[1], ..., p[N-1]) of integers between 0 and N-1, inclusive. All possible permutations have the same probability of being generated.
The generated permutation P is applied to the playlist exactly K times. Each application works as follows: for each i, 0 <= i < N, the song at position i of the playlist is moved to position p[i] (these movements occur simultaneously for all N songs).

Philip considers a shuffle to be successful if the song at position X of the playlist before the shuffle appears at position Y after the shuffle. He discovered that the probability of a shuffle being successful may depend on the number K that he enters in the first step of the shuffle process. Return the value of K he must enter to achieve the maximum probability of a successful shuffle. If there are several such values, return the smallest one among them.

Definition

Class:: PlaylistShuffler
Method:: bestShuffle
Parameters:: int, int, int, long, long
Returns:: long
Method signature:: long bestShuffle(int N, int X, int Y, long K1, long K2)
(be sure your method is public)

Constraints

N will be between 1 and 50, inclusive.
X will be between 0 and N-1, inclusive.
Y will be between 0 and N-1, inclusive.
K1 will be between 1 and 10,000,000,000 (10^10), inclusive.
K2 will be between K1 and 10,000,000,000 (10^10), inclusive.

Examples

```
2
```
```
0
```
```
1
```
```
2
```
```
4
```
```
Returns: 3
```
Suppose that the songs are called A and B and the initial order is A, B. If the generated permutation is {0, 1}, then the list is just left intact no matter what the value of K is. If the permutation is {1, 0}, the list keeps changing between A, B and B, A consecutively. We want to maximize the probability that the final list is B, A. For K = 2 and K = 4 this probability is 0, and for K = 3 the probability is 0.5.
```
2
```
```
1
```
```
1
```
```
1
```
```
10
```
```
Returns: 2
```
This time we want the final list to be A, B. This happens with probability 1 for every even value of K. The smallest one among them is 2.
```
1
```
```
0
```
```
0
```
```
1111111111
```
```
9999999999
```
```
Returns: 1111111111
```
Since there is just 1 song, all values of K lead to the same final result.
```
10
```
```
3
```
```
7
```
```
1000
```
```
10000
```
```
Returns: 1003
```

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.