Problem Statement
DJ Jeipouju likes a single-player music game called BM Mania.
In this game, the player has a controller with keyCount keys, arranged in a row and conveniently numbered 0 through keyCount-1, in order.
When starting a game, the player selects a song.
The game takes the musical score of the song and assigns each note to one of the keys of the controller.
The goal of the game is to "play" the song by hitting the corresponding keys of the controller at appropriate times.
The player also has a computer screen that shows him the keys he will have to hit in the future. During the game, the keys that the player has to hit are shown to the player as lanes: For each key of the controller, there is a column on the screen with downwards moving markers, each representing a keystroke. Whenever a marker reaches the bottom of the screen, the player must press the corresponding key.
A simple scheme of the game screen with 5 keys is shown below. Dashes ('-') represent the markers, equals signs ('=') are the bottom of the screen. For convenience, we show the corresponding key numbers below.
Jeipouju is a pretty good player. Recently, he tried to play a difficult song, but he always failed at the same place in the song. The reason of his failure was the fact that he was unable to play a combination of keystrokes that appeared in two adjacent lanes. However, he can easily play the same combination on any pair of non-adjacent keys.
Luckily for Jeipouju, the game has an option to randomly permute the lanes of a song. The figure below shows one possible outcome of activating the random option. In the figure, the original lane 0 is now on the key 4, lane 1 moved to key 0, lanes 2 and 3 stayed on their respective keys, and lane 4 moved to the key 1.
Jeipouju thinks that there are several pairs of lanes that will cause him to fail if they are assigned to adjacent keys. For each i, one such pair is badLane1[i] and badLane2[i]. More precisely, Jeipouju will win the game if and only if for all i the lanes badLane1[i] and badLane2[i] are assigned to non-adjacent keys.
You are given the int keyCount and two int[]s: badLane1 and badLane2. Return the probability that Jeipouju will win the game after the lanes have been randomly permuted.
The player also has a computer screen that shows him the keys he will have to hit in the future. During the game, the keys that the player has to hit are shown to the player as lanes: For each key of the controller, there is a column on the screen with downwards moving markers, each representing a keystroke. Whenever a marker reaches the bottom of the screen, the player must press the corresponding key.
A simple scheme of the game screen with 5 keys is shown below. Dashes ('-') represent the markers, equals signs ('=') are the bottom of the screen. For convenience, we show the corresponding key numbers below.
| | | | | | | |-| | | | | |-| | |-| |-| |-|-| | |-| | |-|-| | | |-|-| | |-| | | |-| =========== |0|1|2|3|4|
Jeipouju is a pretty good player. Recently, he tried to play a difficult song, but he always failed at the same place in the song. The reason of his failure was the fact that he was unable to play a combination of keystrokes that appeared in two adjacent lanes. However, he can easily play the same combination on any pair of non-adjacent keys.
Luckily for Jeipouju, the game has an option to randomly permute the lanes of a song. The figure below shows one possible outcome of activating the random option. In the figure, the original lane 0 is now on the key 4, lane 1 moved to key 0, lanes 2 and 3 stayed on their respective keys, and lane 4 moved to the key 1.
original permuted
song lanes
| | | | | | | | | | | |
|-| |-| | | | | |-| |-|
| |-| | | | |-| | | | |
|-| | |-| | random activated | | | |-|-|
| |-| | | | =================> |-| | | | |
|-|-| | | | |-| | | |-|
|-| | | | | | | | | |-|
| |-| |-|-| |-|-| |-| |
=========== ===========
|0|1|2|3|4| |0|1|2|3|4|
Jeipouju thinks that there are several pairs of lanes that will cause him to fail if they are assigned to adjacent keys. For each i, one such pair is badLane1[i] and badLane2[i]. More precisely, Jeipouju will win the game if and only if for all i the lanes badLane1[i] and badLane2[i] are assigned to non-adjacent keys.
You are given the int keyCount and two int[]s: badLane1 and badLane2. Return the probability that Jeipouju will win the game after the lanes have been randomly permuted.
Definition
- Class:
- RandomOption
- Method:
- getProbability
- Parameters:
- int, int[], int[]
- Returns:
- double
- Method signature:
- double getProbability(int keyCount, int[] badLane1, int[] badLane2)
- (be sure your method is public)
Notes
- The permutation of lanes is chosen uniformly at random from the set of all possible permutations.
- Your return value must have a relative or an absolute error of less than 1e-9.
Constraints
- keyCount will be between 5 and 14, inclusive.
- badLane1 will contain between 1 and 50 elements, inclusive.
- badLane2 will contain the same number of elements as badLane1.
- Each element of badLane1 and badLane2 will be between 0 and keyCount - 1, inclusive.
- For all i, badLane1[i] and badLane2[i] will be distinct.
- All the pairs of bad lanes will be distinct.
Examples
5
{0}{3}Returns: 0.6
There are 5 keys and only one bad pair. The probability that these lanes are assigned to adjacent keys is 4 / (5 choose 2) = 0.4, so the probability that we have a good arrangement is 1 - 0.4 = 0.6.5
{0, 1, 2}{1, 2, 0}Returns: 0.1
In a good arrangement, no two of the lanes 0, 1, and 2 may be adjacent. Hence they have to be assigned to keys 0, 2, and 4, in some order. The probability of this event is (3! * 2!) / 5! = 0.1.5
{2, 2, 2, 2}{0, 1, 3, 4}Returns: 0.0
All the pairs of lane 2 and other lanes are bad, so it is impossible to obtain a good arrangement.7
{0, 1, 2}{6, 5, 4}Returns: 0.3904761904761904
7
{3, 5, 1, 0, 2, 6, 4}{0, 2, 4, 6, 1, 5, 3}Returns: 0.09166666666666667
Back to all problems