AtCoder Beginner Contest 169
Updated:
- 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.
touristのコード見てたらoverflow避けがこんなに簡単にできるんですねと勉強になった。
— kjnh10 (@kjnh10) May 23, 2020
if ((long double) d * (long double) x < ret) {
ret = d * x;
}
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$.
- $A _ i \in U \subset T$.
- $A _ i \not \in U$ but $A _ i \in T$.
- $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