# AtCoder Beginner Contest 151

Updated:

AtCoder Beginner Contest 151

• Review: 2020-06-16

# Solutions

## A - Next Alphabet

Just flush $c + 1$.

## B - Achieve the Goal

Assume $0$-indexed.

The minimum score needed to achieve the objective will be $A _ {N - 1} = NM - (A _ 0 + \dots + A _ {N - 2}).$ Flush -1 if $A _ {N - 1} > K$, otherwise $\max(0, A _ {N - 1})$.

## C - Welcome to AtCoder

The total penalty will be the sum of the penalty on each AC problem. The penalty of the AC problem is the count of WAs before getting the first AC. Once we get AC, we can ignore the submissions after that.

## D - Maze Master

We want to calculate the following.

$\max _ {p, q} \mathrm{dist}(p, q)$

Just BFS for each starting point $(i, j)$. The answer is the maximum of the distance. Or use Warshall-Floyd’s algorithm. But it seems to me that, for me, BFS is faster in writing.

## E - Max-Min Sums

Assume $0$-indexed.

### Solution

We solve $\max$ for $(N, K, A)$. Then, we again solve $\max$ for $(N, K, -A)$, where $-A = \{ -a \mid a \in A \}$. The original answer is the sum of them. Let’s consider the former problem.

We can assume that $A$ is in the ascending order. $A _ i$ for $i < K - 1$ cannot be the maximum. $A _ i$ for $i \geq K - 1$ is maximum if we choose $A _ i$ and $K - 1$ elements of $A _ j$ for $0 \leq j < i$. Therefore, the answer is $\sum _ {i = K - 1} ^ {N - 1} \begin{pmatrix} i \\ K - 1 \end{pmatrix} A _ i$

If the values are not different, the result is same. The $\max X$ part can be calculated by just reversing $A$.

## F - Enclose All

### My solution

The possibilities are as follows.

• The circle whose diameter is the distance of the fixed $2$ points.
• The outer circle of the triangle of the fixed $3$ points. Note that if they does not make a triangle, the answer will be calculated by above. Note that if the triangle is degenerated, the diameter of the outer circle is larger than the above.

We can calculate them all and determine whether they contain all the points.

### Supposed Solution

Ternary search for a $2$-dimensional function.

### Ternary search for a $2$-dimensional function

Let $a < b$ and $c < d$ be real numbers.

#### Basics

Fact F.1: Let $f \colon [a, b]$ be a convex function. Then, $f$ is continuous on $(a, b)$.

Therefore $f$ does not necessarily has its minimum value. For example, consider a function $f(x) = x$ on $(0, 1]$ and $f(0) = 1$. In fact, $f$ is convex, but it does not attain its infimum. So we assume that $f$ is convex and continuous on $[a, b]$.

Lemma F.2: Let $f \colon [a, b]$ be a continuous, convex function. Let $c _ 0 = \frac{2a + b}{3}, c _ 1 = \frac{a + 2b}{3}.$ Assume that $f(c _ 0) \leq f(c _ 1)$. Then, $f$ attains its minimum value on $[a, c _ 0]$.

Proof. Assume contrarily that there exists $c _ 1 < x _ 0 \leq b$ so that $f(x) > f(x _ 0)$ holds for all $x \in [a, c _ 1]$. Especially, $f(c _ 1) > f(x _ 0)$. Then, there exists $0 < t < 1$ so that $c _ 1 = t c _ 0 + (1 - t) x _ 0$.

Now that $f$ is convex on $[a, b]$, it holds that \begin{align} f(c _ 1) &= f(t c _ 0 + (1 - t) x _ 0) \\ &\leq t f(c _ 0) + (1 - t) f(x _ 0). \tag{F.1} \end{align} In addition, it holds that $t f(c _ 0) + (1 - t) f(x _ 0) < t f(c _ 1) + (1 - t) f(c _ 1) = f(c _ 1), \tag{F.2}$ which contradicts (F.1). This completes the proof.

#### For $2$-dimensional function

Lemma F.3: Let $N \in \mathbb{N} _ +$. Let $X$ be a set composed of $N$ points on $[a, b] \times [c, d]$. Let $f \colon [a, b] \times [c, d] \to \mathbb{R}$ be defined by $f(x, y) = \max _ {p \in X} \lvert p - (x, y) \rvert.$ Then, $f$ is a continuous, convex function.

Proof. Continuousness is obvious. For $p \in X$, the map $(x, y) \mapsto \lvert p - (x, y) \rvert$ is convex. A finite $\max$ function of convex functions is convex. Therefore, $f$ is convex.

Lemma F.4: Let $f \colon [a, b] \times [c, d]$ be a continuous, convex function. Let $x \in [a, b]$. Let $\mathrm{pr} _ x \colon [c, d] \to \mathbb{R}$ be defined by $\mathrm{pr} _ x (y) = f(x, y).$ Then, $\mathrm{pr} _ x$ is convex.

Proof. Let $y _ 0, y _ 1 \in [c, d]$ with $y _ 0 \neq y _ 1$. Let $0 < t < 1$. To show that $\mathrm{pr} _ x$ is convex, we will show that $\mathrm{pr} _ x (t y _ 0 + (1 - t) y _ 1) \leq t \mathrm{pr} _ x (y _ 0) + (1 - t) \mathrm{pr} _ x (y _ 1). \tag{F.3}$ Let $x _ 0 = x _ 1 = x$. The inequality (F.3) is equivalent to the following. $f(t x _ 0 + (1 - t) x _ 1, t y _ 0 + (1 - t) y _ 1) \leq t f(x _ 0, y _ 0) + (1 - t) f(x _ 1, y _ 1).$ This follows from the fact that $f$ is convex.

Lemma F.5: Let $f \colon [a, b] \times [c, d]$ be a continuous, convex function. Let $g \colon [a, b] \to \mathbb{R}$ be defined by $g(x) = \min _ {y \in [c, d]} f(x, y).$ Then, $g$ is convex.

Proof. Let $x _ 0, x _ 1 \in [a, b]$ with $x _ 0 \neq x _ 1$. Let $0 < t < 1$. Let $y _ 0, y _ 1 \in [a, b]$ so that $g(x _ 0) = f(x _ 0, y _ 0), \ \ \ \ \ g(x _ 1) = f(x _ 1, y _ 1).$ Then, it follows that \begin{align} g(t x _ 0 + (1 - t) x _ 1) &\leq f(t x _ 0 + (1 - t) x _ 1, t y _ 0 + (1 - t) y _ 1) \\ &\leq t f(x _ 0, y _ 0) + (1 - t) f(x _ 1, y _ 1) \\ &= t g(x _ 0) + (1 - t) g(x _ 1) \end{align} by the definition of $g$ and the convexness of $f$. This completes the proof.

Proposition F.6: We can compute the minimum value of $f$ by calculating the minimum value of $g$ by ternary search, where we compute the value of $g$ by ternary search.

Proof. This is a direct consequence of Lemma F.2, Lemma F.4 and Lemma F.5. What we have to check is that $\min _ {(x, y)} f(x, y) = \min _ {x \in [a, b]} \min _ {y \in [c, d]} f(x, y) = \min _ {x \in [a, b]} g(x).$

# Others

Original:

A - sample: 2, tle: 2.000, time: 00:49, from_submit: 55:19
B - sample: 3, tle: 2.000, time: 03:02, from_submit: 52:17
C - sample: 3, tle: 2.000, time: 04:07, from_submit: 48:10
D - sample: 2, tle: 2.000, time: 10:58, from_submit: 37:12
E - sample: 4, tle: 2.000, time: 11:04, from_submit: 26:08
F - sample: 3, tle: 2.000, time: 26:08, from_submit: 00:00


Review 2020-06-16:

A - sample: 2, tle: 2.000, time: 03:05, from_submit: 44:00
B - sample: 3, tle: 2.000, time: 02:20, from_submit: 41:39
C - sample: 3, tle: 2.000, time: 04:19, from_submit: 37:20
D - sample: 2, tle: 2.000, time: 12:18, from_submit: 25:03
E - sample: 4, tle: 2.000, time: 09:54, from_submit: 15:08
F - sample: 3, tle: 2.000, time: 15:09, from_submit: 00:00


Tags:

Categories: