## B - Electric Board Editorial by evima

The operation does not change the number of `0`

s, so if \(S\) and \(T\) have different number of `0`

s, the objective is unachievable.

Otherwise, assume that the `0`

s in \(S\) are its \(a_1\)-th, \(a_2\)-th, \(\cdots\), \(a_K\)-th characters, and the `0`

s in \(T\) are its \(b_1\)-th, \(b_2\)-th, \(\cdots\), \(b_K\)-th characters. We will show that the answer is equal to the number of indices \(i\) \((1 \leq i \leq K)\) such that \(a_i \neq b_i\).

First, we need at least this number of operations because one operation changes only one of \(a_1, a_2, \cdots, a_K\).

(Illustration of the operation)

Additionally, we can achieve the objective in this number of operations with, for example, the following strategy:

If there exists \(i\) such that \(a_i > b_i\): Let \(p\) be the minimum \(i\) such that \(a_i > b_i\). Use the operation to change \(a_p\) to \(b_p\).

Otherwise: Let \(q\) be the maximum \(i\) such that \(a_i < b_i\). Use the operation to change \(a_q\) to \(b_q\).

(Illustration of the strategy)

(The sentences to the left says “The minimum \(i\) such that \(a_i > b_i\) is \(4\)”, “The maximum \(i\) such that \(a_i < b_i\) is \(3\)”, and the one to the right says “We have one less \(i\) such that \(a_i \neq b_i\)!”)

(Sample Implementations)

posted:

last update: