Editorial for DMOPC '20 Contest 5 P5 - Slacking Off Again
Submitting an official solution before solving the problem yourself is a bannable offence.
Authors:
,Subtask 1
For the first subtask, we can brute-force all
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
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
Subtask 4
For this subtask, what if we fill the screen with shifted copies of the same string, where row 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
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
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
Comments