AlmostCheckerboards
SRM 845 · 2023-03-02 · by misof
Problem Statement
This problem is about bitmaps. All bitmaps in this problem are black-and-white bitmaps with R rows and C columns.
A bitmap is called a checkerboard if it has the property that no two pixels that share a side share the same color: each black pixel must be horizontally and vertically adjacent to only white pixels and vice versa. Clearly, for any dimensions R and C there are exactly two distinct checkerboards.
The checkerboard distance of a bitmap is the minimum number of pixels that have to be edited (i.e., turned from black to white or vice versa) in order to change that bitmap into a checkerboard.
For example, the bitmap shown below (using 'W' and 'B' for white and black pixels) has checkerboard distance 2.
WBWBW BWBWB BBWWW BWBWB
You are given the dimensions R and C and the checkerboard distance D. Count all bitmaps with these parameters, and return that count modulo 10^9 + 7.
Constraints
- R will be between 1 and 100, inclusive.
- C will be between 1 and 100, inclusive.
- D will be between 0 and 100, inclusive.
3 4 0 Returns: 2
The two perfect checkerboards are shown below: BWBW WBWB WBWB BWBW BWBW WBWB
3 4 47 Returns: 0
You can transform any 3x4 bitmap into any other 3x4 bitmap in at most 3x4 = 12 changes, so there clearly won't be any bitmaps with checkerboard distance exactly equal to 47.
2 2 1 Returns: 8
The eight bitmaps that match these parameters are precisely all the bitmaps that contains three pixels of one color and one pixel of the opposite color. The edit that turns it into a valid checkerboard is always to find the pixel that has the unique color and to toggle the pixel that is diagonally opposite it to make it match.
9 4 15 Returns: 135805043
Remember that the answer should be computed modulo 10^9 + 7. (The exact answer for this test case is 11,135,805,120, and that modulo 1,000,000,007 is 135,805,043.)
2 2 2 Returns: 6
Submissions are judged against all 164 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AlmostCheckerboards with a public method int count(int R, int C, int D) · 164 test cases · 2 s / 256 MB per case