LetterS | Topcoder Archive

Problem Statement

A letter S shape is a set of cells in a square grid that can be painted as follows.

Paint a horizontal contiguous segment that consists of at least two cells. Let L and R be the leftmost and the rightmost of these cells.
Starting at L, paint a vertical contiguous segment going upwards. In addition to L this segment must contain at least two more cells. Let the topmost of those cells be T.
Starting at T, paint a horizontal contiguous segment going to the right. In addition to T this segment must contain at least one more cell.
Similarly to the previous two steps, paint a vertical segment going down from R to B (at least two new cells) and then from B going left (at least one new cell).

Below are several valid letter S shapes. The leftmost one is the smallest valid letter S shape.


   **      *****     **
   *       *         *
   **      ***       *
    *        *       *******
   **        *             *
            **       *******

You are given a grid with R rows and C columns. Both rows and columns are numbered starting from zero. This grid contains some obstacles: for each valid i, there is an obstacle blocking the cell in row obr[i], column obc[i]. Cells with obstacles cannot be painted.

Count all ways in which a letter S shape can be painted into the given grid. Return that count modulo 10^9 + 7.

Definition

Class:: LetterS
Method:: count
Parameters:: int, int, int[], int[]
Returns:: int
Method signature:: int count(int R, int C, int[] obr, int[] obc)
(be sure your method is public)

Constraints

R will be between 1 and 1000, inclusive.
C will be between 1 and 1000, inclusive.
obr will contain between 0 and min(500, R*C) elements, inclusive.
obc will contain the same number of elements as obr.
Each element of obr will be between 0 and R-1, inclusive.
Each element of obc will be between 0 and C-1, inclusive.
The cells described by obr and obc will be distinct.

Examples

```
5
```
```
2
```
```
{}
```
```
{}
```
```
Returns: 1
```
The only valid solution is the smallest possible letter S shape.
```
4
```
```
4
```
```
{2}
```
```
{3}
```
```
Returns: 0
```
No valid solutions, the grid is not tall enough to contain a letter S shape.
```
6
```
```
3
```
```
{1, 3}
```
```
{1, 0}
```
```
Returns: 12
```
The grid looks as follows, with X denoting blocked cells: ... .X. ... X.. ... ... There are 12 possible letter S shapes, one of them is shown below: *** *X. *** X.* ..* .**
```
30
```
```
47
```
```
{}
```
```
{}
```
```
Returns: 190761735
```
Don't forget about the modulo.

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.