UVa problem 11231: sample algorithm

To solve UVa problem 11231 (Black and white painting), one has to distinguish between two cases: when the top left corner (first_box) is white, or black. After some analyses, one is able to find a way to determine if the first_box is white or black based on the given n, m and c. Figure 1 summarizes this.

Figure 1. Summary for determining if the top left corner is white or black given n, m and c.

In Figure 1, if n and m are of the same type, for example, both even or both odd, then the color of the bottom right corner (last_box) will be the same as the first_box. Otherwise, they will have opposite colors.

First, we tackle the case when the first_box is white (case_white). For case_white, there are two cases. Let us name them case_white1 and case_white2.

For case_white1, we take a look at the chess boards embedded within the painting. This is shown in Figure 2.

Figure 2. Chess boards embedded in the painting for case_white_1.

In Figure 2, passing lanes, both horizontal and vertical are shown. Only 4 passing lanes are shown to avoid clutter. A chess board is defined for each intersection between a horizontal passing lane and a vertical passing lane.

We define a chess board as having four coordinates: h1, h2, v1, v2. h1 stands for the lower-numbered row of the board, h2 stands for the higher-numbered row, v1 stands for the lower-numbered column and v2 stands for the higher-numbered column. A chess board will be designated (h1, h2, v1, v2) for brevity.

In Figure 2, then, there are 4 embedded chess boards as identified when a horizontal lane intersects a vertical lane:

(1, 8, 1, 8)

(1, 8, 3, 10)

(3, 10, 1, 8)

(3, 10, 3, 10)

To compute the number of embedded chess boards in case_white1, we need to obtain the total number of boards in each vertical passing lane. Let us call this number x. We also need to obtain the total number of boards in each horizontal passing lane, calling this number y. The product of x and y will give us the total number of boards for case_white1. Let us call this product, z.

By observing the patterns in case_white1, we arrive at a formula given by Equation 1.

[Equation 1]

x = (n - 6) / 2

y = (m - 6) / 2

z = x * y

Next, we tackle case_white2. Figure 3 shows the embedded boards for case_white2.

Figure 3. Chess boards embedded in the painting for case_white_2.

In Figure 3, the embedded boards have the following coordinates:

(2, 9, 2, 9)

(2, 9, 4, 11)

(4, 11, 2, 9)

(4, 11, 4, 11)

Taking the numbers of boards in the vertical lanes to be q, and the number of boards in the horizontal lanes to be r, we arrive at Equation 2, where s is the total number of boards for case_white2

[Equation 2]

q = (n - 7) / 2

r = (m - 7) / 2

s = q * r

Next, we take on case_black. case_black like case_white offers two cases: case_black1 and case_black2. Figure 4 shows some of the boards in case_black1.

Figure 4. Chess boards embedded in case_black_1.

In Figure 4, the boards have the following coordinates:

(2, 9, 1, 8)

(2, 9, 3, 10)

(4, 11, 1, 8)

(4, 11, 3, 10)

We also arrive at Equation 3, using the same analogy for the variable names as in Equation 1.

[Equation 3]

x = (n - 7) / 2

y = (m - 6) / 2

z = x * y

Figure 5 shows case_black_2.

Figure 5, chess boards embedded in case_black2.

In Figure 5, the following boards are defined:

(1, 8, 2, 9)

(1, 8, 4, 11)

(3, 10, 2, 9)

(3, 10, 4, 11)

Equation 4 is also derived using the same terminologies as used in Equation 2.

[Equation 4]

q = (n - 6) / 2

r = (m - 7) / 2

s = q * r

The total number of embedded chess boards for either case, case_white or case_black, is the sum of z and s.