AtCoder Beginner Contest 159
Updated:
Source codes
Solutions
A - The Number of Even Pairs
The answer is \[ \frac{N (N - 1)}{2} + \frac{M (M - 1)}{2}. \]
B - String Palindrome
Let $T = S[0, (N - 1) / 2)$. Check if both $S$ and $T$ are palindromes or not.
C - Maximum Volume
The answer is $X ^ 3$, where $X = L / 3$.
D - Banned K
Let $M$ be such a map that $M[i] = \sharp \{ j \in N \mid A[j] = i \}$. If there is no restriction, the number of pairs whose elements are the same is \[ S = \sum _ {(x, c) \in M} \frac{c(c - 1)}{2}. \] For the case that $A[i]$ is banned, we subtract $M[A[i]] - 1$ from $S$ to get the answer.
E - Dividing Chocolate
Observation
Greedy algorithm + Brute force. We try all the possibilities of the division of the horizontal lines. Hereinafter we fix the cuts of the horizontal lines and we focus on the vertical lines.
Solution
To minimize the number of the cuts of the vertical lines, a greedy algorithm from left to right works. For each vertical lines, we decide to cut it or not to. If none of the pieces breaks the rule, i.e., each pieces has less than or equal to $K$ white chocolates, we decide not to cut the line. Otherwise, we decide to cut it.
The total time complexity is $O(2 ^ H HW)$.
Implementation
For each $mask \subset (H - 1)$, we define the following.
$k = $ the number of the chocolates from the viewpoint of the horizontal cuts,
vector<int>$toInd(i) = j$; the $i$-th row contributes to the $j$-th chocolate from the viewpoint of the horizontal cuts.
We possess vector<int> sum(k); as the sum of the white chocolate.
For $j = 0, \dots, W - 1$, we make $tmp = sum$. For $i = 0, \dots, H - 1$, we add the white chocolates to $tmp$ using $toInd$.
We check if each pieces in $tmp$ exceeds $K$ or not.
- If so, we cut before this manipulation. In this case, we execute $cnt \mathbin{ {+} {+} }$, calculate $sum \gets tmp - sum$ and check if each pieces in $sum$ exceeds $K$ or not. If so, return $\infty$.
- Otherwise, we swap $tmp$ and $sum$.
For each mask, update $ans$ by $popcount(mask) + cnt$ if it is less than $ans$.
F - Knapsack for All Segments
Assume $0$-indexed.
Observation
We choose $L$, $x _ 0, \dots, x _ k$ and $R$ in this order. For each $i = 0, \dots, N - 1$, we assign each elements for $i$. We divide the states into three as follows.
- $k = 0$: We have not chosen $L$ yet.
- $k = 1$: We have already chosen $L$, but not $R$ yet.
- $k = 2$: We have already chosen $R$.
Solution
We apply Snuke’s DP for this problem.
Definition
$dp[i][j][k] = $ the number of the ways to choose elements from $A[0, i)$ so that its sum is $j$, with the current state being $k$ as above.
Initial state
$dp[0][0][0] = 1$. Otherwise, $0$.
Answer
$dp[N][S][2]$.
Transition
For $i \in N$, for $j = 0, \dots, S$, for $(k, nk) \in 3 ^ 2$, for $l \in 2$, we execute the following.
\[
dp[i + 1][nj][nk] \mathbin{ {+} {=} } dp[i][j][k].
\]
Here, we use $l = 0$ to denote that we don’t choose $A _ i$ to add it to the sum, $l = 1$, we choose. Therefore, we would like to execute the following.
\[
nj = \begin{cases} j & l = 0, \\ j + A[i] & l = 1. \end{cases}
\]
Before this execution, we check the transition is valid. If $nj > S$, we have break;. We cannot roll-back $k$ into previous states. Hence, if $k > nk$, we have break;. We also check whether we can pick $A _ i$ up if $l = 1$. If $(k, nk) = (0, 0)$ or $(2, 2)$, we cannot; otherwise, this picking is valid.
Another Solution
We follow the way appeared in YouTube Live.
First, we think of the $0/1$ knapsack problem. The answer is the coefficient of $x ^ S$ of the following polynomial. \[ \left(1 + x ^ {A _ 0} \right) \left(1 + x ^ {A _ 1} \right) \dots \left(1 + x ^ {A _ {N - 1}} \right). \]
Therefore, the answer for our problem is the coefficient of $x ^ S$ of \[ \sum _ {R = 0} ^ N \sum _ {L = 0} ^ {R - 1} f(L, R), \] where \[ f(L, R) = \prod _ {i \in [L, R)} \left(1 + x ^ {A _ i} \right). \]
Let’s convert this into DP.
Definition
We define vector<vector<mint>> dp(N + 1, vector<mint>(S + 1, mint{0})); as follows.
\[ dp[i] = \sum _ {L = 0} ^ {i - 1} f(L, i). \]
Initial state
$dp[0] = 0$.
Answer
The coefficient of $x ^ S$ of the following polynomial. \[ \sum _ {i = 0} ^ N dp[i]. \]
Transition
For $i = 0, \dots, N - 1$, we have the following.
\[
\begin{align}
dp[i + 1] &= \sum _ {L = 0} ^ {i} f(L, i + 1) \\
&= \left( 1 + x ^ {A[i]} \right) \left( \sum _ {L = 0} ^ {i - 1} f(L, i) + 1 \right) \\
&= \left( 1 + x ^ {A[i]} \right) \left( dp[i] + 1 \right).
\end{align}
\]
For example, we implement as follows.
for (auto i{0}; i < N; ++i)
{
dp[i][0]++;
dp[i + 1] = dp[i];
for (auto j{0}; j + A[i] <= S; ++j)
{
dp[i + 1][j + A[i]] += dp[i][j];
}
dp[i][0]--;
}
Others
- 2020-06-20
A - sample: 5, tle: 2.000, time: 09:44, from_submit: 57:29
B - sample: 3, tle: 2.000, time: 02:25, from_submit: 55:04
C - sample: 2, tle: 2.000, time: 00:59, from_submit: 54:06
D - sample: 4, tle: 2.000, time: 02:36, from_submit: 51:30
E - sample: 3, tle: 2.000, time: 28:34, from_submit: 22:55
F - sample: 4, tle: 2.000, time: 14:38, from_submit: 00:00