ClassRankings | Topcoder Archive

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

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.