# AtCoder Beginner Contest 142

Updated:

AtCoder Beginner Contest 142

• Review: 2020-06-05

# Solutions

## A - Odds of Oddness

Just calculate by for-loop.

Or let $M = (N + 1) / 2$. Then flush $M / N$, casting them into double.

## B - Roller Coaster

Just calculate by for-loop, too.

## C - Go to School

### Solution #1

We use vector<tuple<int, int>> V;. We insert $(A _ i, i)$ into $V$ and sort it.

### Solution #2

Assume $0$-indexed.

Let $X[i]$ be the $i$-th person who came to the school. Then, it holds that $X[A _ i - 1] = i$. Flush $X$ in the ascending order.

## D - Disjoint Set of Common Divisors

Let $M = \mathrm{lcm}(A, B)$. Count the prime factors by your library.

  ll A, B;
cin >> A >> B;
Sieve sieve;
auto V{sieve.factor(gcd(A, B))};
cout << V.size() + 1 << endl;


## E - Get Everything

### Solution

This is done by bit-DP.

#### Definition

For $c \in \mathcal{P}(N)$, we define $DP[c]$ as follows.

$DP[c] =$ the minimum cost to buy a set of keys that enable us to unlock all the box $b \in c$.

Flush $DP[2 ^ N - 1]$ if it is not $\infty$, otherwise flush -1.

#### Initial State

$DP[0] = 0$, otherwise $\infty$.

#### Transition

For all $(a, k)$, for all $j \in \mathcal{P}(N)$, we execute the following. $DP[j \cup k] \gets \min(DP[j \cup k], DP[j] + a).$

## F - Pure

If $M = 0$, the answer is -1. Hereinafter we assume that $M \geq 1$.

### Observation

Suppose there exists an induced subgraph $G’$ of $G$ whose in-degree and out-degree of every vertex are both $1$. How is the structure of $G’$? We can easily see that it is a simple cycle and its disjoint union.

However, many algorithm that determines whether the graph has a cycle or not do not detect a simple cycle. If the answer is yes, they just tell us there is a cycle. In this problem, $O(N ^ 2 + M ^ 2)$-solution is allowed.

### My solution

We focus on the fact that the smallest cycle must be a simple cycle. We determine the smallest cycle by brute-force method.

Fix an edge $(A, B)$. We use BFS from $B$ to $A$ to search for the shortest path. If we find a cycle combining the path and the edge, this is a possibility of the smallest cycle. We execute this process for all $(A, B)$. The solution works in $O(M (N + M))$-time.

# Others

Review 2020-06-05:

A - sample: 3, tle: 2.000, time: 03:17, from_submit: 46:11
B - sample: 3, tle: 2.000, time: 01:24, from_submit: 44:46
C - sample: 3, tle: 2.000, time: 02:37, from_submit: 42:10
D - sample: 3, tle: 2.000, time: 05:54, from_submit: 36:16
E - sample: 3, tle: 2.000, time: 12:11, from_submit: 24:05
F - sample: 3, tle: 2.000, time: 24:05, from_submit: 00:00


Tags:

Categories: