A quiz from Iroha-chan

Updated:

Problem

We call 「捨てる」 “burning” in English here.

Solution

Hereinafter, $A$ and $B$ are multi-sets. Let $f \colon A \to B$ a function so that

$f(a) = \mathop{\mathrm{argmin}} _ {b \in B} \lvert a - b \rvert$. If there are several $b \in B$ that attain the minimum, we can choose any of them.

Firstly, we consider the best strategy for A. It’s very simple. For each turn, A should burn $a’ = \mathop{\mathrm{argmin}} _ {a \in A} \lvert a - f(a) \rvert$; otherwise, if A still holds $a’$ at the final state, B can keep $b’ = f(a’)$ so that B can attain \[ \lvert a’ - b’ \rvert = \min _ {a \in A} \lvert a - f(a) \rvert = \min _ {a \in A} \min _ {b \in B} \lvert a - b \rvert \leq \lvert a - b \rvert \] for any $a \in A$ and $b \in B$ at the moment, which is not the best strategy for A.

Secondly, we consider the best strategy for B. It’s very simple, too. Just after the turn of A, it follows that $\sharp A < \sharp B$. Thus $f(A) \neq B$ but $f(A) \subset B$. Thus there exists an element $b’ \in B \setminus f(A)$. B should burn $b’$. Let’s see what happens when B burn something form $B$. For any $a \in A$, $\lvert a - f(a) \rvert$ is no less than before since $B$ becomes smaller. If B burns $b’$, B does not change $f(a)$ at all, which is the best strategy for B.

Finally, we come to the conclusion. A burns $a’ = \mathop{\mathrm{argmin}} _ {a \in A} \lvert a - f(a) \rvert$ for each time and B burns an element of $B$ so that no $f(a)$ is changed. Therefore, A burns elements of $A$ in the ascending order of $\lvert f(a) - a \rvert$. Thus the answer is $\max _ {a \in A} \lvert f(a) - a \rvert$ for the first $A$. We can compute all $f(a)$ for $O(\lvert A \rvert)$ since the candidates of $f(a)$ is just two element for each $a$.

Others

I considered this problem in my rest time for lunch, but I came up with the solution above in over 100 minutes. Very late! But fortunately, a colleague of mine was working on his own branch and I was waiting for his work and my work at the moment was reading source codes. So I wrote this article in working time.