# AtCoder Beginner Contest 139

Updated:

AtCoder Beginner Contest 139

# 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

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.

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.

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

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.

Tags:

Categories: