Statistics

Problem Statement for "InTheLead"

Problem Statement

This week the ICPC finals are taking place in Dhaka, Bangladesh. We send them our greetings by theming some of the problems in this SRM.


Three teams were fighting for the lead in an ICPC competition. The first successful submission was made by one of these three teams, and from that point until the end of the competition it was always true that (at least) one of these three teams had the maximum number of problems solved, and no team other than these three ever had this property. For this problem you can therefore safely pretend that the other teams do not exist and the only three teams in the competition are our three teams.


We say that a team is leading clearly if that team currently has strictly more solved problems than any other team.

One time in the lead is a largest possible continuous interval of time during which a particular team was leading clearly. (Except for a team that leads until the end of the contest the interval is half-open: it starts at the moment the team gained the lead and contains all moments until the moment when some other team caught up to them.)


For each of the three teams (x=0,1,2) you are given the total number of problems solved during the competition: solved[x] and the number of times this team was in the lead: lead[x].

A contest history is a sequence of successful submissions made by our three teams - i.e., a sequence of moments when a particular team's number of solved problems increased by 1. There can never be two (or more) submissions made at the same time. A contest history with X events can be represented as a string of 0s, 1s and 2s of length X; each number representing the corresponding team's successful submission. Two contest histories differ if the strings describing them differ.


Count all contest histories consistent with the given information. Return that count modulo 10^9 + 7.

Definition

Class:
InTheLead
Method:
count
Parameters:
int[], int[]
Returns:
int
Method signature:
int count(int[] solved, int[] lead)
(be sure your method is public)

Constraints

  • solved will contain exactly 3 elements.
  • Each element of solved will be between 0 and 24, inclusive.
  • The sum of solved will be positive.
  • lead will contain exactly 3 elements.
  • Each element of lead will be between 0 and 24, inclusive.

