## Editorial for CCO '23 P4 - Flip it and Stick it

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

The overall approach is to do casework on all possible . In each case, we first characterize all the strings that do not contain (call these good states). Based on this characterization, we then look for a measure of how far is from a good state and a greedy algorithm that repeatedly brings closer to a good state.

Formally, in each of the cases, we will find a function such that at all good states, for all where is obtained from by one reversal, and a greedy algorithm that finds an from any non-good state such that . It will then follow that is the answer for any string .

We can reduce the number of cases by half by noting that the answer remains the same if all the bits in and are flipped, so we may WLOG let .

We need to consider the case .

A good state is when the string is composed of only s. Therefore the answer is if contains only s, and otherwise, the answer is .

We need to consider the case .

A good state is when the string is a block of consecutive s followed by a block of consecutive s. This encourages us to look at blocks of consecutive s, and we might conjecture that the answer is the number of blocks of consecutive s that are not at the beginning of . Indeed, this number can decrease by at most per reversal, and a greedy algorithm that looks for the first block of s that is not at the beginning and performs a reversal to combine it with the beginning (e.g. or ) works.

Alternatively, the answer is just the number of times appears in as a substring, which can be proven similarly.

We need to consider the case .

A good state is when the string does not contain any blocks of two or more consecutive s. If has more s than the number of s plus , then the answer is since no rearrangement of the characters of is a good state.

Otherwise, the answer is the sum of over all blocks of consecutive s. Whenever is not a good state, there exists a substring in , and we can greedily perform a reversal to "cut off" a from a block and "insert" it into this (e.g. ).

Alternatively, the answer is just the number of times appears in as a substring if , otherwise .

We need to consider the cases and . By reversing and flipping the bits of and , these cases are equivalent, so we will only describe .

A good state is when the string has a prefix of consecutive s and no blocks of two or more consecutive s after that. The answer is the number of blocks of two or more consecutive s that are not in the prefix of s, and a greedy algorithm similar to can prove this.

Alternatively, the answer is just the number of times appears in as a substring.

We need to consider the cases and . The case was solved in subtask 4, so we need to solve .

A good state is when the string does not contain any blocks of exactly one consecutive . In one reversal, it is possible to "merge" up to blocks of exactly one (e.g. ). Therefore, if contains blocks of exactly one consecutive , the answer is .

Alternatively, the answer is just the number of times appears in as a substring divided by , rounded up.

The remaining case is when .

Similar to when , a good state is when the string does not contain any blocks of three or more consecutive s. If has more s than twice the number of s plus , then the answer is since no rearrangement of the characters of is a good state.

In this case, it might help to analyze how reversals behave on the blocks of s in more closely. Suppose the s in separate into blocks of consecutive s, where some may be zero. Then a reversal takes any two (where ), changes them to two new block sizes (where any is possible), and reverses the order of the blocks in between and . We can view as a multiset since the order is not important.

We can use blocks of size to cut off pieces of size from larger blocks, and we can also use blocks of size to cut off pieces of size from larger blocks. Intuitively, we should use the size blocks to cut off pieces of size from the largest blocks, since this is the most efficient, and only use size blocks if necessary. This leads to the following greedy algorithm: while the largest block has size , use a size block if there is one (replace with ), otherwise use a size block (replace with ).

The correctness of this greedy algorithm can be proven by finding an explicit function describing the answer. Without size blocks, the answer would be . With arbitrarily many size blocks, we can save up to reversals by cutting off at a time instead of . Thus, we conjecture that the answer is . It is straightforward to check that can decrease by at most per reversal, and the greedy algorithm above gives a way to always decrease by until a good state is reached, so this is indeed the answer.