Connection Status:
Competition Arena > PlaylistShuffler

PlaylistShuffler

TCO11 Round 5 · 2011-05-07 · by ivan_metelsky

TCO11 Round 5 · 2011-05-07 · by ivan_metelsky · Brute Force, Math
Class Name: PlaylistShuffler
Return Type: long
Method Name: bestShuffle
Arg Types: (int, int, int, long long, long long)
Problem Statement

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:
  1. The user is asked to enter an integer K, which must be between K1 and K2, inclusive.
  2. 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.
  3. 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.

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
0)
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.

1)
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.

2)
1
0
0
1111111111
9999999999
Returns: 1111111111

Since there is just 1 song, all values of K lead to the same final result.

3)
10
3
7
1000
10000
Returns: 1003
4)
1
0
0
1
10000000000
Returns: 1

Submissions are judged against all 211 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PlaylistShuffler with a public method long long bestShuffle(int N, int X, int Y, long long K1, long long K2) · 211 test cases · 2 s / 256 MB per case

Submitting as anonymous