AtCoder Beginner Contest 147

AtCoder Beginner Contest 147

• Review: 2020-06-10

Source codes

• My submissions (AtCoder)
• My source codes (GitHub)

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.

Answer

$\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