# AtCoder Beginner Contest 147

Updated:

AtCoder Beginner Contest 147

# Solutions

## A - Blackjack

Determine whether $A + B + C \geq 22$ or not.

## B - Palindrome-philia

Let $N$ be the size of $S$. For $0 \leq i < N / 2$, determine $S[i] = S[N - 1 - i]$ or not. The answer is the count of it.

## C - HonestOrUnkind2

Try all possibilities. The time complexity is $O(N ^ 2 2 ^ N)$.

## D - Xor Sum 4

### Solution

We calculate $S = \sum _ {0 \leq i < j < N} A _ i \oplus A _ j$ for each binary place. For $k = 0, \dots, 59$, we can calculate as follows. $S _ k = \sum _ {0 \leq i < j < N} A _ {ik} \oplus A _ {jk} = N _ o N _ e 2 ^ k,$ where $N _ o$ or $N _ e$ is the number of odd or even elements, respectively.

## E - Balanced Path

### Observation

We focus on the absolute value of the difference. Thus we see the following fact.

• The two numbers on each grid is not needed. Just possess the absolute value of difference: $G[i][j]$.
• If we fix a pass on which the numbers are $a _ 0, a _ 1, \dots, a _ K$, we can compute the answer by DP.

We can solve this problem if we fix the pass and we can convert the grid-type original problem into DP by the same idea.

### DP part

#### Definition

$dp[i][j][k] =$ true or false: Whether we can achieve the absolute value of the difference being $k$ on the point $(i, j)$.

#### Initial state

$dp[0][0][G[0][0]] =$ true; otherwise false.

$\min \{ k \geq 0 \mid dp[H - 1][W - 1][k] \}$.

#### Transition

For $i = 0, \dots, H - 1$, for $j = 0, \dots, W - 1$,

• If $i + 1 < H$, we can take a tour $(i, j) \mapsto (i + 1, j)$. For $k = 0, \dots, C$, if $dp[i][j][k]$ is true, $dp[i + 1][j][\lvert k \pm G[i + 1][j] \rvert] \gets$ true.
• If $j + 1 < W$, we can take a tour $(i, j) \mapsto (i, j + 1)$. For $k = 0, \dots, C$, if $dp[i][j][k]$ is true, $dp[i][j + 1][\lvert k \pm G[i][j + 1] \rvert] \gets$ true.

### How to use bitset

If we are allowed double-count of $\pm c$, we can use bitset. Shift operation is critical.

  vector<vector<bitset<C>>> DP(H, vector<bitset<C>>(W, 0));
DP[0][0][G[0][0] + D] = 1;
for (auto i = 0; i < H; ++i)
{
for (auto j = 0; j < W; ++j)
{
if (i + 1 < H)
{
DP[i + 1][j] |= DP[i][j] << G[i + 1][j];
DP[i + 1][j] |= DP[i][j] >> G[i + 1][j];
}
if (j + 1 < W)
{
DP[i][j + 1] |= DP[i][j] << G[i][j + 1];
DP[i][j + 1] |= DP[i][j] >> G[i][j + 1];
}
}
}


## F - Sum Difference

### Initial step

Let $U$ be the sum of the all $a _ i$. Then, $S - T = S - (U - S) = 2S - U$. Here $U$ is fixed. Thus we can count how many possibilities $S$ can achieve.

If $d = 0$ and $x = 0$, the answer is $1$. If $d = 0$ and $x \neq 0$, the answer is $N + 1$. Hereinafter we assume $d > 0$ since if $d < 0$, we can continue solving this problem converting $x \gets -x$ and $d \gets -d$.

We can write the $i$-th element as $x + di$.

### Observation

We try all $0 \leq k \leq N$, where $k$ is the number of the elements taken by $S$.

Then, $S$ is calculated as follows. $S = k x + d \sum _ {i \colon k \text{ elements}} i.$

Here, $\sum$-part will achieve its minimum $L = 0 + 1 + \dots + (k - 1) = \frac{(k - 1)k}{2},$ and its maximum $R = (N - 1) + (N - 2) + \dots + (N - k) = kN + \frac{(k + 1)k}{2}.$ Note that $\sum$-part runs on all $[L, R]$. Therefore, the all possibilities of $S$ is described as follows. $S _ k = \{ kx + dX \in \mathbb{N} \mid L \leq X \leq R \}. \tag{F.1}$ We want to concat all the S _ k. How can we do that?

### Solution

We convert it into the range-concat problem split into $D$ columns. Let $r = (kx) \% d$ and $m = (kx - r)/d$. Note that, in C++, if $x < 0$, the normal operation of $\%$ results in $r < 0$. Make sure that $0 \leq r < d$. Therefore we can regard (F.1) is as the range $[m + L, m + R + 1)$ on the $r$-th quotient space.

Then, the concat operation is done by simple task-scheduling problem.

Tags:

Categories: