AtCoder Beginner Contest 151

Updated:

AtCoder Beginner Contest 151

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

Just BFS for each starting point $(i, j)$. The answer is the maximum of the distance.

Or use Warshall–Floyd’s algorithm.

E - Max-Min Sums

We can separately compute $\max X$ and $\min X$. First we compute the sum of $\min X$. Without loss of generalities, we assume that $A$ is in the ascending order.

To simplify the situation, all the values are different. We fix $\min X = A[i]$. Then, what happens? $X$ won’t contain $A[j]$ for $j < i$ and does contain $A[i]$. Thus $K - 1$ elements of $A[j]$ for $j > i$ will be contained. The possibility will be \[ \begin{pmatrix} N - i - 1 \\\ K - 1 \end{pmatrix} \] Therefore the sum of $\min X$ will be as follows. \[ \sum _ {i = 0} ^ {N - 1} A _ i \begin{pmatrix} N - i - 1 \\\ K - 1 \end{pmatrix} \]

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$. Indeed, $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 tha 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 convex function.

Proof. 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 $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 $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

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