AtCoder Beginner Contest 169

Updated:

AtCoder Beginner Contest 169

  • Review: 2020-06-19

Source codes

Solutions

A - Multiplication 1

Just flush $A \times B$.

B - Multiplication 2

Solution

We must obey the rule “if the result exceeds $10 ^ {18}$, print -1 instead”, avoiding the overflow. Here is an easy way; casting ll into long double for us to multiply two integers without overflow.

Thus, when we see the the result exceeds $10 ^ {18}$, we stop there, flush -1 and exit. There occurs, however, a new problem here. If there exists such $i$ that $A _ i = 0$, the real result will be $0$ but by this algorithm we mistakenly flush -1. Thus before executing the multiplication, we check whether there exists $i$ so that $A _ i = 0$.

C - Multiplication 3

This is a problem about truncation error.

We get the input by ll a; and long double b;. Then, we cast $100b$ into ll c; by static_cast<ll>(floor(b * 100 + 0.5));. Then, flush $ac / 100$.

D - Div Game

Let $N = \prod _ i p _ i ^ {e _ i}$ be the prime factorization. The best way to choose $z$ is to try $z = e _ i ^ 1, e _ i ^ 2, \dots$ and so on to the extent that we can no longer divide the integer for all $i$. The answer is its sum.

E - Count Median

Solution

Let $M _ A$ and $M _ B$ be the median of $\{ A _ i \}$ and $\{ B _ i \}$ respectively. Then, the possible medians lies in $[M _ A, M _ B]$. We can arbitrarily choose each element in $[A _ i, B _ i]$. Thus, if $N$ is even, the median is available by $(1 / 2)$-based indentations; if $N$ is odd, the median is available as integers.

Implementation

To avoid non-integers, if $N$ is odd, we double $A _ i$ and $B _ i$ in advance. Then, the answer is $M _ B - M _ A + 1$.

F - Knapsack for All Subsets

Solution

Let $T$ be the subset of $\{ A _ i \}$. Let $U \subset T$ be the set of $A _ i$ on which we consider the sum, i.e., $\sum _ {A _ i \in U} A _ i = S$.

Instead of fixing $T$ and then choosing elements for $U$, we decide whether the element $A _ i$ is included in $U$ and / or $U$ for each $i$. Then, this manipulation becomes choosing the following three possibilities for each $A _ i$.

  1. $A _ i \in U \subset T$.
  2. $A _ i \not \in U$ but $A _ i \in T$.
  3. $A _ i \not \in T$.

Therefore, we can solve this problem by fixing a little the well-known ordinary $0/1$-knapsack problem.

DP part

Definition

$dp[i][j] = $ the possibilities where we work on $A[0, i)$ to generate $\sum _ {A _ k \in U} A _ k = j$.

Initial state

$dp[0][0] = 1$; otherwise $0$.

Answer

$dp[N][S]$.

Transition

For $i = 0, \dots, N - 1$, for $j = 0, \dots, S$, we execute the followings. \[ \begin{align} dp[i + 1][j + A[i]] & \mathbin{ {+} {=} } dp[i][j] & & (j + A[i] \leq S), \\ dp[i + 1][j] & \mathbin{ {+} {=} } dp[i][j]. \end{align} \] Here the former line is corresponding to the case 1., and the latter line is to the cases 2. and 3.

Others

  • 2020-06-01
A - sample: 2, tle: 2.000, time: 00:59, from_submit: 44:38
B - sample: 3, tle: 2.000, time: 03:16, from_submit: 41:21
C - sample: 3, tle: 2.000, time: 02:44, from_submit: 38:38
D - sample: 5, tle: 2.000, time: 04:45, from_submit: 33:53
E - sample: 2, tle: 2.000, time: 06:45, from_submit: 27:08
F - sample: 3, tle: 2.000, time: 27:08, from_submit: 00:00
  • 2020-06-19
A - sample: 2, tle: 2.000, time: 05:43, from_submit: 21:28
B - sample: 3, tle: 2.000, time: 04:36, from_submit: 16:52
C - sample: 3, tle: 2.000, time: 03:13, from_submit: 13:39
D - sample: 5, tle: 2.000, time: 02:49, from_submit: 10:50
E - sample: 2, tle: 2.000, time: 06:29, from_submit: 00:00
F - sample: 3, tle: 2.000, time: 04:21, from_submit: 01:27