LetterS
TCO20 South America · 2020-07-18 · by misof
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.
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.
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.
1
1
{}
{}
Returns: 0
Submissions are judged against all 83 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LetterS with a public method int count(int R, int C, vector<int> obr, vector<int> obc) · 83 test cases · 2 s / 256 MB per case