TaroCheckers | Topcoder Archive

Problem Statement

Cat Taro has a board with N rows and M columns divided into unit cells. He wants to place some checkers on the board. Each cell can contain at most one checker. The following conditions must be fulfilled:

For each row i, there is exactly one cell with a checker among the first left[i] cells of the i-th row.
For each row i, there is exactly one cell with a checker among the last right[i] cells of the i-th row.
For each column, there is at most one cell with a checker in that column.

You are given the int M and the two int[]s left and right (each with N elements). Let X be the total number of valid ways to place checkers. Return the value (X modulo 1,000,000,007).

Definition

Class:: TaroCheckers
Method:: getNumber
Parameters:: int[], int[], int
Returns:: int
Method signature:: int getNumber(int[] left, int[] right, int M)
(be sure your method is public)

Constraints

left will contain between 1 and 50 elements, inclusive.
right and left will contain the same number of elements.
M will be between 2 and 200, inclusive.
Each element of left and right will be between 1 and M, inclusive.
For each valid i, the value left[i]+right[i] will be less than or equal to M.

Examples

```
{1, 2}
```
```
{2, 1}
```
```
4
```
```
Returns: 1
```
Only one way to place checkers is possible in this case: (In each row, the first left[i] and the last right[i] cells have a darker background.)
```
{1, 4, 2}
```
```
{2, 3, 1}
```
```
7
```
```
Returns: 6
```
```
{4, 7, 4}
```
```
{7, 4, 7}
```
```
11
```
```
Returns: 5760
```

{10, 25, 100, 74}

{100, 47, 27, 100}

Returns: 796178974

{21, 99, 87, 12, 138, 16, 78, 36, 98, 40, 57, 10, 61, 100, 8, 110, 96, 9, 69, 110, 14, 71}

{83, 8, 25, 169, 1, 89, 109, 89, 19, 112, 39, 112, 87, 66, 116, 16, 41, 97, 52, 70, 111, 23}

Returns: 235017573

{3, 37, 26, 50, 8, 3, 38, 15, 58, 47, 35, 8, 27, 22, 5}

{19, 26, 62, 15, 84, 13, 6, 46, 22, 53, 23, 8, 29, 55, 6}

Returns: 528024858

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.