TopCoder Statistics - Problem Statement

Problem Statement

There are three schools, numbered 0, 1, and 2.

You are given three int[]s amt, lo, hi. Each of these int[]s contain exactly three elements.

The number of students in school i is equal to amt[i]. Students from the same school are indistiguishable.

All these students took part in a national exam. Each student earned a distinct integer number of points on the exam. In addition, you know that each student from school i earned between lo[i] and hi[i] points, inclusive.

After the exam, we will order the students by increasing number of points, and write down which school each student came from. This will give us a string of length sum(amt) consisting of '0's, '1's, and '2's.

Count the number of distinct strings that can result from a valid scenario, modulo 10^9+7. Note that in some test cases (such as the one shown in Example 1) there can be no valid scenarios at all.

Definition

Class:: ClassRankings
Method:: countWays
Parameters:: int[], int[], int[]
Returns:: int
Method signature:: int countWays(int[] amt, int[] lo, int[] hi)
(be sure your method is public)

Constraints

amt, lo, hi will contain exactly 3 elements.
Each element of amt will be between 1 and 50, inclusive.
Each element of lo, hi will be between 1 and 1,000, inclusive.
For each valid i, lo[i] will be less than or equal to hi[i].

Examples

{1,1,1}

{1,1,1}

{100,100,100}

Returns: 6

We can get the strings 012, 021, 102, 120, 201, 210.
{1,1,1}

{1,1,1}

{1,1,1}

Returns: 0

There is no way for the students to finish with distinct scores.
{2,1,3}

{5,1,2}

{6,1,4}

Returns: 1
{2,4,3}

{1,4,8}

{6,10,12}

Returns: 15
{50,50,50}

{1,1,1}

{150,150,150}

Returns: 824706821
{24,39,8}

{135,386,57}

{652,667,911}

Returns: 550794614
{32,3,2}

{69,45,702}

{823,508,990}

Returns: 435897
{4,17,6}

{259,171,531}

{947,666,622}

Returns: 771619843
{41,27,3}

{103,6,30}

{185,143,683}

Returns: 624133691
{25,2,9}

{784,353,489}

{814,857,774}

Returns: 630
{10,30,29}

{356,246,275}

{539,642,586}

Returns: 170912572
{16,23,5}

{4,410,126}

{272,947,580}

Returns: 1086008
{18,50,32}

{738,406,394}

{804,440,983}

Returns: 0
{3,35,44}

{172,467,6}

{877,842,759}

Returns: 298272272
{37,22,18}

{387,32,98}

{489,561,610}

Returns: 15581453
{4,7,31}

{357,308,590}

{862,686,790}

Returns: 585244196
{43,21,7}

{152,521,671}

{672,884,833}

Returns: 193587842
{49,34,3}

{784,509,672}

{850,836,978}

Returns: 17015089
{39,20,14}

{435,748,316}

{781,837,903}

Returns: 478249277
{37,36,6}

{67,392,329}

{703,649,523}

Returns: 401248250
{44,37,47}

{318,173,468}

{427,760,628}

Returns: 954697316
{19,26,28}

{1,225,319}

{232,256,824}

Returns: 127
{20,7,8}

{529,347,67}

{988,625,498}

Returns: 6724520
{14,42,35}

{96,638,882}

{626,790,889}

Returns: 0
{36,43,11}

{128,378,414}

{257,429,709}

Returns: 27824
{49,1,29}

{138,146,272}

{414,792,730}

Returns: 615384205
{15,8,1}

{39,184,17}

{104,230,817}

Returns: 24
{1,9,3}

{280,423,270}

{955,943,480}

Returns: 2860
{27,12,45}

{90,231,102}

{710,994,173}

Returns: 556581707
{36,13,39}

{482,191,485}

{487,201,545}

Returns: 0
{4,5,49}

{71,107,4}

{819,122,809}

Returns: 491773271
{1,13,10}

{2,191,293}

{167,438,359}

Returns: 1144066
{28,36,13}

{402,542,261}

{483,928,522}

Returns: 620076241
{19,22,35}

{413,249,157}

{960,804,718}

