UVa 11231

From Algorithmist
Jump to navigation Jump to search

11231 - Black and white painting[edit]

Summary[edit]

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.

Explanation[edit]

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.

Gotchas[edit]

  • m, n <= 8?
  • OBOB

Input[edit]

8 8 0
8 8 1
9 9 1
40000 39999 0
0 0 0

Output[edit]

0
1
2
799700028