# AtCoder Beginner Contest 147

Updated:

AtCoder Beginner Contest 147

• Review: 2020-06-10

# Solutions

## A - Blackjack

### Solution

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

### Implement

I noticed that I should not have done by vector<int> A(3). We just use int A, B, C;. It is faster in terms of writing codes.

## 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. If not, we increment the counter. The answer is the count of it.

## C - HonestOrUnkind2

### Solution

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

### Caution

Be careful that, in this problem, the unkind people do not necessarily tells us wrong things. We check only honest people’s statements.

## 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{Z} \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$; if $r < 0$, we have $r \mathbin{ {+} {=} } d;$. Therefore we can regard (F.1) is as the range $[m + L, m + R + 1)$ on the $r$-th quotient space.

More precisely, let f \colon \mathbb{Z} \to \mathbb{Z} / d \mathbb{Z} \times \mathbb{Z}$be defined as follows. $f(n) = (n \% d, n / d).$ Then, we see that$f$is bijection. In addition, we have $f( S _ k ) = { r } \times [m + L, m + R + 1).$ where$r$,$m$,$L$and$R$are defined as above. Therefore, the concat operation is done by simple task-scheduling problem by using map<ll, vector<Schedule>> M;. To insert$S _ k$, we push$M[r] \gets [m + L, m + R + 1)\$. Here we define using Schedule = tuple<ll, bool>; and push_back two elements for each interval.

# Others

Review 2020-06-10:

A - sample: 2, tle: 2.000, time: 03:06, from_submit: 81:17
B - sample: 3, tle: 2.000, time: 01:26, from_submit: 79:50
C - sample: 3, tle: 2.000, time: 23:00, from_submit: 56:51
D - sample: 3, tle: 2.000, time: 05:13, from_submit: 38:34
E - sample: 2, tle: 2.000, time: 13:03, from_submit: 40:49
F - sample: 3, tle: 2.000, time: 38:35, from_submit: 00:00


Tags:

Categories: