Problem Statement |
| |
There are two teams A and B, each with exactly n members, that will compete in a contest to decide which team is better. The contest consists of n one-on-one fights, where a member of team A fights a member of team B. A valid fight arrangement of the teams assigns each member of team A to a distinct member of team B. All valid pairings are equally likely to be chosen. For example, if each team has 2 fighters (A1, A2 and B1, B2), there are two possible assignments: (A1 vs. B2, A2 vs. B1) and (A1 vs. B1, A2 vs. B2). Each of those assignments has a 50% chance of being chosen.
Each fighter has a non-negative integer strength. If fighters with strengths X and Y are matched in a fight, the team of the fighter with the greater strength is awarded (X-Y)2 points. If both have equal strength, the fight ends in a tie and no team is awarded any points. After all the fights are finished, each team adds up their points. The winning margin of team A is their point total minus team B's point total. You must calculate and return the expected value of that number.
To keep the input small, it will be codified in the following way. You will be given two int[]s A and B representing team A and B, respectively. Use the following pseudo-code on each of the int[]s to generate the strengths of that team's members (array indices are 0-based):
input array: X
output array: R (of size n)
j := 0
m := size of X
for i := 0 to n-1
R[i] := X[j]
s := (j+1)%m
X[j] := ( ( X[j] ^ X[s] ) + 13 ) % 49999
j := s
This code, along with the constraints, ensures that each member's strength is between 0 and 49998, inclusive. In the above code, % is the modulo operator and ^ is the bitwise XOR binary operator. See the notes section for information on performing XOR in your language.
|
| |
Definition |
| | | Class: | RandomFights | | Method: | expectedNrOfPoints | | Parameters: | int[], int[], int | | Returns: | double | | Method signature: | double expectedNrOfPoints(int[] A, int[] B, int n) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The input is only coded for convenience. The intended solution does not rely at all in a property of the way it is generated, it just generates both arrays and works on them. |
| - | The returned value must have an absolute or relative error less than 1e-9. |
| - | If x and y are ints, (x^y) represents the bitwise XOR operation on them in C++, Java, C# and Python. In VB.Net (x BitXor y) does it. |
| |
Constraints |
| - | A and B will each contain between 1 and 50 elements, inclusive. |
| - | Each element of A and B will be between 0 and 49998, inclusive. |
| - | n will be between 1 and 50000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 4.0 | | The winning margin of A is always (6-4)2=4. |
|
|
| 1) | |
| | | Returns: 0.0 | | There are two possible assignments here: (1 vs. 3) and (7 vs. 5), or (1 vs. 5) and (7 vs. 3). In the first case, each team gets 4 points, so the winning margin of A is 0. In the second case, each team gets 16 points, so the winning margin is also 0. Since the winning margin is 0 in every case, the expected value is, of course, 0. |
|
|
| 2) | |
| | | Returns: 20.0 | | The two possible assignments in this case are: (3 vs. 1) and (7 vs. 5), or (3 vs. 5) and (7 vs. 1). The winning margin in the first case is 4+4=8, and in the second case, it is 36-4=32. Since both assignments are equally likely to be chosen, the expected value is the average of the two margins. |
|
|
| 3) | |
| | {45,35,236,2342,5543,21,32,2,6,23,24,23,41,1} | {2345,45,2345,345} | 50 |
| Returns: 1.2721986164E8 | | A and B can have different lengths. Each one is generated separately. |
|
|
| 4) | |
| | {34,3245,2534,53,53,46,346,246,346,2,624,624,6,245,6324,6542,624,6} | {345,234,523,4624,6,2456,345,634,634,7,3457,376,34,6234,62,523,52,35,32} | 7 |
| Returns: -9713701.714285715 | | You can have extra unused elements in the input. |
|
|
| 5) | |
| | | Returns: 0.0 | | If both teams are that even, neither of them can take advantage. |
|
|