Editorial for CCO '23 P4 - Flip it and Stick it - Olympiads Online Judge

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 $T$ $T$ . In each case, we first characterize all the strings that do not contain $T$ $T$ (call these good states). Based on this characterization, we then look for a measure of how far $S$ $S$ is from a good state and a greedy algorithm that repeatedly brings $S$ $S$ closer to a good state.

Formally, in each of the cases, we will find a function $f(S)$ $f (S)$ such that $f(S) = 0$ $f (S) = 0$ at all good states, $f(S') \ge f(S)-1$ $f (S^{'}) \geq f (S) - 1$ for all $S,S'$ $S, S^{'}$ where $S'$ $S^{'}$ is obtained from $S$ $S$ by one reversal, and a greedy algorithm that finds an $S'$ $S^{'}$ from any non-good state $S$ $S$ such that $f(S') = f(S)-1$ $f (S^{'}) = f (S) - 1$ . It will then follow that $f(S)$ $f (S)$ is the answer for any string $S$ $S$ .

We can reduce the number of cases by half by noting that the answer remains the same if all the bits in $S$ $S$ and $T$ $T$ are flipped, so we may WLOG let $T_1 = \tt 0$ $T_{1} = 0$ .

Subtask 1

We need to consider the case $T = \tt 0$ $T = 0$ .

A good state is when the string is composed of only $\tt 1$ $1$ s. Therefore the answer is $0$ $0$ if $S$ $S$ contains only $\tt 1$ $1$ s, and otherwise, the answer is $-1$ $- 1$ .

Subtask 2

We need to consider the case $T = \tt 01$ $T = 01$ .

A good state is when the string is a block of consecutive $\tt 1$ $1$ s followed by a block of consecutive $\tt 0$ $0$ s. This encourages us to look at blocks of consecutive $\tt 1$ $1$ s, and we might conjecture that the answer is the number of blocks of consecutive $\tt 1$ $1$ s that are not at the beginning of $S$ $S$ . Indeed, this number can decrease by at most $1$ $1$ per reversal, and a greedy algorithm that looks for the first block of $\tt 1$ $1$ s that is not at the beginning and performs a reversal to combine it with the beginning (e.g. $\tt 11[00111]01 \to \tt 11[11100]01$ $11 [00111] 01 \to 11 [11100] 01$ or $\tt [001]011 \to \tt [100]011$ $[001] 011 \to [100] 011$ ) works.

Alternatively, the answer is just the number of times $T = \tt 01$ $T = 01$ appears in $S$ $S$ as a substring, which can be proven similarly.

Subtask 3

We need to consider the case $T = \tt 00$ $T = 00$ .

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

Otherwise, the answer is the sum of $(\text{block size}-1)$ $(block size - 1)$ over all blocks of consecutive $\tt 0$ $0$ s. Whenever $S$ $S$ is not a good state, there exists a substring $\tt 11$ $11$ in $S$ $S$ , and we can greedily perform a reversal to "cut off" a $\tt 0$ $0$ from a block and "insert" it into this $\tt 11$ $11$ (e.g. $\tt 00[01010111101]1 \to \tt 00[10111101010]1$ $00 [01010111101] 1 \to 00 [10111101010] 1$ ).

Alternatively, the answer is just the number of times $T = \tt 00$ $T = 00$ appears in $S$ $S$ as a substring if $((\text{# 0s in }S) \le (\text{# 1s in }S)+1)$ $((# 0s in S) \leq (# 1s in S) + 1)$ , otherwise $-1$ $- 1$ .

Subtask 4

We need to consider the cases $T = \tt 001$ $T = 001$ and $T = \tt 011$ $T = 011$ . By reversing and flipping the bits of $S$ $S$ and $T$ $T$ , these cases are equivalent, so we will only describe $T = \tt 011$ $T = 011$ .

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

Alternatively, the answer is just the number of times $T = \tt 011$ $T = 011$ appears in $S$ $S$ as a substring.

Subtask 5

We need to consider the cases $T = \tt 010$ $T = 010$ and $T = \tt 011$ $T = 011$ . The case $T = \tt 011$ $T = 011$ was solved in subtask 4, so we need to solve $T = \tt 010$ $T = 010$ .

A good state is when the string does not contain any blocks of exactly one consecutive $\tt 1$ $1$ . In one reversal, it is possible to "merge" up to $2$ $2$ blocks of exactly one $\tt 1$ $1$ (e.g. $\tt 01[011001]0 \to \tt 01[100110]0$ $01 [011001] 0 \to 01 [100110] 0$ ). Therefore, if $S$ $S$ contains $x$ $x$ blocks of exactly one consecutive $\tt 1$ $1$ , the answer is $\lceil \frac{x}{2} \rceil$ $⌈ \frac{x}{2} ⌉$ .

Alternatively, the answer is just the number of times $T = \tt 010$ $T = 010$ appears in $S$ $S$ as a substring divided by $2$ $2$ , rounded up.

Subtask 6

The remaining case is when $T = \tt 000$ $T = 000$ .

Similar to when $T = \tt 00$ $T = 00$ , a good state is when the string does not contain any blocks of three or more consecutive $\tt 0$ $0$ s. If $S$ $S$ has more $\tt 0$ $0$ s than twice the number of $\tt 1$ $1$ s plus $2$ $2$ , then the answer is $-1$ $- 1$ since no rearrangement of the characters of $S$ $S$ is a good state.

In this case, it might help to analyze how reversals behave on the blocks of $\tt 0$ $0$ s in $S$ $S$ more closely. Suppose the $\tt 1$ $1$ s in $S$ $S$ separate $S$ $S$ into blocks of $x_1,\dots,x_k$ $x_{1}, \dots, x_{k}$ consecutive $\tt 0$ $0$ s, where some $x_i$ $x_{i}$ may be zero. Then a reversal takes any two $x_i,x_j$ $x_{i}, x_{j}$ (where $i < j$ $i < j$ ), changes them to two new block sizes $y,x_i+x_j-y$ $y, x_{i} + x_{j} - y$ (where any $0 \le y \le x_i+x_j$ $0 \leq y \leq x_{i} + x_{j}$ is possible), and reverses the order of the blocks in between $i$ $i$ and $j$ $j$ . We can view $x_1,\dots,x_k$ $x_{1}, \dots, x_{k}$ as a multiset since the order is not important.

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

The correctness of this greedy algorithm can be proven by finding an explicit function describing the answer. Without size $0$ $0$ blocks, the answer would be $\sum_{x_i > 2}(x_i-2)$ $\sum_{x_{i} > 2} (x_{i} - 2)$ . With arbitrarily many size $0$ $0$ blocks, we can save up to $\sum_{x_i > 2} \lfloor \frac{x-2}{2} \rfloor$ $\sum_{x_{i} > 2} ⌊ \frac{x - 2}{2} ⌋$ reversals by cutting off $2$ $2$ at a time instead of $1$ $1$ . Thus, we conjecture that the answer is $f(S) = \sum_{x_i > 2}(x_i-2) - \min\left(\sum_{x_i > 2} \lfloor \frac{x-2}{2} \rfloor,\text{# 0s among }x_i\right)$ $f (S) = \sum_{x_{i} > 2} (x_{i} - 2) - min (\sum_{x_{i} > 2} ⌊ \frac{x - 2}{2} ⌋, # 0s among x_{i})$ . It is straightforward to check that $f$ $f$ can decrease by at most $1$ $1$ per reversal, and the greedy algorithm above gives a way to always decrease $f$ $f$ by $1$ $1$ until a good state is reached, so this is indeed the answer.

Comments

There are no comments at the moment.