Examples

  1. {1, 1, 1}

    {0, 0, 0}

    Returns: 0

    This is impossible. The data claims that none of the teams were ever in the lead. However, as they all solved a problem, one of them had to be the first to solve a problem, and at that point in time that team would be in the lead.

  2. {1, 1, 1}

    {0, 1, 0}

    Returns: 2

    Team 1 (the one that should have been in the lead once) must have been the first team to solve a problem. Afterwards there are two possibilities: either the other two teams each solved a problem in the order team 0, team 2, or they did it in the opposite order.

  3. {1, 1, 1}

    {0, 2, 0}

    Returns: 0

    This is also impossible. One argument that shows why: once you stop being in the lead, you cannot regain the lead without solving at least one additional problem.

  4. {1, 2, 1}

    {0, 2, 0}

    Returns: 4

    Here we can tell that team 1 must have made the very first successful submission of the first contest, and that at least one of teams 0+2 had to solve their only problem before team 1 could solve their second.

  5. {1, 2, 3}

    {1, 1, 1}

    Returns: 3

  6. {4, 5, 6}

    {1, 2, 2}

    Returns: 15631

  7. {24, 24, 24}

    {8, 8, 8}

    Returns: 785165557

  8. {24, 24, 24}

    {9, 8, 7}

    Returns: 942619740

  9. {24, 24, 24}

    {20, 2, 2}

    Returns: 725878448

  10. {24, 24, 24}

    {0, 24, 0}

    Returns: 974672469

  11. {2, 0, 3}

    {0, 2, 1}

    Returns: 0

  12. {4, 3, 3}

    {2, 1, 1}

    Returns: 242

  13. {0, 0, 2}

    {0, 0, 1}

    Returns: 1

  14. {4, 0, 2}

    {2, 1, 1}

    Returns: 0

  15. {4, 2, 3}

    {1, 0, 0}

    Returns: 96

  16. {4, 2, 5}

    {0, 2, 3}

    Returns: 16

  17. {1, 1, 5}

    {0, 0, 0}

    Returns: 0

  18. {1, 2, 0}

    {0, 0, 1}

    Returns: 0

  19. {3, 4, 4}

    {1, 0, 1}

    Returns: 272

  20. {1, 5, 2}

    {0, 1, 0}

    Returns: 54

  21. {5, 0, 3}

    {1, 2, 1}

    Returns: 0

  22. {4, 2, 2}

    {1, 2, 1}

    Returns: 0

  23. {4, 3, 2}

    {2, 0, 2}

    Returns: 16

  24. {1, 3, 3}

    {0, 0, 2}

    Returns: 13

  25. {1, 3, 0}

    {0, 0, 1}

    Returns: 0

  26. {5, 0, 0}

    {0, 0, 2}

    Returns: 0

  27. {4, 3, 3}

    {1, 0, 1}

    Returns: 209

  28. {2, 5, 4}

    {0, 1, 3}

    Returns: 211

  29. {2, 0, 4}

    {1, 0, 0}

    Returns: 0

  30. {2, 3, 5}

    {1, 0, 0}

    Returns: 0

  31. {3, 1, 1}

    {0, 0, 0}

    Returns: 0

  32. {1, 5, 4}

    {0, 1, 1}

    Returns: 117

  33. {0, 2, 3}

    {0, 0, 0}

    Returns: 0

  34. {5, 0, 3}

    {0, 0, 0}

    Returns: 0

  35. {2, 0, 2}

    {0, 0, 0}

    Returns: 0

  36. {1, 1, 5}

    {1, 2, 1}

    Returns: 0

  37. {3, 4, 4}

    {0, 0, 0}

    Returns: 0

  38. {5, 0, 1}

    {0, 0, 1}

    Returns: 0

  39. {2, 5, 0}

    {2, 1, 1}

    Returns: 0

  40. {20, 24, 22}

    {1, 1, 5}

    Returns: 82080211

  41. {24, 24, 20}

    {5, 8, 5}

    Returns: 276636140

  42. {23, 20, 23}

    {6, 7, 5}

    Returns: 448084971

  43. {22, 24, 20}

    {4, 5, 8}

    Returns: 218440136

  44. {22, 24, 22}

    {4, 4, 5}

    Returns: 402354682

  45. {20, 24, 23}

    {4, 5, 2}

    Returns: 849882787

  46. {23, 22, 23}

    {4, 6, 4}

    Returns: 185831007

  47. {22, 20, 22}

    {1, 2, 0}

    Returns: 920808888

  48. {23, 23, 21}

    {1, 4, 11}

    Returns: 544109482

  49. {24, 24, 21}

    {10, 5, 6}

    Returns: 179536060

  50. {24, 23, 20}

    {3, 5, 4}

    Returns: 601076509

  51. {23, 24, 20}

    {5, 8, 6}

    Returns: 517193421

  52. {23, 22, 20}

    {3, 3, 2}

    Returns: 17338591

  53. {21, 24, 21}

    {4, 5, 7}

    Returns: 6962072

  54. {23, 20, 24}

    {6, 2, 4}

    Returns: 659143061

  55. {21, 20, 21}

    {7, 4, 5}

    Returns: 614516615

  56. {22, 20, 22}

    {2, 0, 1}

    Returns: 498169145

  57. {21, 22, 20}

    {0, 2, 8}

    Returns: 646885322

  58. {23, 23, 23}

    {8, 8, 5}

    Returns: 173523296

  59. {23, 23, 24}

    {7, 3, 5}

    Returns: 413588647

  60. {20, 24, 22}

    {0, 0, 1}

    Returns: 0

  61. {24, 20, 22}

    {5, 3, 3}

    Returns: 324484220

  62. {22, 24, 22}

    {3, 6, 4}

    Returns: 542829531

  63. {22, 23, 20}

    {0, 0, 0}

    Returns: 0

  64. {23, 21, 23}

    {3, 4, 4}

    Returns: 258076867

  65. {22, 20, 21}

    {3, 3, 0}

    Returns: 710720915

  66. {20, 24, 24}

    {0, 0, 0}

    Returns: 0

  67. {22, 24, 21}

    {5, 8, 4}

    Returns: 752889771

  68. {20, 24, 21}

    {5, 5, 6}

    Returns: 352725279

  69. {20, 20, 22}

    {3, 10, 6}

    Returns: 58073065

  70. {21, 22, 20}

    {0, 0, 0}

    Returns: 0

  71. {24, 24, 21}

    {3, 0, 1}

    Returns: 465285730

  72. {23, 23, 23}

    {6, 4, 12}

    Returns: 905441486

  73. {21, 20, 20}

    {2, 0, 2}

    Returns: 494746209

  74. {22, 24, 24}

    {3, 1, 9}

    Returns: 350352236

  75. {21, 20, 21}

    {0, 6, 3}

    Returns: 569852968

  76. {24, 21, 20}

    {1, 9, 3}

    Returns: 143687078

  77. {24, 22, 21}

    {5, 3, 6}

    Returns: 397743230

  78. {22, 22, 21}

    {6, 8, 5}

    Returns: 488762931

  79. {21, 23, 24}

    {5, 1, 4}

    Returns: 77459049

  80. {16, 24, 10}

    {20, 20, 17}

    Returns: 0

  81. {6, 20, 7}

    {1, 11, 12}

    Returns: 0

  82. {24, 5, 15}

    {19, 23, 23}

    Returns: 0

  83. {5, 6, 12}

    {23, 21, 1}

    Returns: 0

  84. {15, 10, 17}

    {17, 2, 8}

    Returns: 0

  85. {3, 4, 21}

    {16, 23, 18}

    Returns: 0

  86. {21, 6, 8}

    {19, 12, 3}

    Returns: 0

  87. {8, 17, 11}

    {3, 12, 11}

    Returns: 0

  88. {20, 17, 7}

    {9, 8, 19}

    Returns: 0

  89. {21, 22, 20}

    {10, 18, 1}

    Returns: 0

  90. {24, 19, 6}

    {9, 14, 24}

    Returns: 0

  91. {10, 24, 3}

    {4, 18, 5}

    Returns: 0

  92. {8, 10, 8}

    {3, 9, 6}

    Returns: 0

  93. {1, 24, 8}

    {19, 20, 6}

    Returns: 0

  94. {6, 21, 15}

    {15, 2, 12}

    Returns: 0

  95. {20, 0, 20}

    {24, 18, 4}

    Returns: 0

  96. {3, 13, 9}

    {7, 13, 24}

    Returns: 0

  97. {6, 2, 6}

    {20, 20, 21}

    Returns: 0

  98. {7, 17, 2}

    {17, 13, 9}

    Returns: 0

  99. {10, 11, 3}

    {2, 22, 10}

    Returns: 0

  100. {24, 24, 24 }

    {24, 24, 24 }

    Returns: 0

  101. {24, 24, 24 }

    {20, 20, 20 }

    Returns: 0

  102. {24, 24, 0 }

    {24, 0, 0 }

    Returns: 1

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: