AtCoder Beginner Contest 152

AtCoder Beginner Contest 152

• Review: 2020-06-16

Source codes

• My submissions (AtCoder)
• My source codes (GitHub)

Solutions

A - AC or WA

Flush Yes if $N = M$; otherwise No.

B - Comparing Strings

Just do as they indicate us to. We can use the constructor of std::string.

int main()
{
  int a, b;
  cin >> a >> b;
  string s(b, '0' + a);
  string t(a, '0' + b);
  cout << min(s, t) << endl;
}

C - Low Elements

We hold int mini; as the minimum value of the passed $P _ i$’s. We reset $mini \gets \min(mini, P[i])$. If $mini = A[i]$, we execute ans++;.

D - Handstand 2

We define

$C[i][j] = $ the number of the positive numbers less than or equal to $N$ which starts by $i$ and ends by $j$.

We can compute $C$ by running on $[1, N]$. The answer is \[ \sum _ {i = 1} ^ 9 \sum _ {j = 1} ^ 9 C[i][j] C[j][i]. \]

E - Flatten

$X$ is a multiple of $A _ i$ for all $i$. Therefore $X$ is a multiple of the LCM of $A _ i$’s. Therefore the minimum is achieved when $X$ is LCM.

We can compute LCM directly by cpp_int or we can execute it by prime factorization.

F - Tree and Constraints

This is a problem solved by inclusive-exclusive principle.

Let $m _ j$ be the condition satisfying that all the edges on the pass $(u _ j, v _ j)$ are white-colored. For $i \in 2 ^ N$, let $f(i)$ be the number of the coloring which satisfies all $m _ j$ for $j \in i$. Then, we see that $f(i) = 2 ^ {N - 1 - w _ i}$, where $w _ i$ is the number of the fixed white edges determined by the conditions $m _ j$.

Then, the answer is \[ A = \sum _ {i \in 2 ^ M} (-1) ^ {\lvert i \rvert} f(i) = \sum _ {i \in 2 ^ M} (-1) ^ {\lvert i \rvert} 2 ^ {N - 1 - w _ i}. \] Thus what we have to do is calculate $w _ i$ for each $i$. First we calculate the mask for $m _ j$ for each $j$ by DFS. Fix $i$. Then we merge these masks by bit operations. we can compute $w _ i$ by popcount. We also use it to calculate $(-1) ^ {\lvert i \rvert}$. To compute $2 ^ {N - 1 - w _ i}$, we just use 1 << (N - 1 - w);.

Others

Assignments:
A - sample: 3, tle: 2.000, time: 01:05, from_submit: 54:07
B - sample: 2, tle: 2.000, time: 01:22, from_submit: 52:45
C - sample: 5, tle: 2.000, time: 02:54, from_submit: 49:51
D - sample: 5, tle: 2.000, time: 04:10, from_submit: 45:41
E - sample: 3, tle: 2.000, time: 14:17, from_submit: 31:24
F - sample: 4, tle: 4.000, time: 31:25, from_submit: 00:00