AtCoder Beginner Contest 139

Updated:

AtCoder Beginner Contest 139

Source codes

Solutions

A - Tenki

Just compare $S$ and $T$.

B - Power Socket

First, we have $1$ sockets. We add a power strip to gain $A - 1$ sockets. Therefore we continue to add power strip $t$ times to gain $t(A - 1) + 1$. Then, we have \[ t (A - 1) + 1 \geq B. \] The answer is ((B - 1) + (A - 1) - 1 )/(A - 1).

C - Lower

We reverse the order of $H$. We define a $DP$ table as follows.

$DP[i] = $ the length of the increasing sequence that starts the $i$-th element to the right.

The initial state: $DP[i] = 0$ for $i = 0, \dots, H - 1$. The answer: $\max _ i DP[i]$. The transition: For $i = 1, \dots, H - 1$, \[ DP[i] = \begin{cases} DP[i - 1] + 1 & H[i] \geq H[i - 1], \\\ 0 & \text{otherwise}. \end{cases} \]

D - ModSum

Answer

The answer is $N(N - 1)/2$.

Reasoning

We assume $1$-indexed. We define $f \colon \mathfrak{S} _ N \to \mathbb{N}$ as follows. \[ f(\sigma) = \sum _ {i = 1} ^ N \sigma(i) \text{ mod } i. \] Here, we have $(\sigma(i) \text{ mod } i) \leq i - 1$. Then, for $\sigma \in \mathfrak{S} _ N$, it follows that \[ f(\sigma) \leq \sum _ {i = 1} ^ N i = \frac{N(N - 1)}{2}. \] Thus we have the upper bound of the answer as the right hand side. This bound actually attains by \[ \sigma = \begin{pmatrix} 1 & 2 & 3 & \dots & N \\\ N & 1 & 2 & \dots & N - 1 \end{pmatrix}. \]

E - League

Assume $0$-indexed.

Answer #1

We can solve this problem by a greedy algorithm as follows.

We hold the information of $A$ by vector<queue> A; Player $i$ and $j$ can be matched if and only if $A[i].front() = j \land A[j].front() = i$. We have to spend one day to match all of these and that’s the best way. If there is no matches but there remains competition, the answer is -1.

The important thing is time complexity. If you check all players every day, the total time complexity would be $O(N^3)$, which cannot work in this problem. Consider that new matches $(i, j)$ will occur if either $i$ or $j$ would match the day before. So keeping who matched today will reduce time complexity. With this trick, the solution works in $O(N^2)$-time.

Answer #2

We convert the each matches $(i, j)$ into $\mathbb{N}$-numbered vertexes. Then, the constraints of $A$ will be the order of the vertexes. Let’s consider them into edges. Then, the problem becomes as follows. Given this graph $G$, you will flush -1 if there is any loop. If not, you will flush the maximum length of this DAG $G$. This can be solved by DFS.

In the following code, we check whether there is a loop in $G$ by collecting vertexes by set<point> Y;

int dfs(point p)
{
  if (DP.find(p) != DP.end())
  {
    return DP[p];
  }
  if (Y.find(p) != Y.end())
  {
    No();
  }
  Y.insert(p);
  int tmp{0};
  for (auto e : V[p])
  {
    tmp = max(tmp, dfs(e) + 1);
  }
  Y.erase(p);
  return DP[p] = tmp;
}

F - Engines

Answer

Assume $0$-indexed. Let $V = \{ v _ 0, v _ 1, \dots, v _ {N - 1} \} \subset \mathbb{R}^2$. The problem requires that we make $w = \sum _ { i \in {I} } v _ i$ for some $I \subset N$ to attain the maximum of the Euclid norm $\lvert \cdot \rvert$. This problem is equivalent to the following problem.

Find $I \subset N$ and $e \in \mathbb{R} ^ 2$ with $\lvert e \rvert = 1$ that attains the maximum of $(w, e)$.

This equivalence can be easily seen because for any $w \in \mathbb{R} ^ 2 \setminus \{ 0 \}$ we set $e = w/\lvert w \rvert$ to maximize $(w, e)$ and then it follows that $\lvert w \rvert = (w, e)$.

We have the following equation. \[ (w, e) = \sum _ {i \in I} (v _ i, e). \] This equation tells us how to make $I \subset N$. Fix $e \in \mathbb{R}^2$. Then, for $i \in N$, if $(v _ i, e) > 0$, we take $i$ into $I$; otherwise not.

Therefore, if $w$ attains its maximum norm, there exists $e \in \mathbb{R}^2$ with $\lvert e \rvert = 1$ so that for any $i \in I$, it follows that $(v _ i, e) > 0$ and for any $i \in N \setminus I$, it follows that $(v _ i, e) \leq 0$.

Therefore, after we sort $V$ by $\arg$, we only consider some range of $V$. We can try all of them in $O(N^3)$ time or $O(N^2)$ time.

Others