Connection Status:
Competition Arena > KingdomAndDice

KingdomAndDice

SRM 548 · 2012-06-05 · by fushar

SRM 548 · 2012-06-05 · by fushar · Dynamic Programming, Simulation
Class Name: KingdomAndDice
Return Type: double
Method Name: newFairness
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

King Dengklek has two N-sided dice. The dice are not necessarily equal. Each of the dice is fair: when rolled, each side will come up with probability 1/N. Some time ago, each side of each die was labeled by a positive integer between 1 and X, inclusive. The labels were all unique. In other words, exactly 2*N distinct integers were used to label the sides of the two dice.

King Dengklek has been playing with the first die for a long time. Therefore, some of its labels were scratched off. The corresponding sides of the die are now empty. The second die still has all of its labels.

The current labels on the first die are given in the int[] firstDie: if the i-th side has no label, firstDie[i] is 0, otherwise firstDie[i] is the label. The current labels on the second die are given in secondDie: the i-th side of the second die has the label secondDie[i].

In King Dengklek's favorite game, he takes one of the dice, his opponent takes the other, and they each roll the die they have. The one who throws a larger number is the winner. King Dengklek wants to fill in the missing labels on the first die. His goal is to fill them in such a way that his favorite game becomes as fair as possible.

When filling in the missing labels, King Dengklek wants to preserve the two properties mentioned above: first, each integer between 1 and X, inclusive, may only occur at most once on the two dice. Second, no other labels may be used. However, there is an exception to the second rule: King Dengklek is also allowed to use the label 0. Moreover, he may even use this label multiple times.

You are given the int[]s firstDie and secondDie, and the int X. For a particular way to fill in the missing labels, let P be the probability that the player with the first die wins in the king's game. Find the labeling that minimizes the value |P - 0.5| and return the corresponding value of P. If there are two possible solutions, return the smaller one.

Notes

  • Your return value must have a relative or an absolute error of less than 1e-9.
  • |x| denotes the the absolute value of x. For example, |3| = |-3| = 3.

Constraints

  • firstDie and secondDie will contain the same number of elements, between 2 and 50, inclusive.
  • X will be between 2*N and 1,000,000,000, inclusive, where N is the number of elements in firstDie.
  • Each element of firstDie will be between 0 and X, inclusive.
  • Each element of secondDie will be between 1 and X, inclusive.
  • Each integer between 1 and X, inclusive, will occur at most once in firstDie and secondDie together.
Examples
0)
{0, 2, 7, 0}
{6, 3, 8, 10}
12
Returns: 0.4375

One possible solution is to relabel the first die into {4, 2, 7, 11}. The probability of winning against the second die will be 7/16.

1)
{0, 2, 7, 0}
{6, 3, 8, 10}
10
Returns: 0.375

One possible solution is to relabel the first die into {9, 2, 7, 5}. The probability of winning against the second die will be 3/8.

2)
{0, 0}
{5, 8}
47
Returns: 0.5

One possible solution is to relabel the first die into {10, 0}.

3)
{19, 50, 4}
{26, 100, 37}
1000
Returns: 0.2222222222222222

The first die does not have any missing labels.

4)
{6371, 0, 6256, 1852, 0, 0, 6317, 3004, 5218, 9012}
{1557, 6318, 1560, 4519, 2012, 6316, 6315, 1559, 8215, 1561}
10000
Returns: 0.49

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

Coding Area

Language: C++17 · define a public class KingdomAndDice with a public method double newFairness(vector<int> firstDie, vector<int> secondDie, int X) · 148 test cases · 2 s / 256 MB per case

Submitting as anonymous