Subtask 1

For the first subtask, we can brute-force all ~2^{NM}~ possible colourings, choosing the one with the fewest ugly sub-rectangles.

Subtask 2

For the second subtask, we can use the following pattern:

BBBBBBBBBBBBB...
YYYYYYYYYYYYY...
BYBYBYBYBYBYB...
YBYBYBYBYBYBY...

Observe that in this pattern, any sub-rectangle of width ~2~ or more always has differing first and last rows. So if we choose the first ~N~ rows and ~M~ columns of the pattern, the resulting rectangle will have no ugly sub-rectangles.

Subtask 3

At this point, we may begin to suspect that a colouring with no ugly sub-rectangles is always possible. This is in fact true.

Using a backtracking solution, we can find a ~30 \times 30~ colouring with no ugly sub-rectangles. If our solution isn't efficient enough, we can run it offline and hard-code the result. Then any ~N \times M~ sub-grid of the ~30 \times 30~ colouring will suffice.

Subtask 4

For this subtask, what if we fill the screen with shifted copies of the same string, where row ~i~ is shifted ~i-1~ places from the first row? We claim that if this colouring has an ugly rectangle, the string must have two identical substrings that overlap each other (for example, BYYBYYBY consists of two identical strings, BYYBY, overlapping in the middle at BY).

We prove this assertion. Let's fill the entire screen with shifted copies of the same string:

Suppose this colouring contains a ~K \times K~ ugly square. By our construction, the first column and the first row of the square are identical. The last column and the ~K~ letters of the first row starting at the upper-right corner of the square are also identical. Hence, as the first and last columns of the square are identical, our string contains an overlap. For example, here we have ~abcd = defg~ with an overlap of ~d~:

A similar result holds for ugly rectangles that are not square.

Hence, if we fill the screen with shifted copies of an overlap-free string, there will be no ugly rectangles. All we need to do now is find such a string. We can do this using another backtracking program (either online or offline); we need a string of length ~N + M~.

Subtask 5

To solve the final subtask, we could use the same program as in Subtask 4, but in order to generate a string of the required length, our program would need to be quite efficient. Alternatively, we might already know of an overlap-free string called the Thue-Morse sequence. We can compute the first ~N+M~ terms of this sequence in linear time.