Returns: 687460357
{15,41,1}

{2,339,1}

{596,661,182}

Returns: 981308041
{6,46,31}

{26,18,33}

{952,82,123}

Returns: 651240179
{47,41,2}

{147,347,833}

{989,806,947}

Returns: 606750642
{18,21,33}

{437,335,397}

{998,920,475}

Returns: 878510098
{41,42,35}

{884,113,324}

{972,487,535}

Returns: 308505150
{20,48,43}

{23,18,2}

{430,834,24}

Returns: 0
{25,4,11}

{427,437,429}

{914,988,781}

Returns: 595617091
{37,41,5}

{2,20,12}

{492,622,715}

Returns: 901889476
{47,25,27}

{769,162,554}

{841,646,629}

Returns: 176533095
{43,9,49}

{220,508,293}

{810,596,849}

Returns: 332291605
{2,1,15}

{30,247,401}

{147,932,864}

Returns: 16
{14,45,22}

{197,229,35}

{674,808,395}

Returns: 993816851
{37,24,15}

{848,117,71}

{878,155,649}

Returns: 0
{25,6,41}

{871,172,413}

{993,511,891}

Returns: 885305113
{12,1,1}

{70,381,637}

{651,833,727}

Returns: 182
{38,8,14}

{128,828,249}

{797,946,973}

Returns: 898528385
{12,4,10}

{783,61,299}

{837,964,717}

Returns: 14950
{44,11,27}

{1,67,262}

{786,458,702}

Returns: 620943292
{29,3,33}

{231,15,317}

{647,367,362}

Returns: 733594374
{18,17,14}

{20,264,98}

{309,846,743}

Returns: 601538962
{39,41,39}

{583,284,241}

{829,750,778}

Returns: 257026503
{4,41,8}

{50,5,55}

{95,49,80}

Returns: 495
{2,10,13}

{53,4,21}

{59,97,85}

Returns: 147584514
{1,3,2}

{8,22,48}

{93,69,71}

Returns: 60
{6,4,1}

{56,52,63}

{64,85,78}

Returns: 330
{49,18,1}

{1,32,1}

{71,80,47}

Returns: 83730929
{2,13,2}

{11,9,7}

{13,66,35}

Returns: 765
{8,21,25}

{37,54,14}

{84,83,68}

Returns: 308630451
{1,41,31}

{9,11,19}

{41,77,88}

Returns: 696197061
{25,39,3}

{11,9,31}

{35,82,55}

Returns: 3420
{2,22,24}

{1,35,1}

{18,70,82}

Returns: 890592402
{39,14,4}

{36,23,66}

{95,39,94}

Returns: 216216
{25,14,10}

{12,21,74}

{69,99,85}

Returns: 145138970
{38,42,15}

{35,2,53}

{93,54,100}

Returns: 212147470
{12,1,4}

{76,46,10}

{92,96,56}

Returns: 17
{24,18,23}

{19,28,16}

{46,97,97}

Returns: 107734336
{1,8,5}

{54,27,15}

{60,53,93}

Returns: 2002
{18,30,22}

{58,7,26}

{94,61,49}

Returns: 5244
{15,7,17}

{17,7,19}

{67,36,69}

Returns: 5758127
{16,9,4}

{24,33,8}

{77,49,48}

Returns: 130210080
{21,28,24}

{2,3,1}

{81,83,25}

Returns: 803523467
{2, 4, 3 }

{1, 4, 8 }

{6, 10, 12 }

Returns: 15
{50, 50, 50 }

{1, 100, 200 }

{1000, 1000, 1000 }

Returns: 824706821
{50, 50, 50 }

{1, 1, 1 }

{1000, 1000, 1000 }

Returns: 824706821
{50, 50, 50 }

{1, 1, 1 }

{1000, 800, 600 }

Returns: 824706821
{50, 50, 50 }

{1, 201, 401 }

{1000, 800, 600 }

Returns: 824706821
{50, 50, 50 }

{100, 300, 500 }

{1000, 1000, 1000 }

Returns: 824706821

Statistics

Problem Statement for "ClassRankings"

Problem Statement

Definition

Constraints

Examples