AtCoder Beginner Contest 125
Updated:
Source codes
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[1] = 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[0]$ 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. \]