## Editorial for Canada Day Contest 2021 - Bob and Canada

**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:

**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