AtCoder Beginner Contest 151
Updated:
- Review: 2020-06-16
Source codes
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