# AtCoder Beginner Contest 141

Updated:

AtCoder Beginner Contest 141

• Review: 2020-06-04

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

Tags:

Categories: