AtCoder Beginner Contest 141
Updated:
- Review: 2020-06-04
Source codes
Solutions
A - Weather Prediction
Just use if structures.
B - Tap Dance
Assume $0$-indexed. We check $S[i]$ for each $i = 0, \dots, \lvert S \rvert - 1$. If $i \% 2 = 0 \land S[i] = \mathrm{L}$, the answer is "No". If $i \% 2 = 1 \land S[i] = \mathrm{R}$, the answer is "No". Otherwise the answer is "Yes".
C - Attack Survival
Assume $0$-indexed. We write \[ P[k] = \sharp \{ i \in N \mid A[i] = k \}. \] The final score of player $i \in N$ is $K - (Q - P[k])$. So this solution work in $O(N)$-time.
D - Powerful Discount Tickets
In this problem / will mean the division in the computer. Then we have
\[
(x / 2) / 2 = (x \mathbin{> >} 1) \mathbin{> >} 1 = x \mathbin{> >} 2 = x / 4
\]
for any $x \in \mathbb{N}$. Thus we can use discount tickets one by one. Therefore, the greedy algorithm works as follows. Let $Q$ be a priority queue by the descending order. We push all $A _ i$ in $Q$. We continue to use a discount ticket for $Q.top()$. The time complexity is $O(N \log N + M \log N)$.
E - Who Says a Pun?
Solution
First, we compute the length of the plain longest common substring.
$calc(i, j) = $ the length of the longest common substring which starts by $S[i]$ and $S[j]$ for $i \neq j$.
This can be computed by a memo-recursion method as follows.
\[
calc(i, j) =
\begin{cases}
calc(i + 1, j + 1) + 1 & S[i] = S[j], \\
0 & i \not \in N \lor j \not \in N \lor S[i] \neq S[j].
\end{cases}
\]
The answer is
\[
\max _ {i, j \in N, i \neq j} \min \left( calc(i, j), \lvert i - j \rvert \right).
\]
F - Xor Sum 3
Solution
Assume $0$-indexed. Let $X _ b$ and $X _ a$ be the xor sum of blue and red numbers respectively. First we compute \[ X = \bigoplus _ {i \in N} A _ i. \] If the $k$-th bit is $0$, the pair of each $k$-th bit of $X _ b$ and $X _ a$ will be $(1, 1)$ or $(0, 0)$. If the $k$-th bit is $1$, the pair of each $k$-th bit of $X _ b$ and $X _ a$ will be $(1, 0)$ or $(0, 1)$, which will not affect the final result. So we ignore those bits of $X$ for the following argument. Thus $X _ b = X _ a$ holds, supposing we have ignored unneeded bits. So our aim is to maximize $X _ b$ by choosing good elements in $\{ A _ i \}$.
Linear algebra on $\mathbb{F} _ 2$
We can solve this problem in terms of linear algebra on $\mathbb{F} _ 2$. We have \[ X _ b = \sum _ {i \in N} a _ i A _ i, \tag{F.1} \] where $a _ i \in \mathbb{F} _ 2$, $\sum$ means $\oplus$. We are assigned to find max element in the vector space $\langle A _ 0, \dots, A _ {N - 1} \rangle \subset 2 ^ {60}$. The maximum can be calculated by the following greedy method. Note that we’ve ignored unneeded bits.
First we consider whether we can make the highest bit equal to $1$. We can do it if and only if there is an element $A _ i$ whose highest bit is $1$. If yes, we swap $A _ 0$ and $A _ i$ and we make $A _ i \gets A _ i \oplus A _ 0$ if the highest bit of $A _ i$ is equal to $1$ for all $i \in N \setminus \{ 0 \}$. We use $A’ _ i$ to denote the new $A _ i$. If follows that \[ \langle A’ _ 0, \dots, A’ _ {N - 1} \rangle = \langle A _ 0, \dots, A _ {N - 1} \rangle. \] In addition all the highest bit of $A’ _ i$ for $i \in N \setminus \{ 0 \}$ is $0$. So if we maximize \[ X _ b = \sum _ {i \in N} a’ _ i A’ _ i, \] we conclude that $a’ _ 0 = 1$ if and only if the highest bit is $1$. We say we have created $A’ _ 0$.
We continue to this transformation. Suppose $A _ 0, \dots, A _ {R - 1}$ have been created. Find an element $A _ i$ for $i \geq R$ whose bit now considered is $1$. If we can’t find, we cannot create $A _ R$ and we jump to the next bit. If we’ve found one, swap $A _ R$ and $A _ i$ and we convert $A _ i \gets A _ i \oplus A _ R$ for $i \in N \setminus \{ R \}$ if the bit considered now of $A _ i$ is equal to $1$. We have created the new $A _ R$.
The final result is (F.1) where $a _ i = 1$ for all $i = 0, \dots, R - 1$; otherwise $a _ i = 0$ (or $1$ is also good because $A _ i = 0$ for any $i \geq R$ by ignoring the unneeded bits).
This solution works in $O(60N) = O(N)$-time.