AtCoder Beginner Contest 163

Updated:

AtCoder Beginner Contest 163

Source codes

Solutions

A - Circle Pond

Flush $2 \pi R$ with $\pi$ being M_PI.

B - Homework

Assume $0$-indexed.

The number of possible holidays is \[ X = N - \sum _ {i \in M} A _ i. \]

We flush $X$ if $X \geq 0$; otherwise -1.

C - management

We make the histogram of $A _ i$ and flush it.

D - Sum of Large Numbers

$10 ^ {100}$ is so large that this problem can be transformed into the following one.

Let $K \leq X \leq N + 1$. Choose $X$ elements from $\{ 0, 1, \dots, N \}$ and let $S$ be its sum. Then, how many possibilities of $(X, S)$ are there?

Assume $X$ is fixed. Then, the minimum of $S$ is \[ lb(X) = 0 + 1 + \dots + (X - 1) = \frac{X(X - 1)}{2}, \] wheres the maximum of $S$ is \[ ub(X) = N + (N - 1) + \dots + (N - (X - 1)) = NX - \frac{X(X - 1)}{2}. \] $S$ can be achieved any integers in $[lb, ub]$. Therefore, the answer is calculated as follows. \[ \sum _ {X = K} ^ {N + 1} \left( ub(X) - lb(X) + 1 \right). \]

E - Active Infants

Assume $0$-indexed.

Observation

Let $\sigma \in \mathfrak{S} _ N$. The score is described as follows. \[ f(\sigma) = \sum _ {i \in N} A _ i \lvert i - \sigma(i) \rvert. \] Here, we have the following relation about absolute value. \[ \lvert i - \sigma(i) \rvert = \max \{ i - \sigma(i), \sigma(i) - i \}. \] Hence, it follows that \[ f(\sigma) = \max _ {U \sqcup L = N} \left( \sum _ {i \in L} A _ i (\sigma(i) - i) + \sum _ {i \in U} A _ i (i - \sigma(i)) \right). \] What we want to find is \[ \max _ {\sigma \in \mathfrak{S} _ N} f(\sigma) = \max _ {U \sqcup L = N} \max _ {\sigma \in \mathfrak{S} _ N} \left( \sum _ {i \in L} A _ i (\sigma(i) - i) + \sum _ {i \in U} A _ i (i - \sigma(i)) \right). \] We fix the disjoint union $U \sqcup L = N$. How can we find the maximum argument of $\mathfrak{S} _ N$? Let $i, j \in U$ with $A _ i > A _ j$. If $\sigma$ gives its maximum, it follows that $\sigma(i) < \sigma(j)$, which is equivalent to \[ \left( A _ i (\sigma(i) - i) + A _ j (\sigma(j) - j) \right) - \left( A _ i (\sigma(j) - i) + A _ j (\sigma(i) - j) \right) = (A _ i - A _ j)(\sigma(i) - \sigma(j)) > 0. \] Thus, to summarize the situations, we have the followings.

  • For any $i, j \in U$ with $A _ i > A _ j$, we have $\sigma(i) < \sigma(j)$.
  • For any $i, j \in L$ with $A _ i > A _ j$, we have $\sigma(i) > \sigma(j)$.

Therefore, once we fix $U \sqcup L = N$, a greedy algorithm to determine $\sigma(i)$ in $A _ i$’s descending order works.

DP-part

Let $V = \{ A _ i, i \}$ be sorted in descending order.

Definition

vector<vector<ll>> $dp[i][j] = $ the possible maximum by determining $V[0, i)$’s places, with $\lvert U \rvert = j$.

Initial state

$dp[0][0] = 0$. Otherwise, $dp[i][j] = -\infty$.

Answer

$\max _ {0 \leq j \leq N} dp[N][j]$.

Transition

For $i = 0, \dots, N - 1$, let $(a, ind) = V[i]$. For $j = 0, \dots, N$, if $dp[i][j] = -\infty$, continue;.

We think both of the cases $ind \in U$ or $ind \in L$. For the former one, $\sigma(ind) = j$; for the latter one, $\sigma(ind) = N - 1 - (i - j)$. Hence, We execute the following two manipulations. \[ \begin{align} dp[i + 1][j + 1] &\gets ^ {\max} dp[i][j] + a (j - ind), \\ dp[i + 1][j] &\gets ^ {\max} dp[i][j] + a (N - 1 - (i - j) - ind). \end{align} \] Actually, $j$ runs in $[0, i]$. Thus, the out-of-range problem will not occur.

F - path pass i

Assume $0$-indexed.

Basic strategy

We count the number of simple paths that won’t visit $k$-colored vertexes and subtract it from $N (N + 1) / 2$.

This number can be calculated by gathering the subgraphs generated by eliminating $k$-colored vertexes, more precisely, the sizes of them. Let $V _ k = \{ s _ 0, \dots, s _ l \}$ be the collection of its sizes. Then, what we want to calculate is $\sum _ {i = 0} ^ {l} s _ i (s _ i + 1) / 2$.

Solution (recursive DFS + colored stack)

We want to obtain $V _ k$ for all $k \in N$ in $O(N)$-time by DFS.

DFS

Consider the following graph, where black vertex is colored by $color$. We consider how to determine a subgraph $\{ 3 \}$ for this $color$.

F, DFS

We use recursion and a vector of stacks $S$. Here, $S[color]$ has temporary subtrees that are not subtracted.

We give IDs for vertexes while visiting them. When the we visit back $3$ from $9$, we can determine the size of subtree $subtree$ whose root is $3$ by $9 - 3 + 1 = 7$. Then, we come back $1$ from $3$. We would like to get the size of the subgraph containing $3$ where $color$-colored vertexes are removed.

We look at $S[color]$, which are aligned by ids in descending order. Let $(id, size)$ be its top element. If $id$ is less than $1$, it means $subtree$ contains $(id, size)$, so we subtract $size$ from $subtree$’s size to obtain the size of the $color$-colored-removed subgraph.

Key Point

We have to get all $V[color]$ by one DFS. Thus, what we can use is restricted as follows.

  • Information of DFS without color: going out and coming back.
  • Colored stacks.

Other solution

We can use BIT or Segment tree instead of colored stack.

Others