AtCoder Beginner Contest 142

Updated:

AtCoder Beginner Contest 142

Source codes

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

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

D - Disjoint Set of Common Divisors

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

  Sieve sieve;
  ll A, B;
  cin >> A >> B;
  ll M{gcd(A, B)};
  auto V{sieve.factor(M)};
  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$.

Answer

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 does 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$. If we find a cycle, 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