Editorial for Canada Day Contest 2021 - Bob and Canada
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Hint
In order to make a string Canadian, you need to change all the W
s in the red sections and the R
s in the white section.
Hint
Try to come up with a formula for the number of edits based on the starting point of the second and third section.
Solution
Let's say the first section (red) goes from index to
, the second (white) goes from
to
, and the third (red) from
to
. You can first try every combination of
and
. In order to count the number of Rs and Ws in a range quickly you can use a prefix sum array
and
. The answer for
and
will be
. Looking at this formula you can notice that for any
you should always choose the
that minimizes
. So as you loop through
from
to
, instead of checking every
, you can just store the minimum value of
so far.
Time complexity:
There are quite a few other accepted solutions so feel free to show your own in the comments.
Comments