# AtCoder Beginner Contest 125

Updated:

AtCoder Beginner Contest 125

# Solutions

## A - Biscuit Generator

Flush $BT / A$.

## B - Resale

Assume $0$-indexed. For $i \in N$, if $V _ i > C _ i$, we should take this gem and get $V _ i - C _ i$ value in total; otherwise we should not. Therefore the answer is $\sum _ {i \in N} \max(0, V _ i - C _ i).$

## C - GCD on Blackboard

Assume $0$-indexed.

If we choose $A _ i$ to change, the answer is $G _ i = \gcd \{ A _ j \in \mathbb{N} \mid j \in N \land j \neq i \} \tag{C.1}$

Then, how can we calculate this quickly? We can rearrange (C.1) as follows. $G _ i = \gcd \left( \gcd \{ A _ j \mid j < i \}, \gcd \{ A _ j \mid j > i \} \right).$ Let $L[i] = \gcd \{ A _ j \mid j < i \}, \ \ \ \ R[i] = \gcd \{ A _ j \mid j > i \}.$ We can calculate this by recursion as follows. Let $L = A _ 0$. We execute the following for $i = 1, \dots, N - 2$. $L[i + 1] = \gcd(L[i], A _ i).$ Let $R[N - 2] = A _ {N - 1}$. We execute the following for $i = N - 2, N - 3, \dots, 2$. $R[i - 1] = \gcd(R[i], A _ i).$

To calculate $G _ i$’s, first we determine $G _ 0 = R$ and $G _ {N - 1} = L[N - 1]$. Then, we calculate $G _ i = \gcd(R[i], L[i])$ for $i = 1, \dots, N - 2$. The answer is $\max _ {i \in N} G _ i$.

## D - Flipping Signs

Assume $0$-indexed.

### Observation

Let $s _ i$ be the sign of the resulting coefficient corresponding to $A _ i$. First, we show the following lemma.

Lemma F.1: Let $k \in N$. Assume that we are given $\{ s _ i \}$. Then, there exists a manipulations that gives $\{ s _ i \}$ for all $i \in N$ except $k$.

Proof. For each $i$, we can choose whether we do the manipulation or not. The order of $i$ is,

• $i = 0, 1, 2, \dots, k - 1$, and
• $i = N - 1, N - 2, \dots, k + 1$.

We have $\{ s _ i \}$ as the result except $k$.

Then, what $s _ k$ will be? This is determined by the following lemma.

Lemma F.2: The number of the negatives in $\{ s _ i \}$ is even.

Proof. Each manipulation changes the number of the negatives $\pm 2$ or $0$. Therefore the parity will be preserved.

### Solution

We can apply greedy method almost perfectly. Then the desired maximum would be $S = \sum _ {i \in N} \lvert A _ i \rvert.$ We count the number of zeros and negatives. If there exists a zero, $S$ is achieved. If the number of negatives is even, $S$ is achieved. Otherwise, $S$ will not be achieved by Lemma F.1 and F.2. We have to sacrifice one element. It should be the absolutely minimum element. Thus the answer in this case is $S - 2 \min _ {i \in N} \lvert A _ i \rvert.$

Tags:

Categories: