Statistics

Problem Statement for "TwoFairDice"

Problem Statement

Alice and Bob are going to play a simple dice game.

In the game, each player has their own six-sided die. Each player rolls their die and they look at the numbers they rolled. Whoever has the bigger number wins. If both numbers are the same, the game ends in a tie (nobody wins).


Alice and Bob like to play the game with custom dice. These don't have numbers 1 to 6 on their sides. Instead, the players choose what numbers they put onto their dice. They can choose any integer between 0 and 1000, inclusive, for each face. They can also put the same number on multiple faces of their die.


The game is considered fair if each player has the same probability of winning it.

Alice has already chosen the numbers on her die. You are given these in the int[] A. Bob has already chosen some of the six numbers on his die. You are given these in the int[] B.

Bob wants to choose the remaining numbers for his die so that his game with Alice will be fair. Can he do that? If yes, how many different options does he have? Count them and return their count. Remember that each of Bob's missing numbers must also be an integer between 0 and 1000, inclusive.

Definition

Class:
TwoFairDice
Method:
finish
Parameters:
int[], int[]
Returns:
long
Method signature:
long finish(int[] A, int[] B)
(be sure your method is public)

Notes

  • Treat the ways of adding the numbers to Bob's die as ordered sequences of integers. For example, adding {1, 2, 2} and adding {2, 2, 1} should be counted as two separate options.
  • (Equivalently, imagine that each of the faces of Bob's die is painted in a different color, and two ways are only equal if both numbers and colors match.)

Constraints

  • A will have exactly 6 elements.
  • Each element of A will be between 0 and 1000, inclusive.
  • B will have between 0 and 6 elements, inclusive.
  • Each element of B will be between 0 and 1000, inclusive.

Examples

  1. {1, 2, 3, 4, 5, 6}

    {6, 2, 3, 1, 5}

    Returns: 1

    The only way to make these two dice fair is to add the number 4 onto Bob's last face, thus creating two dice with the exact same probability distribution.

  2. {1, 2, 3, 4, 5, 6}

    {7, 8, 9, 10}

    Returns: 0

    Regardless of what two numbers we add to Bob's die, he will be the favorite in the game. There is no way to make these two dice fair.

  3. {1, 2, 3, 4, 5, 6}

    {7, 8, 9}

    Returns: 1

    The only way to make these two dice fair is to add three zeros.

  4. {500, 500, 500, 500, 500, 500}

    {}

    Returns: 312505625007500001

    Some of the very many ways to create a fair die for Bob in this test case include {500, 500, 500, 500, 500, 500}, {500, 100, 500, 500, 987, 500}, {987, 100, 500, 500, 500, 500}, and {1, 2, 3, 999, 998, 997}.

  5. {2, 4, 6, 8, 10, 12}

    {1, 3, 5, 9, 11, 13}

    Returns: 1

    Both dice are already complete and they happen to be fair, so there's exactly one valid way of finishing Bob's die: do nothing :)

  6. {10, 20, 30, 40, 50, 60}

    {}

    Returns: 25276563851453

  7. {10, 10, 11, 12, 12, 12}

    {11, 12, 12}

    Returns: 3

    The only way that works here is adding a 12 and two 10s, thus making the two dice essentially equivalent. This should be counted as three ways: we can add {10, 10, 12}, {10, 12, 10}, or {12, 10, 10}.

  8. {10, 10, 11, 12, 12, 12}

    {10, 10, 10, 12}

    Returns: 1976

    Here we cannot make the two dice have the same multiset of values: Bob's die already has more 10s than Alice. But we can still make the game fair: we have to add one 12 and one number greater than 12 (i.e., anything in the 13-1000 range).

  9. {440, 566, 566, 440, 64, 566}

    {64, 64, 64, 584, 351}

    Returns: 0

  10. {939, 939, 741, 559, 939, 9}

    {939, 939, 939, 920}

    Returns: 1116

  11. {807, 780, 860, 244, 860, 860}

    {936, 36, 957, 200, 746, 200}

    Returns: 0

  12. {426, 762, 762, 112, 791, 762}

    {791, 112, 893, 619}

    Returns: 112227

  13. {388, 116, 642, 388, 861, 642}

    {}

    Returns: 79018277705221144

  14. {523, 523, 832, 637, 523, 637}

    {559, 821, 523, 821}

    Returns: 0

  15. {974, 974, 849, 974, 974, 322}

    {441}

    Returns: 170994113450

  16. {401, 352, 401, 352, 110, 110}

    {273, 401, 68, 401, 273}

    Returns: 48

  17. {580, 577, 10, 577, 711, 577}

    {}

    Returns: 12640974062307356

  18. {309, 309, 309, 309, 309, 309}

    {55, 900}

    Returns: 273544742395

  19. {423, 423, 423, 423, 423, 423}

    {427, 362, 427, 423, 423}

    Returns: 423

  20. {800, 800, 800, 800, 800, 800}

    {800, 294, 800}

    Returns: 96000600

  21. {471, 1000, 283, 653, 962, 653}

    {470, 557, 962, 283}

    Returns: 1371

  22. {900, 900, 900, 900, 900, 900}

    {}

    Returns: 14580729002700001

  23. {976, 414, 828, 312, 976, 312}

    {835, 856, 414, 976}

    Returns: 624

  24. {214, 214, 214, 214, 215, 296}

    {214}

    Returns: 6195381007380

  25. {28, 28, 0, 28, 0, 886}

    {532, 628, 886}

    Returns: 0

  26. {515, 583, 583, 515, 583, 515}

    {525}

    Returns: 94001637165007

  27. {638, 79, 638, 79, 638, 638}

    {420, 638, 61, 420, 61}

    Returns: 0

  28. {466, 759, 759, 466, 644, 759}

    {125, 104, 410}

    Returns: 13997521

  29. {442, 335, 517, 335, 442, 517}

    {323, 76}

    Returns: 173736930586

  30. {528, 659, 659, 229, 659, 229}

    {519, 83}

    Returns: 62139773920

  31. {625, 485, 625, 485, 7, 603}

    {}

    Returns: 112663620938105790

  32. {864, 864, 864, 864, 864, 886}

    {145, 864, 886, 145, 187, 81}

    Returns: 0

  33. {939, 321, 939, 92, 92, 656}

    {787, 572, 830, 830}

    Returns: 61912

  34. {360, 816, 531, 360, 533, 435}

    {}

    Returns: 59521016031640441

  35. {98, 127, 596, 791, 791, 791}

    {127, 866, 447, 447, 98}

    Returns: 209

  36. {505, 145, 333, 505, 333, 145}

    {333, 792}

    Returns: 811089140

  37. {923, 378, 923, 923, 923, 378}

    {378, 207, 378}

    Returns: 17787

  38. {578, 741, 741, 578, 578, 741}

    {502}

    Returns: 89466784976360

  39. {532, 375, 353, 353, 375, 532}

    {}

    Returns: 120064929967704036

  40. {232, 209, 232, 232, 232, 209}

    {232, 951, 432, 209}

    Returns: 418

  41. {340, 340, 340, 410, 410, 410}

    {933, 410}

    Returns: 933594036

  42. {840, 840, 840, 842, 842, 840}

    {}

    Returns: 46759388722784375

  43. {963, 952, 952, 963, 691, 691}

    {963, 691}

    Returns: 8166365245

  44. {746, 474, 416, 746, 746, 737}

    {416, 416}

    Returns: 1624666296

  45. {998, 692, 692, 692, 692, 831}

    {228, 228, 590, 88, 831}

    Returns: 0

  46. {268, 656, 656, 268, 656, 268}

    {655, 151, 604, 247}

    Returns: 118336

  47. {171, 171, 874, 171, 594, 891}

    {891, 594, 594}

    Returns: 373977

  48. {948, 948, 948, 980, 980, 316}

    {620, 948}

    Returns: 2169856

  49. {538, 538, 781, 781, 36, 538}

    {401, 103}

    Returns: 9081124072

  50. {879, 879, 816, 422, 40, 40}

    {331, 492, 734, 331}

    Returns: 96832

  51. {784, 784, 784, 540, 784, 784}

    {}

    Returns: 31737982363404486

  52. {918, 918, 960, 960, 389, 918}

    {960, 623, 389, 176, 176}

    Returns: 0

  53. {265, 265, 265, 265, 265, 265}

    {}

    Returns: 147788168947587001

  54. {381, 664, 545, 381, 230, 381}

    {545, 230, 230, 623, 693, 623}

    Returns: 0

  55. {301, 301, 301, 301, 301, 301}

    {38, 212, 38}

    Returns: 341532099

  56. {108, 429, 429, 153, 108, 153}

    {873, 908, 908}

    Returns: 1259712

  57. {93, 93, 93, 93, 93, 93}

    {321, 321, 708, 708, 93, 93}

    Returns: 0

  58. {784, 271, 271, 784, 60, 809}

    {468, 60, 468, 523}

    Returns: 1024

  59. {891, 891, 891, 845, 891, 845}

    {845}

    Returns: 1324431755

  60. {619, 619, 903, 903, 885, 645}

    {}

    Returns: 29902527824654681

  61. {711, 952, 952, 952, 475, 711}

    {}

    Returns: 5865097892561715

  62. {626, 331, 626, 331, 626, 626}

    {626, 331, 164, 298, 164}

    Returns: 0

  63. {542, 775, 542, 566, 566, 775}

    {291}

    Returns: 63669708105575

  64. {463, 536, 536, 536, 544, 544}

    {571}

    Returns: 207266173338570

  65. {760, 520, 872, 520, 520, 281}

    {281, 820, 281, 281, 982}

    Returns: 1

  66. {331, 331, 331, 331, 331, 331}

    {560, 331}

    Returns: 879557032

  67. {80, 80, 892, 80, 892, 80}

    {}

    Returns: 23185093298677475

  68. {305, 305, 305, 305, 282, 282}

    {282, 771, 638, 200, 771}

    Returns: 0

  69. {13, 14, 2, 2, 2, 13}

    {10, 13, 12, 1, 14, 8}

    Returns: 0

  70. {1, 7, 11, 7, 13, 1}

    {10, 13, 8, 14, 7, 6}

    Returns: 0

  71. {1, 8, 15, 1, 1, 9}

    {14, 12, 11, 9}

    Returns: 0

  72. {1, 1, 15, 8, 8, 1}

    {1}

    Returns: 364335230

  73. {4, 4, 4, 4, 4, 4}

    {}

    Returns: 1266129980641

  74. {8, 1, 8, 1, 1, 0}

    {0, 1, 15, 1, 6}

    Returns: 1

  75. {1, 7, 12, 1, 7, 7}

    {1, 7, 7, 12}

    Returns: 2

  76. {10, 15, 10, 15, 2, 2}

    {1, 10, 13, 15}

    Returns: 3999

  77. {9, 13, 0, 0, 13, 13}

    {15, 0}

    Returns: 795312

  78. {15, 8, 1, 1, 15, 9}

    {1, 9}

    Returns: 692236

  79. {9, 12, 9, 12, 8, 8}

    {}

    Returns: 9895596022621

  80. {3, 5, 13, 5, 5, 3}

    {10, 10, 13, 10, 13, 10}

    Returns: 0

  81. {2, 1, 5, 1, 5, 5}

    {14, 12, 1, 15, 13}

    Returns: 0

  82. {2, 2, 2, 2, 2, 2}

    {13, 3, 3, 13}

    Returns: 0

  83. {12, 10, 12, 12, 10, 12}

    {}

    Returns: 19308614544775

  84. {2, 7, 7, 8, 7, 2}

    {15, 7, 2, 7, 2}

    Returns: 0

  85. {3, 3, 3, 3, 3, 7}

    {4, 2, 5, 4, 7, 3}

    Returns: 0

  86. {2, 11, 1, 10, 6, 3}

    {13}

    Returns: 10972025

  87. {2, 9, 9, 2, 2, 9}

    {8}

    Returns: 777235956

  88. {11, 9, 13, 1, 9, 13}

    {8, 11, 1, 1, 11}

    Returns: 0

  89. {2, 2, 6, 6, 2, 5}

    {5, 9, 6, 7}

    Returns: 0

  90. {10, 10, 10, 12, 10, 10}

    {13, 13, 1, 1, 13, 13}

    Returns: 0

  91. {12, 12, 12, 12, 12, 12}

    {6, 6}

    Returns: 46298509920

  92. {1, 14, 13, 13, 1, 13}

    {}

    Returns: 107428155265

  93. {6, 6, 6, 6, 6, 6}

    {7, 4, 4, 7}

    Returns: 11929

  94. {12, 12, 12, 14, 14, 2}

    {1}

    Returns: 42050031030

  95. {9, 15, 15, 15, 15, 15}

    {15, 13}

    Returns: 58225320

  96. {12, 1, 12, 12, 12, 8}

    {}

    Returns: 62376600680

  97. {11, 11, 11, 11, 5, 1}

    {13}

    Returns: 22441090

  98. {7, 9, 9, 9, 9, 7}

    {14, 7, 7, 4, 9}

    Returns: 991

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.
This problem was used for: