PROBLEM LINK:
Author: Alei Reyes
Primary Tester: Hussain Kara Fallah
Secondary Tester: Kacper Walentynowicz
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given a string consisting of characters U,D. In a move you can select a consecutive substring and flip all characters belonging to. (U changes to D and vice versa). What’s the minimum number of moves to make all characters equal?
EXPLANATION:
The first thing that will come up to our minds is that we should split the string from the beginning into a block of consecutive ‘U’ characters, followed immediately by a block of consecutive ‘D’ characters, then a block of ‘U’ characters, then a block of ‘D’ characters… etc. (Of course if our string starts with D then the letters are the opposite). And flip the D blocks.
The number of D blocks = (The number of U blocks) or (the number of U blocks + 1)
If our string starts with D then
The number of U blocks = (The number of D blocks) or (the number of D blocks + 1)
so our answer would be [number of blocks / 2] (of course rounded down).
Example:
Consider our string was “UUUDDUUUDDDUU”
We would split it into :
[UUU] , [DD] , [UUU] , [DDD] , [UU]
The best solution is to flip [DD] , [DDD]
Another Example :
Consider our string was “DDDUDDUU”
We would split it into :
[DDD] , [U] , [DD] , [UU]
Here because the number of U blocks is equal to number of D blocks then flipping the blocks of any letter would be optimal.
Why is this always correct?
If we are looking for a better solution than the mentioned above, then we should flip at least 2 of our targeted blocks at once. But that’s impossible because we would affect at least one proper block between them (consisting of characters equal to our final character) and we must return it to its original state again and that’s impossible without an additional move.
Consider we tried to obtain a better strategy in the first example:
That means that we would change all D letters to U in one move. It’s only possible by flipping the substring [DDUUUDDD] (or any substring formed by extending this one from left or right), but doing this would change U letters to D and we need to return them back to U, and this will cost us at least one operation.