DiagonalColumn
TCO19 Round 3B · 2019-04-15 · by Errichto
Problem Statement
There is a grid with H rows and W columns. All cells in the grid are initially white.
You may perform zero or more painting steps. Each step looks as follows:
- You select either any one column of the grid, or any one diagonal that goes down and to the right.
- You paint all its cells black.
The same cell can be painted multiple times. Once it's black, it remains black when you paint it again.
Two grids are different if one of them has a white cell at some coordinates at which the other grid has a black cell. Compute and return the number of different grids you can obtain, modulo 1,000,000,007.
Constraints
- H and W will be between 1 and 38, inclusive.
2 2 Returns: 12
In the figure below, the columns and diagonals you are allowed to paint are shown using asterisks. columns: diagonals: *. .* .. *. .* *. .* *. .* .. The 12 different grids that can be produced are shown below, using '.' for white and '#' for black. .. .. .# #. .. #. .. #. #. .# .# ## .# .# #. #. ## .# #. ## .# ## ## ## And the four grids that cannot be produced look as follows: #. .. ## .. .. .# .. ##
2 3 Returns: 37
3 2 Returns: 28
1 5 Returns: 32
Each of the 2^5 black-and-white grids can be produced.
6 1 Returns: 64
Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DiagonalColumn with a public method int countGrids(int H, int W) · 76 test cases · 2 s / 256 MB per case