AtCoder Beginner Contest 166
Updated:
Source codes
Solutions
A - A?C
If $S = $ “ABC”, flush “ARC”. If $S = $ “ARC”, flush “ABC”.
B - Trick or Treat
Make the histogram of $A _ {ij}$ and count $0$s.
C - Peaks
For $e = (v, w)$, if $H[v] > H[w]$, $w$ will no longer satisfy the condition; if $H[v] < H[w]$, $v$ will no longer satisfy the condition; if $H[v] = H[w]$, neither $v$ nor $w$ satisfies the condition.
When all the edges pass, the remaining vertexes satisfy the condition. Count the number of them.
D - I hate Factorization
Solution
It suffice to try all $(A, B)$ with $-300 \leq A, B \leq 300$.
Reasoning
We will prove the validness of the strategy above in a little extended version.
Let $f(A, B) = A ^ 5 - B ^ 5$ for $A, B \in \mathbb{Z}$. For $A \in \mathbb{Z}$, let $g _ A(B) = f(A, B)$ for $B \in \mathbb{Z}$.
Lemma D.1: For $A \in \mathbb{Z}$, it holds that \[ \min _ {B \neq A} \left\lvert g _ A(B) \right\rvert = \min \left( \left\lvert f(A, A - 1) \right\rvert, \left\lvert f(A, A + 1) \right\rvert \right). \tag{D.1} \]
Proof: We see that $g _ A$ is a decreasing function and $g _ A(A) = 0$. This implies (D.1).
Lemma D.2: If $A \not \in [-300, 300)$ and $B \neq A$, it holds that \[ \lvert f(A, B) \rvert > 10 ^ 9. \tag{D.2} \]
Proof: It holds that \[ f(A, B) = (A - B)\left(A ^ 4 + A ^ 3 B + A ^ 2 B ^ 2 + A B ^ 3 + B ^ 4 \right). \] We see that \[ \left\lvert f(A, A - 1) \right\rvert = \left\lvert A ^ 4 + A ^ 3 (A - 1) + A ^ 2 (A - 1) ^ 2 + A (A - 1) ^ 3 + (A - 1) ^ 4 \right\rvert. \] Thus, if $A - 1 \geq 200$, \[ \left\lvert f(A, A - 1) \right\rvert > 5 \cdot (200)^4 > 10 ^ 9. \tag{D.3} \] The same inequality holds if $A < -200$. In addition, we also see that \[ \left\lvert f(A, A + 1) \right\rvert = \left\lvert A ^ 4 + A ^ 3 (A + 1) + A ^ 2 (A + 1) ^ 2 + A (A + 1) ^ 3 + (A + 1) ^ 4 \right\rvert. \] We apply the same argument above to see that, if $A \geq 200$ or $A + 1 \leq -200$, \[ \left\lvert f(A, A + 1) \right\rvert > 5 \cdot (200)^4 > 10 ^ 9. \tag{D.4} \] If $A \not \in [-300, 300)$ and $B \neq A$, both (D.3) and (D.4) holds. Therefore, by Lemma D.1, we see that \[ \lvert f(A, B) \rvert \geq \min _ {B \neq A} \left\lvert g _ A(B) \right\rvert > 10 ^ 9. \]
Proposition D.3: Let $\lvert X \rvert \leq 10 ^ 9$. Then, the following condition (i) and (ii) are equivalent.
(i) There exists such $(A, B) \in \mathbb{Z} ^ 2$ that $f(A, B) = X$.
(ii) There exists such $(A, B) \in [-300, 300) ^ 2$ that $f(A, B) = X$.
Proof: It is obvious that (ii) $\Longrightarrow$ (i) holds. Suppose (i). If $X = 0$, it holds that $f(A, B) = 0$ for any $(A, B)$ with $A = B$, which implies (ii). Hereinafter assume that $X \neq 0$. Let $(A, B) \in \mathbb{Z} ^ 2$ be such that $f(A, B) = X$. It holds that $A \neq B$. Assume to the contrary that $A \not \in [-300, 300)$. Then, by Lemma D.2, (D.2) holds. Since $X \leq 10 ^ 9$, this implies that $f(A, B) > X$, which is a contradiction. Thus, we admit that $A \in [-300, 300)$. Assume to the contrary that $B \not \in [-300, 300)$. Seeing that $f(A, B) = -f(B, A)$, we can apply Lemma D.2 to see that $f(A, B) > X$, which is again a contradiction. Therefore, we see that $(A, B) \in [-300, 300) ^ 2$, which implies (ii). This completes the proof.
E - This Message Will Self-Destruct in 5s
Solution
We count the number of $(i, j) \in N ^ 2$ with $j > i$ and $A _ j + A _ i = j - i$. This is equivalent to the following condition.
\[
j - A _ j = A _ i + i.
\]
Let map<ll, ll> $M$ be the dynamic histogram of $\{ A _ i + i \} _ {i < j}$. For $i = 0, \dots, N - 1$, we ask $M[i - A _ i]$ and add it to the counter. After that, we make an increment: $M[A _ i + i]{ + + };$.
F - Three Variables Game
Let $a$, $b$ and $c$ be the numbers of $A$, $B$ and $C$, respectively. We will use the characters $X$, $Y$ being either $A$, $B$ or $C$ with $X \neq Y$. Let $x$ and $y$ the numbers corresponding to $X$ and $Y$, respectively.
Solution
The following lemma is obvious, but plays an important role.
Lemma F.1: We cannot continue playing this game if and only if we encounter the event $XY$ with $x = y = 0$.
Let $s = a + b + c$. We exclude the case $s = 0$; the answer is “No” since $N \geq 1$. Note that each manipulation does not alter $s$.
Case $s = 1$
It is difficult to manage to play the game when $s$ is small. First, consider $s = 1$. In this case, our choice is determined uniquely for each step. Just adding $1$ to $0$ and subtract $1$ from $1$. If we encounter $x = y = 0$, the answer is “No”; otherwise “Yes” and flush that unique set of manipulations.
Case $s \geq 2$
Lemma F.2: Assume $s \geq 2$. The answer is “No” if and only if, given the first string is $XY$, it holds that $x = y = 0$. Otherwise, we can complete playing the game.
Proof: Assume that we are given the string $XY$ and $x + y \geq 1$. Our strategy is stated as follows.
- If $x = 0$, we make an increment of $x$ and a decrement of $y$.
- If $y = 0$, we make an increment of $y$ and a decrement of $x$.
- Otherwise, we make an increment of the variable which appears in the next step, too.
We prove that, if we adopt this strategy in this turn, we won’t make the game terminated in the next turn. By Lemma F.1, it suffice to show that, in the next turn, we won’t encounter the situation that $x’ + y’ = 0$, where $x’$ and $y’$ are next variables we will take an action for.
Assume that $x = 0$. If the next string is also $XY$, we can continue the next turn. Assume that the string is different. If $y \geq 2$, both $x$ and $y$ become positive. Thus, we can continue the next turn. Suppose that $y = 1$. Let $z$ be the variable other than $x$ or $y$. In this case, It follows that $z = s - x - y = s - 1 \geq 1$. Hence, we can continue the next turn as desired. The case $y = 0$ is the similar.
Assume that $x, y \geq 1$. Since we make an increment of the variable which appears in the next step, it implies that $x’ + y’ \geq 1$ in the next turn as desired. This completes the proof.