Kazune Takahashi

Ygnaiih… ygnaiih… thflthkh’ngha

AtCoder Beginner Contest 159

Updated:

AtCoder Beginner Contest 159

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

You May Also Enjoy