Editorial for Canada Day Contest 2021 - Bob and Canada - Olympiads Online Judge

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

Hint

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.

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

Time complexity: $\mathcal O(n)$ $O (n)$

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

Comments

There are no comments at the moment.