B - Electric Board Editorial by evima
The operation does not change the number of 0s, so if \(S\) and \(T\) have different number of 0s, the objective is unachievable.
Otherwise, assume that the 0s in \(S\) are its \(a_1\)-th, \(a_2\)-th, \(\cdots\), \(a_K\)-th characters, and the 0s 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: