AtCoder Beginner Contest 165

AtCoder Beginner Contest 165

Source codes

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

Solutions

A - We Love Golf

Check is the largest multiple of $K$ less than or equal to $B$ is greater than or equal to $A$ or not, i.e., $(N / B) \times B \geq A$.

B - 1%

Just do the simulation. Use boost::multiprecision::cpp_int to prevent overflow. The calculation “$\times 1.01$” should be done by *= 101; and /= 100;.

C - Many Requirements

Apply brute-force method. The maximum number of possibilities will be $\begin{pmatrix} 20 \\ 10 \end{pmatrix} \approx 1.85 \times 10 ^ 5$.

We can construct the vector of the sequences of the length $n$ from that of the length $n - 1$ recursively.

D - Floor Function

Let $x = By + z$ with $y, z \in \mathbb{N}$ and $0 \leq z < B$. Then, we have \[ \begin{align} f(x) &= \left\lfloor \frac{Ax}{B} \right\rfloor - A \left\lfloor \frac{x}{B} \right\rfloor \\
&= \left\lfloor \frac{ABy + Az}{B} \right\rfloor - A \left\lfloor \frac{By + z}{B} \right\rfloor \\
&= Ay + \left\lfloor \frac{Az}{B} \right\rfloor - Ay \\
& = \left\lfloor \frac{Az}{B} \right\rfloor. \end{align} \] This is an increasing function for $z$. Therefore, $\max _ {0 \leq x \leq N} f(x) = f(\min(B - 1, N))$.

E - Rotation Matching

Solution

Assume $0$-indexed.

Consider the satisfying condition that $\{ (x _ i, y _ i) \} _ {i \in N}$ should be a valid allotment. The following condition is a satisfying condition. \[ \sharp \{ y _ i - x _ i, x _ i - y _ i \in \mathbb{Z} / N \mathbb{Z} \mid i \in M \} = 2M \tag{E.1} \]

We can assume that $N = 2M + 1$. The following picture gives an answer.

Implement

The following code gives an answer ($1$-indexed).

  N = M * 2 + 1;
  for (auto i{0}; i < M / 2; ++i)
  {
    cout << 1 + i << " " << M - i << endl;
  }
  for (auto i{0}; i < M - M / 2; ++i)
  {
    cout << M + 1 + i << " " << N - i << endl;
  }

F - LIS on Tree

DP for the typical LIS

We recall the typical LIS. Assume that we calculate the length of the LIS on $\{ a[i] \} _ {i \in N}$.

Definition

We update the following table.

vector<int> $dp[i] = $ the minimum tail of the LIS of the length $(i + 1)$ in the current state.

Note that $dp$ is an increasing function of $i$.

Initial state

$dp[i] = \infty$.

Answer

The minimum index $i$ so that $dp[i] = \infty$. This is calculate by the following code.

lower_bound(dp.begin(), dp.end(), infty) - dp.begin();

Transition

For $i = 0, \dots, N - 1$, we find the minimum index $j$ so that $dp[j] \geq a[i]$ and $dp[j] \gets a[i]$. This is done by the following code.

*lower_bound(dp.begin(), dp.end(), a[i]) = a[i];

Solution

For each transition, we update just one line. Therefore, we can easily rollback in each step.

This is convenient for DFS. We use one LIS table and keep reusing it. When we come to the vertex, we do the transitions and calculation above. After visiting the children, we rollback it as follows.

  void dfs(int src = 0, int parent = -1)
  {
    ans[src] = lis.query(a[src]);
    for (auto const &e : v[src])
    {
      if (e.dst != parent)
      {
        dfs(e.dst, src);
      }
    }
    lis.rollback();
  }

Others