Contest Duration: - (local time) (120 minutes) Back to Home
Official

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