11231 - Black and white painting
Given the dimensions of a m x n chessboard with a specified colour of the tile in the lower right corner, count the number of 8 x 8 standard chessboards embedded within.
Any embedded chessboard can be identified uniquely with its lower right corner. If we count the number of valid lower-right-hand-corners, we thus have our solution.
For convenience we identify the lower right corner of the large board with coordinate (1, 1). We can write any lr-corner of a standard chessboard as (r, c) with the following restrictions:
- (r, c) must be a white tile
- the board starting at (r, c) must fit within the board, ie
- r + 8 <= #rows of the large board = m
- c + 8 <= #cols = n
For any row of width n starting with a white tile, we get the number of candidates by
candidates( n ) = (( n - 8 ) / 2 ) + 1, if n >= 8 else 0
That is, if we have at least some candidates, remove columns where the "embedded" board would stretch outside the larger board (n - 8). Get the number of white tiles in the range - half of them - ((n - 8) / 2) and compensate as we are off by one.
For any row starting with a black tile we can simply remove one column, thus getting candidates( n - 1 ) by the above formula.
We now simply calculate the number of ok starting rows (ie such that r+8 <= m) starting with a black and white tile respectively, and multiply the results together. This can be done in O(1) with explicit formula, or O(m) if one lazily loops over the rows.
- m, n <= 8?
8 8 0 8 8 1 9 9 1 40000 39999 0 0 0 0
0 1 2 799700028