Editorial for Canada Day Contest 2021 - Bob and Canada

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Aaeria


In order to make a string Canadian, you need to change all the Ws in the red sections and the Rs in the white section.


Try to come up with a formula for the number of edits based on the starting point of the second and third section.


Let's say the first section (red) goes from index 1 to a, the second (white) goes from a+1 to b, and the third (red) from b+1 to n. You can first try every combination of a and b. In order to count the number of Rs and Ws in a range quickly you can use a prefix sum array r[] and w[]. The answer for a and b will be (w[n]-w[b])+(r[b]-r[a])+(w[a]). Looking at this formula you can notice that for any b you should always choose the a that minimizes w[a]-r[a]. So as you loop through b from 2 to n-1, instead of checking every a, you can just store the minimum value of w[a]-r[a] so far.

Time complexity: \mathcal O(n)

There are quite a few other accepted solutions so feel free to show your own in the comments.


There are no comments at the moment.