AtCoder Beginner Contest 142


AtCoder Beginner Contest 142

  • Review: 2020-06-05

Source codes


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


This is done by bit-DP.


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$.


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$.


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.


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