AtCoder Beginner Contest 148

AtCoder Beginner Contest 148

• Review: 2020-06-10

Source codes

• My submissions (AtCoder)
• My source codes (GitHub)

Solutions

A - Round One

Flush $6 - A - B$.

B - Strings with the Same Length

Just do as they indicate us to.

C - Snack

Flush $\mathrm{lcm}(A, B)$.

D - Brick Break

We can compute the maximum of the remaining bricks by greedy algorithm.

E - Double Factorial

Solution

Let

$g(n, p) = $ how many times $n$ can be divided by $p$.

The answer is \[ g(n!!, 10) = \min(g(n!!, 2), g(n!!, 5)). \] If $n$ is odd, it immediately follows that $g(n!!, 2) = 0$. Hence the answer is zero. Hereinafter we assume that $n$ is even. We see that \[ \begin{align} n!! &= n \cdot (n - 2) \cdot \dots \cdot 4 \cdot 2, \\
\frac{n}{2}! &= \frac{n}{2} \cdot \left( \frac{n}{2} - 1 \right) \cdot \dots \cdot 2 \cdot 1. \end{align} \] Therefore we see that \[ \begin{align} g(n!!, 2) &= g\left( \frac{n}{2}!, 2 \right) + \frac{n}{2}, \\
g(n!!, 5) &= g\left( \frac{n}{2}!, 5 \right). \end{align} \] In addition, it follows that \[ g(n!, p) = \frac{n}{p} + g\left( \frac{n}{p}!, p \right) + \frac{n}{p}. \] And it stops by $g(0, p) = 0$.

Another Solution

Just count how many $5$s $N!!$ has as factors. This is done directly as follows.

  if (N & 1)
  {
    cout << 0 << endl;
    return 0;
  }
  ll M{N};
  ll five{0};
  while (M >= 5)
  {
    five += M / 10;
    M /= 5;
  }
  cout << five << endl;

F - Playing Tag on Tree

Solution

First of all, Takahashi-kun and Aoki-kun can’t pass each other. Therefore, Takahashi-kun cannot reach the vertex $x$ where $\mathrm{dist} _ T(x) \geq \mathrm{dist} _ A (x)$. Of course the vertexes on Aoki-kun’s side won’t be reached by Takahashi-kun. Otherwise, let $y$ be the intersection point of Takahashi and Aoki on the pass from the initial vertexes. We have $\mathrm{dist} _ T(y) \geq \mathrm{dist} _ A (y)$, which means Aoki-kun can capture Takahashi-kun as long as he wants to reach $x$. On the contrary, Takahashi-kun can reach $x$ where $\mathrm{dist} _ T(x) < \mathrm{dist} _ A (x)$.

In addition, we see that, if Takahashi-kun reaches $x$, Aoki-kun will take $\mathrm{dist} _ A (x) - 1$ turns to capture him. Note that $-1$ means that Takahashi-kun will be captured in front of $x$. Therefore we can achieve \[ \max _ {x \colon \mathrm{dist} _ T(x) < \mathrm{dist} _ A (x)} \mathrm{dist} _ A (x) - 1. \] In addition, this is the maximum value since Aoki-kun cannot reach each vertex $x$ by less than $\mathrm{dist} _ A (x)$ turns.

Others

Review 2020-06-10:

Assignments:
A - sample: 2, tle: 2.000, time: 02:12, from_submit: 21:36
B - sample: 3, tle: 2.000, time: 01:02, from_submit: 20:33
C - sample: 3, tle: 2.000, time: 00:42, from_submit: 19:52
D - sample: 4, tle: 2.000, time: 04:15, from_submit: 15:36
E - sample: 3, tle: 2.000, time: 05:14, from_submit: 10:23
F - sample: 4, tle: 2.000, time: 10:23, from_submit: 00:00